___82連鎖: 3月 2013

3/29/2013

450

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

250

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

450

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

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

250

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

500

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

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

300

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

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

500

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

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

250

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