The 2nd Imos Contest

ICPC

いもすさんちに遊びに行ってきました。

Problem A: Cards
  • 初っ端からyukとペアプログラミング。
  • 最初や最後のカードが抜けてるケースは撃墜ポイントだなぁとか思ったけど、よく見たら全部Sampleに入ってた。残念。
  • つつがなくAccepted。
Problem B: Imos Day
  • とりあえずBFS2回で。
    • DFSを選ばなかったのは趣味です。
  • さっくり実装。でも答えが出てこない。
  • そもそも入力のTreeがTreeになってない。どう見ても入力の取り間違いです。
  • yuk曰く、「rootが省略されてるんじゃね？」なるほど。
  • 直したらSample出てきた。Accepted.
Problem C: Lucky Time
  • 後輩Kが果敢に挑むも撃沈。
Problem D: Hailstones
  • 最初は周期を真面目に計算する方向で考えてたけど、ふと lcm(1, 2, ..., 10) と決め打ちしていいことに気付く。
    • lcm(1, 2, ..., 10) = 2520. ってLayCurseさんが言ってたのを思い出してベタ打ち。
  • 実装はyukに任せました。ちょっと嵌ってたようですが、最終的にはAC貰ってました。
Problem C: Lucky Time　(Retry)
  • 86,400回ループ * 5,000ケースはギリギリ間に合ってくれると信じて*1yukが突撃。
    • 駄目だった。何度か定数倍最適化するもTLE。
  • まだまだ最適化が足りないのだ、ビット演算使えばどうにかなるはず、と信じて私が突撃。
    • 私はそこまでビット演算を使いこなせなかった。Sample出てこない。
  • ついにyukが先に全ケース計算しておけばいいことに気付く。
  • 実装してそのままAccepted。
    • この1問のために書いたソースコードが4つ。全部合わせて268行。
    • いくらなんでもアホすぎる・・・。
  • この時点で残り10分だったので、諦めてみんなでのんびりまったりする。
    • FはPollard's Rho Methodで一発だと気付いたけど、あのライブラリは作りかけのまま放置してた。
      • ちゃんと作っておけばよかった・・・。
  • おつかれさまでした。
  • 19位。
  • -Wに僅差で負けました。残念。
  • そろそろ次のコンテストの問題文を書く作業に戻ります。

*1:Problem Bの計算量と実際の実行時間から概算しました