問題概要 グラフとクエリが与えられる。それぞれのクエリで指定されたただ1つの頂点Kを通過して頂点aから頂点bまでの最短経路長を求める。 atcoder.jp 解法 どうせa->KとK->bをいちいちdijkstraしていたのでは間に合わないのだろうなあという気持ちになる。 …

問題概要 2人で交互に文字列から1文字ずつ除いていく。先に任意のアルファベットを隣り合わせた方が負け。2人とも最適に動いた時どっちが勝つ? atcoder.jp 解法 最終的に出来上がる(敗者の最終手を打つ前の段階の文字列)は1字飛ばしで同じ文字が存在すること…

問題概要 黒色と白色のマス目で構成されたマス目が与えられる。操作(問題文参照してください)を行って全てのマスを黒色にする場合の最小の操作回数を求める。 atcoder.jp 解法 まず、黒色のマスが初期状態で存在しない場合、無から有は錬成できないので、答…

問題概要 I,O,T,J,L,S,Zの7つの型のブロック(テトロミノ)を入力された個数の範囲内で組み合わせて縦2マス、横2Kマスの長方形を作る時のKの最大値を求める。 atcoder.jp 解法 上で言った6つの型のテトロミノを以下そのアルファベット名で呼称する。 まず、作…

問題概要 スタートマスから経由すべきマスを全て経由するルートを1つ構成する。 onlinejudge.u-aizu.ac.jp 解法 グリッド上で条件を満たす経路を1つ構成する問題はロシアゲーとか呼ばれているらしい(他のロシアゲーの例:D - Grid Coloring。解説記事はこれ)…

問題概要 与えられた文字列に含まれる"WA"という文字列を全て"AC"という文字列に置き換えるとどうなるか。 atcoder.jp 解法 文字列を逆に見ていって"AW"(逆に見ているのでこうなる)があったら"CA"に変えればいい。O(|S|)。 atcoder.jp

問題概要 N本の竹から色々操作をして長さがA,B,Cの3本の竹を得るためにはどのくらいMPが必要か(操作1回ごとに必要MPが定められている)。 atcoder.jp 解法 AtCoderにしてはまあまあ珍しい(本当か?(要出典))愚直な全探索。O(4^N)。 atcoder.jp