[Contest] 2010 AUT ACM-ICPC Local Contest

UVa
  • チームで出るということになってたので大学に集合。
  • みんなどこにいるんだろ？とりあえずコーチの部屋に行ってみる。
  • 「『今日は台風が近づいてるから個人戦』ってメールしたよ？」
  • え。そんなメール届いてない・・・。
    • コーチのメールを確認させてもらったけど、宛先は間違ってない。でもやっぱり届いてない。
      • なんで？
  • そんなわけで個人戦。

Problem A: Abnormal 89's

  • 御飯食べて問題印刷して読みつつスコアボードを見る。
    • 早くもACしてる人がちらほら。簡単なのかな。
  • N = 200,000
    • え？どうすんの？
  • 頭 1, 2, 3, ..., N 文字が回文であることをまとめて O(N) で判定できればいいのだけど・・・。
    • うーん。どうやるんだろう。分からん・・・。
  • ...
  • 根本的に方針を変えてみよう。
  • とりあえず反転したものを並べて書いてみる。
    • "abacc" "ccaba"
    • ...ぺかーん！
  • 反転して k 文字巡回シフトしたものと一致したら alindrome!
    • いやまて、それだと palindrome も alindrome にならないか？
      • 1 <= k < n に限ればそんなことはないっぽい。
    • って、そもそも k を全通り試してたら O(N2) だ。
      • ...ぺかーん！ローリングハッシュが使える！
        • 実装！
  • 書けた。unsigned long long であるべきところが int になっててしばらくはまった。
  • submit. Wrong Answer.
  • なんだろう。とりあえずスペルは合ってるっぽい。
  • もしかしてこの解法嘘？
    • (a+b).reverse == b.reverse + a.reverse なのでそんなことはないはず。
  • 超絶運が悪くてハッシュが衝突してる？
    • とりあえずハッシュの係数を変えてみる。さすがにこれだけではsubmitしないけど。
  • うーん。他に怪しいところはないだろうか。
  • ...
  • って、スペル間違ってる！
    • 「とりあえずスペルは合ってるっぽい」とか言ってるバカをお仕置きしたい。
  • Accepted. これはひどい。

Problem B: Benefit

  • 問題文にLCMという単語を見つけたあたりから、この問題が頭の中をぐるぐるし始める。
    • 読めた。似たような解法でいける。勝ち組だ。
  • 適当に素因数分解する。出来た。
  • submit. Runtime Error.
    • 素因数分解がおかしい。ループn回で切られるようにしてsubmit.
  • TLE.
    • 面倒くさがるの良くないよね。sqrt(n)回で切られるようにしてsubmit.
  • Runtime Error.
    • あれ・・・？
  • 適当に大きい値入れてみたら撃墜された。
  • ようやくAccepted.

Problem E: EnimEN

  • 実は普通のNimと同じになったりしないかな？
  • うーん。ゲーム理論はやっぱり苦手だ・・・。
  • ...あ、石の数2個以上の山があれば先手と後手入れ替えられる？
    • UVaとか蟻本にあった Euclid Game によく似てる気がする。
  • 石1個の山しかない場合は自明に定まる。
  • 2個以上の山は、先手が1個残して取れば全部消せる。
    • 石1個の山だけを考えて後手必勝なら、先手は最後の2個以上の山を一度に消せばよい。
      • 超絶先手有利・・・！
  • 書いた。submit. Accepted.

Problem G: Genius MJ

  • xyでソートするだけ。簡単。
  • complex<int>を使うと90度回転が簡単だった。
  • Accepted.

Problem C: Calculus Simplified

  • O(N!) にしか見えないけど、N の上限が書いてない・・・。
  • ...あれ？
    • どう見てもこの式って簡略化すると (x+x+...+x) - (x+x+...+x) の形に落ちるよね。
      • greedyに割り当ててくだけだ。O(N) で大丈夫。
  • 構文解析書いた。submit.
  • 運良く一発で Accepted.
  • 疲れてきたのでこの辺でコーヒーを買いにいったりとか。
    • 適当に選んだ缶コーヒーが人口甘味料入りだったのでちょっとしょんぼり。

Problem F: Fabulous DAGy

  • ややこしい問題だ・・・。
  • DAGに追加された辺がどれだったかを仮定してループを探す。
    • u - v の辺が追加されたとしたなら、それを除いたグラフに v - (全ノード) - u のパスがないと最大サイクルにならない。
      • DAGなので、DPでもすれば O(V+E) ぐらいで探せるよね。
        • って、これだと O(E2) だ。どうしよう。
  • O(VE) ぐらいならギリギリ間に合うと信じてみる。
    • v - (全ノード) - u のパスをもっと速く探したい。
      • ...
      • ...できないなぁ。
    • もしかして、追加された辺の候補を減らすほうが簡単？
      • 追加されたのは 1 本なのだから、何でも良いから閉路を 1 つ持ってきて、それに含まれる辺だけ調べればいい気がする。
        • これで候補が O(V) 個に減る。
        • 閉路の検出は・・・ V 回DFSしても O(VE) なので大丈夫だよね。
  • 集中力が切れたので、1時間ぐらいかけてだらだらと実装する。書けた。
    • DPとかしなくても、トポロジカルソートすれば簡単に見つかるよね。
      • どちらにしても閉路がないことは確認しなければいけないし。
  • submit. TLE.
  • あ、辺の候補はもっと速く見つけられそう。
    • DFSをかけて閉路が見つからなかったら、そのとき辿ったノードは絶対閉路に含まれない・・・よね？
  • submit. TLE.
  • うーん。致命的に遅くはないはずだけどなぁ。
    • 手元で最大ケースを100回回す。4秒。ジャッジデータは40ケース。ギリギリだなぁ。
    • それにしても最大ケースの入力ファイルでかいな。
      • scanfも捨てて、自分でもっと速い入力を書いたほうが良いのかも。
  • とはいえ残り3分なのであきらめた。
  • 5完で14位。
    • うーん。こんなものかな。