解いた問題

3/29/2013

SRM551 Div1 Medium

450

変更の回数をコストにしてダイクストラする。

SRM551 Div1 Easy

250

並べる文字と並べる位置を全部試す。

SRM574 Div1 Medium

450

memo[ どの頂点を使った ][ 最後にどこを使った ]

次に使う頂点との両側にすでに訪れた頂点があれば交差する。はず。
0 と N-1 の隣接を忘れるという悲しい出来事があって本番中に通せなかった。

SRM574 Div1 Easy

250

とりあえずメモ化する。意外と間に合う。

3/25/2013

SRM550 Div1 Medium

500

配置の仕方が、nCk = n-1Ck-1 + n-1Ck を何となく連想させる。
描画してみる。向きと幅がアレだけど、nCk mod 2 のフラクタルに見える。しかし、値の範囲が大きすぎる。

どうやら、nCkが奇数であることと(~n&k)==0は同値らしい。

3/24/2013

SRM550 Div1 Easy

300

座標の最大と最小から盤面のサイズを予測する。
予測した盤面上で動きが再現できりるか試す。

問題を把握するまでに時間を要した上に、実装でもつまらない間違いを連発。
悲しい。

3/21/2013

SRM572 Div1 Medium

500

前半分と後半分に分けて、半全列挙。
半全列挙なんて最後に使ったのいつだったろう。すっかり存在を忘れていた。

探索でも解けるらしい。rand を使っている人もいた。

SRM572 Div1 Easy

250

前からの範囲と後ろからの範囲がオーバーラップすることに注意。
同じ文字にする必要のあるインデックスの中で、どれに合わせるべきかを調べていく。

3/17/2013

SRM 567 Div1 Medium

500
文字数の多い文字から考える。難しさが easy と大差ない気がする。

SRM567 Div1 Easy

250

積が平方数になるような2つの数を考えればいい。

SRM571 Div1 Medium

500
クリークなんて、どうせバックトラック。3 m >= 2 n の条件から、16個くらいの頂点を消すことを考える。

SRM571 Div1 Easy

250
バックトラックして頭から作っていく。