ACM/ICPC Domestic Contest 2010

ICPC

自分に出来る最大のパフォーマンスを発揮したのだろうとは思うけれど、それでも悔しいものは悔しいのです。

Before Contest

  • ぽつぽつと雨が降る程度の天気。
    • ここ5年、国内予選の日には雨が降ってます。
  • いつもは簡単な問題を解いてウォーミングアップするのですが、今年はスルー。
    • ビジュアライザをちょっといじったりしてました。
    • 毎年、ウォームアップの成績と本番の成績は反比例する傾向にあるので、ちょっと怖くなったというのもあったりなかったり。
      • 私が寝坊したせいというのもあったりなかったり。
  • 模擬予選と同じ方針で行こう、と確認してコンテスト開始。

Problem A: 角角画伯，かく悩みき

  • 印刷した問題文を@romanchuに届けるときにちょっと読んで、「いつもより文体柔らかいなぁ、変わったなぁ」とか思ったり。
  • ちょっと嵌ってたみたいだけど、すぐにCorrect.

Problem C: ポロック予想

  • 読んだ。
    • 典型的なコイン両替問題にしか見えない。
      • 模擬予選の C を解いたとき「本番はこんなに簡単なはずがないよなぁ」と思ったのですが、まさかもっと簡単になるとは。
  • A の裏で B を読んだ @iakasT と会議。
    • どう見ても C の方が簡単そうだ。こっち先に書いていいよね。
  • A が通ったので書き始める。
  • 書いた。滅茶苦茶な値出てきた。
    • って、最小枚数じゃなくて表し方の総数を求めてた！ばか！
  • 一瞬で直した。sample出てきた。
  • Correct.

Problem B: 迷図と命ず

  • C 解いてる間に紙の上に擬似コード書いてもらってた甲斐あって、@iakasTがあっという間にCorrect.

Problem D: ぐらぐら

  • 面倒臭いけど書くだけらしい。@romanchuに頑張ってもらうことにした。

Problem E: 最強の呪文

  • 文字列連結と辞書順最小の組み合わせって何か危険な臭いがする。
    • そう簡単に Bellman-Ford の負閉路検出には持ち込めないような気がするんだけど...。
  • なんとなく writer はあの人なんだろうなとか思ったりする。
    • 相変わらずいい問題作るなぁ。解ける気がしない...。
  • ...
  • ...この嫌な気持ちをはっきりと言葉に表してみたい。
    • ...
    • ノード n を除く全てのノードについて、そこをゴールとしたときの解が分かったとしても、それを使ってノード n の解を求めることが出来ない！
      • 例えば、(0 -> 1, "abc"), (0 -> 1, "abca"), (1 -> 2, "d") という3本の辺があったとする。
      • ノード 1 で終わる最適解は "abca" ではなく "abc"。
      • にもかかわらずノード 2 で終わる最適解は "abca" + "d" になっている！
      • つまり、dp[n] := n で終わる最小の文字列 を求める解法は不可能！
    • じゃあどうしよう。
      • とりあえず、dp[n][l] := n で終わる長さ l の最小の文字列 みたいなことは出来るはずだ。
    • あとは、無限に長い文字列が作れる場合を検出すればOK.
      • とても長い文字列が作れたら、きっと無限に長く出来るに違いない。
    • スーパー嘘仮定タイム！！！
      • 辞書順最初の文字列を作るとき、同じ辺を2回以上通らない！
        • 全ての辺の文字列長の総和 を越える辞書順最初の文字列が見つかったら、無限に長く出来る！
      • すると dp[40][400*6+いくつか] でどうにか間に合う！
    • ...で、この嘘仮定って本当？
      • 普段なら信じて突っ込むところだけど、よりにもよって国内予選でそれはしたくない。
      • どうしよう...。
    • ...
    • あ。
    • 同じ辺を2回通るということは (A)(S)(B)(S)(C) 見たいな文字列が出来るということで。
      • (S)(B) < (S)(C) ならば、 (A)(S)(B)(S)(B)(S)(C), (A)(S)(B)(S)(B)(S)(B)(S)(C), ... って無限に長く出来るし、
      • (S)(B) >= (S)(C) ならば、 (S)(B) を取り除いて (A)(S)(C) としたほうが小さい。
    • どっちにしろ解にならない！
      • 嘘は本当になりました！やった！
  • @romanchu のヘルプに入れるように D の問題文を読みつつ、ペアプロしながら@iakasTに実装してもらう。
  • sample出てきた！submit!
  • Wrong Answer...
  • ...
  • どこがおかしいんだろう。アルゴリズムは間違ってないはずだ...。
    • dp[n][(全ての辺の文字列長の総和) + 100] を計算してるのだけど、怪しいのはこの適当に決め打った 100 ぐらいしか...。
    • ...マズい！
      • 40ノードを全力で使えば、長さ240ぐらいの閉路が作れてしまう！
  • +400 ぐらいにしてジャッジデータ食わせてみる。1ケースだけ答え変わった！
    • ついでに +1000 とかも試してみる。もう変わらない。
  • 今度こそ行けるはずだ！submit!
  • Correct!

Problem D: ぐらぐら

  • トリプロ開始。
  • ほとんどのケースは出てきたけど、重心の計算がおかしくて1ケースだけ合わないらしい。
    • もしかして重心の定義を勘違いしているのでは？と思って、別の解釈で重心を手計算してみる。
    • 計算し終わる前に、@iakasTが今の解釈でも正しく出るはずと結論付けた。
      • そうこうしているうちにバグも見つかって潰れた。
  • 待望のCorrect!
  • @romanchuに強実装を投げておくと、そのうちきっちり解いてくれるのでチームメイトとしては気が楽です。

Problem F: 古い記憶

  • あと45分ぐらい残ってる。諦めるには早すぎるけど、全然思い浮かばない...。
    • さすがに全探索は間に合わないだろう。編集距離 d 以下を全列挙ぐらいならできそうだけど。
  • 最低 13 文字という条件が露骨に怪しい。
    • 「最小の入力サイズにちゃんと意味がある問題って美しいよね」みたいな事を偉い人が仰ってたのを思い出した。
      • やっぱり writer の顔が透けて見える。
    • 40 (テキスト長) - 13 = 27.
    • 使用できる文字も大文字アルファベットと . の 27種。
    • よく見たら問題文の冒頭も 西暦4'27'2年。
    • これらは何らかの複線なのでは！？
  • とか言ったところで解法は見えない...。
  • ...
  • あれ、よく見たら「全てのピースは同じ長さである」とか書いてある！
    • これはすっごく使えそうな気がするというか解法見えた？
    • 整理しつつチームメイトに説明してみよう。
  • 編集距離 d 以下の文字列を全列挙する。
    • これは愚直にやる。
      • 挿入・削除・置換がそれぞれ (40*27), (40), (40*27) 通りぐらいあるので、1回でざっと 2,400 分岐。
        • d <= 2 なのでおよそ 2,4002個。全列挙できなくも無い。
  • 全列挙したそれぞれの文字列について、作成可能かどうか線形時間で判定する。
    • それにはローリングハッシュを使う。というか Rabin-Karp.
      • あらかじめ、全てのピースのハッシュ値を求めておく。
      • ローリングハッシュを使うと、その文字列のある長さの全ての substring のハッシュ値を線形時間で求められる。
        • つまり、いずれかのピースとマッチした位置を線形時間で全て求められる。
    • マッチした位置と各ピースの長さが分かってるのだから、ピースで覆えるかの判定も簡単に出来る。
  • 残り時間は35分。書けるか？いや書くしかない！
  • がりがりがりがり。
    • 全列挙のところ、string使わずにchar配列で丁寧にやらないと遅くなりそうだけど、そんな悠長なことを言ってる時間は無い。
  • 書けた。ハッシュの計算がちょっと違う。覆えるかの判定もちょっと怪しい。直した。
  • まだ作られない文字列がある。
    • sample2つ目の ".ABRACADABRA.ABRACADABRA." が出てこない。
      • 覆えるか判定するルーチンに強引に放り込む。あれ、出来てる？
  • @romanchu「全列挙するときの枝刈りで刈りすぎてない？」
    • コメントアウトしてみた。sampleの上3ケース出てきた！
      • 4ケース目はしばらくお時間をいただいております。
  • しかし時計はもう 19:32.
    • リロードしてみる。終わってた...。

Result

  • 5AC, 20720sec. 5th place.
    • 合宿には行けそう。目標は達成しました。
  • F が間に合わなかったのが何とも悔しい。
    • @iakasT が後で試したところによると、ジャッジ入力は14分ぐらいで出てきたらしい。
      • 定数倍の高速化の余地があるコードだったので、頑張れば半分ぐらいにはなるかも。
    • もっと時間があれば...とは思うのだけど、誰も無駄な行動を取ってはいなかった。
      • つまりは実力が足りないのでしょうなぁ。

Timestamp

  • 出力ファイルのタイムスタンプ (≒ 正解した時刻) の晒し上げ。 



 bash-3.2$ ls -la {A,B,C,D,E}.out

 -rw-r--r-- 1 (username) (groupname)  250 Jul  2 16:46 A.out

 -rw-r--r-- 1 (username) (groupname)  254 Jul  2 17:05 B.out

 -rw-r--r-- 1 (username) (groupname)  820 Jul  2 16:54 C.out

 -rw-r--r-- 1 (username) (groupname)  396 Jul  2 18:40 D.out

 -rw-r--r-- 1 (username) (groupname) 4243 Jul  2 18:27 E.out

  • A, C, B, E, D の順番。
    • アルファベット無視しまくりだけど、この順番で解いたチームは多いのでは。

Word Count



bash-3.2$ wc *.cpp

   33   120   650 A.cpp

   74   150  1406 B.cpp

   34    61   577 C.cpp

  247   683  4516 D.cpp

   58   118  1143 E.cpp

  123   231  2156 F.cpp

  569  1363 10448 total

  • Dが長い。よく通したなぁ。
  • @romanchu, @iakasT, @matyaa の実装量が綺麗に 2:1:1 となっていてバランスがよろしい。
  • G は72時間ぐらいあれば通せてたかも。
  • 審判団の皆さん、お疲れ様でした。ありがとうございました。