ICPC 2015 国内予選 参加記

ICPC

チーム ikura-hamachi-salmon で参加して32位でした。

登場人物

  • 私 (B4, ICPC 4回目)
  • 23氏 (M1, ICPC 4回目)
  • OUDON氏 (B2, ICPC 2回目)

出来事

  • 打ち合わせ通り，私がA問題を担当する。例年より難しいような…。うちの1年生チームは解けるかな…？とりあえず合格点を全探索して10分くらいでAccepted
  • OUDON氏がB問題を担当する。解法は自明らしいので任せておいた
  • 次に簡単なのはC問題だと23氏に教えてもらったので問題文を読む。「整数は1ケタ」「整数は9個まで」など実装上のテクがいろいろ書かれたメモがあってサイコー。いつもの再帰降下型の構文解析器を流用すれば，めちゃくちゃ簡単に書けそうな気がしてきたので，D問題を読む
  • OUDON氏がB問題をバグらせているらしいので，印刷して23氏と紙デバッグしてもらうことに
  • その間にC問題を書くと予想以上に簡単に書き終わってAccepted
  • B問題がしょーもないバグだったそうなのでC問題のすぐ後にAccepted。ここまで30分〜40分くらい。このときの順位は15位くらいだった
  • 再びD問題を読む。どうせ硬貨の枚数をキーにしてDPするんだと思うけど，どこから手を付ければ良いのか分からない。いろいろ実験して知見を集めるのが良さそうな気がしたので23氏に実験してもらう
  • E問題をOUDON氏が読んでいたのでF問題を読む。最初に制約を考えずにMSTしてから貪欲に調整していくのかな？
  • G問題を読む。自明にやばそう。折り紙を実装したことが無いのでパス
  • H問題を読む。座圧してそれからどうするの？
  • 解ける可能性があるとしたらD問題かE問題だろうということになり，D問題をみんなで考察する
    • 各種類の硬貨の枚数をキーにする必要があるのか，硬貨の合計金額だけ持っていればよいのかで意見がいろいろ出る
    • 10円玉1枚と1円玉10枚は等価？
    • 1回の支払いで得られる小銭の最大の枚数は，100円玉は4枚，50円玉は1枚，… で，支払いは最大100回あるので， dp[100][400+1][100+1][400+1][100+1][400+1] (店，100円玉，50円玉，10円玉，5円玉，1円玉) というのが考えられるけど当然NG
    • 実は dp[100][4+1][1+1][4+1][1+1][4+1] だけで良い？ もしかして dp[100][999+1] だけで良い？
    • mod 1000 しか考えなくても良いとか，支払金額は定価〜定価+999のどれかであるとか，DPの要素の型はpair<int(500円玉の枚数), int(-支払金額)>でmaxを取れば良いとか，いろいろ知見は集まるが解法まで辿り着かず
  • 暗雲が立ち込めてきたのでE問題にとりかかる
    • 「ロックをかける順番によって作った有向グラフにサイクルが存在する」ことは「デッドロックが発生しうる」ことの必要十分条件だと思っていたのだけど，実は必要条件であって十分条件ではないらしい (知らなかった)
    • 「データベースの教科書を持ってこればよかったなぁ」とぼんやりと考えていたら，そういえばデータベースの講義は金曜日にあったことを思い出し，鞄からデータベースの教科書を取り出す
    • 「さすがにデッドロックの検出方法は載ってるでしょーｗ」と意気揚々と読み始めるが，「デッドロックが現在発生しているか」ということを検出する方法しか書いておらず役に立たなかった

まとめ

最後の150分座ってるだけだったつらい