360.1

日付が変わっても最新の日記を書こうとすると前日の分に書かされそうになる件について。0時からのイベントは今日の日記です。

250

数字がたくさん並んでいるテーブルがあって、同じ列や行から2個取らないようにしつつ、できるだけたくさん数を取る。その場合、どうやっても同じ合計になるなるか、そうでないかを判定せよという問題。

縦横の長さが違う場合の処理を入れないといけないなぁと思い、縦横の長さが違う場合には同じ数字がずらっと並ぶことを確認した上でそういうルーチンにしたのですが、よくよく考えてみると探索する深さを短い方にあわせてメモ付き全探索すれば良さそうです。メモ付き全探索は正方形の場合にしか適用できないと思っていたので、ルーチンが長くなった感じ。

500

迷路の中にいる二人を出会えなくするのに必要な壁の個数を求めよという問題。

何も考えないで解くならば、グラフを書いて最大流です。でも、なにやら、一人の周りに4つ壁を置けば通れなくさせることは絶対にできるので、1〜3個置いて通れなく出来るかどうかを判定すれば良いそうです。実際盤面の大きさは10x10なので、全部試しても1M通りちょっとくらいにしかなりません。頭いいなぁ。

ライブラリある人が何も考えずに最大流を求めた方が圧倒的に速いとは思うし、最大流を浮かべてしまった人は最大流以外の解法に確信を持てるかどうかというところ。昔書いた最大流のルーチンを拾ってきたけれど、メモリを大量に使用するらしく失敗。まぁ2部グラフであることを前提に書いたルーチンだったので、ないよりはいいくらいのものだったのかも知れないけれど。

1000

凸包の作りかけデータをもらえるので、それに最短のデータを継ぎ足して凸包を完成させよという問題。何通りもある場合には一番小さいものを答えよという問題。

取り敢えずもらったデータが凸包であるかどうかを判定して、新しい点を小さい順に追加していけば良さそう。3角形が既にできている状況なら、1点足せばおしまいだと思う。500で時間切れしたのでやってないけど。