UTPC (プログラミングコンテスト)

年齢が鶴の寿命に並んだせいか 2 時間で息切れしてしまった.

A-C-B-D-E-F-G-J の順に受理された. ぽかをやって Problem F で一度だけ Wrong Answer を食らった. ほかは全部一発.

Problem A
提出のときに 0 という Problem ID を指定すると練習問題に対する提出とみなされるという少々変わったトラップにひっかかってしまった.同様のトラップにはまった人は結構いたようだ. :Problem B:「プログラムの実行時間が制限時間を越えないように注意すること」という注意書きと,入力の上限値を見た瞬間に,反射神経的にさけてしまったが,よくよく考えてみれば計算量は O(√N) になるので何の問題もないのでした.ここでの判断間違いは最後まで響いたように思う. :Problem C:[1,1,1,2,2,2,3,3,3] の順列を全生成して,同じ番号が振られた 3 枚組がそれぞれセットを構成するか調べるだけだが,実装がちょっと面倒くさい. :Problem D:とりあえず鉄の壁で外枠を囲む.戦車はマップ(を格納する二次元配列)には記入せず,入出力のときに細工する. :Problem E:隣接する家同士の間隔に着目して,長いほうから (k-1) 個の間隔だけは線を引かないようにする. :Problem F:譜面の長さを n 倍にする関数と 1/n 倍にする関数をそれぞれ用意すれば 8 割がたおしまい.後者は 00 以外が消去されるときは実行されないように細工すること.入力文字列の長さを最短にするときは 1/n 倍にする関数を繰り返し呼び出すわけだが,このとき n に関するループは大きいほうから回すとよい(小さいほうから回すときは圧縮不可能になるまで同一の n の値について 1/n 倍の関数を呼び出し続ける必要がある).長さの上限に関する定数値の設定を間違えるというちょっとしたポカをしてしまった. :Problem G:実は左側から順番に処理すればよいので動的計画法が適用できる.気づくまでだいぶ時間がかかった(うすうすは気づいていたが確信が持てなかった).きちんと検討すれば決定的に計算できるかもしれない. :Problem H:解いたのは nya3 ひとりだけ.たぶん「駅 s から駅 t まで,ちょうど i ステップで到達可能であるかどうか」という表 p[s,t,i] を用意して(s = t の場合も含める),こいつを上手にいじれば解けるという気はするが….このとき i は 1..N だけで十分のはず.書いているうちに気づいたが,ひょっとしたら余りに着目すればいいのかもしれない. :Problem I:メモつきのミニマックスを書いたら見事に誤作動した.メモを外すと今度はまともに終わらない.あとで考え直したら(コンテストの時間内に)解法はわかった.ショートカットのない長さ 4 以上の閉路がないか調べて,閉路があるときは,閉路中のノードの全部について,Aaron が到達する前に Bruce が到達できるかどうか確認する(同着は Bruce が到達可能とみなす).到達不可能なノードがひとつでもあれば infinity になる.複数の閉路があるときは全部の閉路について調べる.それ以外のときはダイクストラを 2 回走らせればほとんどおしまい.解法がわかったときは,ループのチェックを書くだけの気力が残っていなかったので泣く泣く捨てた. :Problem J:LL(1) 向けの再帰降下法以外のパーザーは満足に書けないので相当苦労した.受理されたコードを見直したら SLR(1) のパーザーになっていた.ちなみに通ったのは終了 5 分前ぐらい. :Problem K:これを解けばよかったかな.反復進化か幅優先探索をやればすむだろうということはわかっていたが,この問題を読んだころには探索のコードを書くだけの気力がなくなっていたので,手つかずのまま終わった. :Problem L:図を見た瞬間に吐き気がしたので問題文をまともに読んでいない.

提出物一式NYSL

〔追記〕 Problem I について.上記解法は問題があるという指摘をオフラインで受けました.想定解法はキャッシュつきの min-max を少し工夫したものらしい.