http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2271 問題 略 解法 やるだけ。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1317 問題 換字暗号により暗号化された文がある。使用されえる単語をn個与えるので復号しろ。 1 解法 暗号文の単語に含まれる文字の種類が多い順にソートしてバックトラックで解く。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1324 問題 頂点数nで重み付きの辺がm本でさらに各頂点に通行料feeと高さhが与えられた有向グラフが与えられる。始点(fee=0,h=0)から終点(fee=0,h=1000)まで往復したい。ただし、通行料を取られる…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1318 問題 辺数nのグラフが与えられる。srcからdestまで行きたいのだが途中でLGPガスを補給する必要がある。車の燃料タンクにはcap分だけLGPガスを搭載できる。またLGPガスステーションはグラフ中…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1316 問題 ドーナッツに文字が書かれている。文字を8方向のいずれかで見た時に、2回以上でる文字列でかつ最も長いものを答えよ。2つ以上ある場合は辞書順最小のものを答えよ。 3 3 解法 全列挙す…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1315 問題 各個人の部屋に入った時間と出た時間が与えられる。プログラムの女神と一緒に最も長く部屋にいた人の時間をtとする。そのような人の数*tを求めよ。 解法 やるだけ。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1322 問題 数式を与えるので計算しろ。 解法 上端、下端、右端を持ってパースするだけ。分数を見つけたら適当に上下に分割する。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1321 問題 マインスイーパーの盤面を与えるので爆弾を置く数を最小化しろ。 1 ヒントの数 爆弾を置けるのは*かヒントの位置 解法 各数値の周り9マスを順番に見る＋どこまで見たかと数値の周りにあ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1314 問題 matlabの演算を実装しろ。 解法 やるだけ。indexed-primaryとtransposed-primaryはprimaryの直後にwhileループで実装する。スカラーも行列型で実装すると楽。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2289 問題 略 解法 解説通りにてきとうに多めに候補点を取れば良い。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2287 問題 略 解法 同じ高さの水槽で連結成分を作って有向グラフを作る。あとは各クエリに対して、その時間まで高い水槽からいっきに水を流す。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1292 問題 線分と円弧でコマの輪郭を与えるのでその重心を求めよ。またその重心がコマの内側かどうか判定せよ。 線分、円弧の個数 座標の絶対値 解法 解説に書いてあるように円弧を線分で近似すれ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1294 問題 図のように折れ線でn個の点を結んでいく。ただし、途中の線分には2つ以上の点が乗っていなければならない。折れ曲がり回数の最小値とその時の線分の長さの合計の最小値を求めよ。 n 解…

First AC狙いでやっぱり後ろか見ていくことに。 I問題 うまい扇の取り扱い方ってあったっけ？ モンテカルロ法とかεずつ動かして試すくらいしか思いつかんなあ。 H問題 夏合宿に似た問題があった気がする。 今見ているノートの切れ端を2つとどこまで見たかで…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2307 問題 頂点数n、辺数mの有向グラフが与えられる。各頂点には文字列が書かれている。グラフをwalkしたときに訪れた頂点の順番で文字列を連結した物を考える。そうしてできた文字列で回文になっ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2257 問題 略 解法 解説通りにAhoCorasickを使った。メモリ制限がきつかったんで状態をmapで保持＋dpし終わった所はclearするようにした。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2270 問題 略 解法 解説に書いてある通り、永続データ構造を使った。二部探索木と言うよりかは頂点の数値を1〜nに圧縮して、セグメントツリーっぽく保持した。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2268 問題 略 解法 解説に書いてある通り、深さは2*lognくらいまでしか見ず、fftで畳み込み計算を行った。

なんとなく後ろから見ていく。 J問題 x番目の要素をO(logn)で取り出せる二部探索木があれば楽勝な気が。 I問題 DP臭い でも1周して戻ってくるのをどこで使うかで厄介になってくるなあ そんなもん初めに全部使ってしまえばいいじゃね？ 書いた。合わん。「や…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1070&lang=jp 問題 略 解法 dequeを6個使う。数列の前半部分、後半部分を保持するのに2個。最大値・最小値×前半・後半で4個。 数列は中央で折って、(n+1)/2と(n+1)/2+1番目の数値をdequeのfrontに…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1064&lang=jp 問題 略 解法 書いてある通りに実装するだけ。

問題 略 解法 DPで解く。普通に考えるとだが、Mに関しての総和を持っておくとに落ちる。さらに途中ででかい数値を使うとどう頑張ってもSを超える場合があるので、その場合をスキップすることにより枝刈りが効いて間にあうようになる。 MLEも厳しいのでDPの配…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2221&lang=jp 問題 略 解法 一番上の列から始めて、左から右の順に押すボタンを決めることにする。そうすると直前の5つのボタンの押し方が分かっていればボタンの左上にあるマスの得点…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2220&lang=jp 問題 略 解法 解法は主に3通りある。 1つ目は二部探索により実数解をひとつ見つけ、その解を使って次数を一つ落として二次方程式の解の公式を使って解く方法。 2つ目はカ…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2219&lang=jp 問題 略 解法 各能力値ごとにナップサック問題を解く。C問題より楽な気がするけど実際にはCより解かれてない。まあ私が1回生の時には解けなかったことを考えると当然かも…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2218&lang=jp 問題 略 解法 実装ゲー。ストレート、フラッシュの判定と各手札の枚数を数えて役をチェックすると楽。ストレートの判定の部分をミスって1WAした。出題の意図としては、ア…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2217&lang=jp 問題 略 解法 全てのマスに対してdfsを行い、現在のdfsで訪れたマスにきた場合はループのカウントをする。他の探索で訪れていた場合は無視する。

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2216&lang=jp 問題 略 解法 やるだけ。皆O(1)でやると思ってたらO(n)でやってる人が結構いてびっくりした。

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1023&lang=jp 問題 略 解法 平面走査を行う。 各点のイベントとしてx-2*rの位置にinイベント、x+2*rの位置にoutイベントを挿入してx座標でソートしておく。 イベントが起こるとy座標で…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1059&lang=jp 問題 略 解法 メモ化全探索で間にあう。探索自体は左上の敵から始めてその点を0にするような長方形を使った場合を全て調べればよい。 微妙にメモリが足りないので一番左上…