ICPC練習会

Algorithm

今終了．久々の緊張感が心地よかったです．問題はこちらから．

http://icpc-mock.ipl.t.u-tokyo.ac.jp/contest/problems.html

AからCまではサクサク解けると思ってたけど，1人でやってたこともあってしょうもないミスを連発してたorz．やっぱりペアプログラミングの恩恵は大きいなぁ．一応問題の感想を．

  • A

携帯電話の文字入力をシミュレートする問題．キャンセルがなかったり確定ボタンが押されることが保障されていたり，実装し易いようになってる．ひたすらswitchで場合分け．

  • B

4種類のコインを何枚か持っていて，n円の買い物をしたあと，お釣りも全部含めて持っているコインの数が一番少なくなるようにしろって問題．最初はお釣りのみが少なくなるように実装してwrong．続いて，お釣りと払ったコインの枚数の合計で求めててwrong．アホすぎる．

何か上手いやり方がありそうだけど，分からないのでバックトラックしながら全探索．問題の規模から見ても，ジャッジ側もそれを予想している感じ．

  • C

問題の説明は省略．魔王に一番近いクリスタルに，魔王より早く到達できるかを調べる．それが無理ならNOだし，そうじゃないならクリスタル全部に対して繰り返す．

これも簡単な問題のはずなんだけど，何度も間違った．勇者の位置は，クリスタルをゲットするたびにそのクリスタルの座標に変更していけば良いんだけど，魔王はそうはいかないので，常に入力の位置からの距離を出さなきゃならない．そのとき，その時点までで侵食が進んでるはずの距離との差をとらなきゃならないんだけど，この「侵食が進んでるはずの距離」を，勇者とクリスタルの距離としなきゃならないのに，魔王とクリスタルの距離でやってたorz．だから当然ほとんどのケースでNOに．おかしいとは思いながらもwrongもらい続け，あきらめてD問題に向かったオレ．こんなとき誰かがいたらすぐにデバッグ終わってるはず！そう思いたい．

追記．オレはC問題は，とにかく魔王に一番近いクリスタルから取るように実装しました．魔王の円を横切ることは何となくなさそうだったので．

  • D

一番はまった問題．正方形と，正方形の内部を通る直線が何本か与えられて，正方形が何個の領域に分けられるかって問題．

とりあえず交差する直線の分だけ領域数を増やしていけばいいと思うんだけど，同一点とみなすかどうかの部分ではまったかもしれない．幾何が苦手なのは相変わらずかぁ．こういう問題は解けるようにならないと，アジア予選入賞は厳しそうです．

  • E

シミュレーション．頑張れば解けると思うけど，はまりそう＆めんどくさそうで手をつけず．PQを使ってイベント駆動でシミュレートするんかな．よく分かりません．

  • F

スケジューリング問題．これはちょっとやばそうな気がした．

50人いてほとんどの人とスケジュールがあう場合，各人について2パターンがあるから，状態数が爆発する．全探索は無理だとして，枝狩りか，DPか．さっぱり分からない．考える余裕すらなかったというのが正確ですね．DにはまりまくってEとFは全く手をつけませんでした．

と書いてて思ったけど，誰かに地図を渡した時点で，そいつのことは完全に無視できるから，何とかなるかも．30日という制限はどうなんでしょう．最悪のケースだとはんぱない時間がかかりそうですが．

んで，結局A,B,Cの3問を解いて7位でした．1人でやった割にはまあまあだけど，3人いてもこれくらいだったかもしれないし．順位にはあまり意味はないでしょう．

それよりメールでの出力送信とかの方がためになりました．忘れてるからね．面倒くさかったけど，とりあえず本番は大丈夫そう．本番ではまた練習セッションもあるし．

主催してくださった方々ありがとうございました＆お疲れ様でした．国内予選を突破できたら，アジア予選に向けてまた勉強会をやってくれると，わしゃ嬉しいです．

それから練習セッションのM問題．誰も解けなかったようですが，何が正解だったんだろうか．個人的には10が怪しいと思うんだけど．気になって眠れません．アメリカGP見るにはちょうどいいかも知れないけども．