Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

UTPC 2013 参加記

さたしゅんくん とUTPC 2013 に, チーム†背徳ト絶望ノ番人†で参加し, 16 位を収めました. ということで時系列でコンテストを振り返ってみます. コードは後で載せます. 進捗ダメです.


[-00:42:00] チーム名決め
kagamiz の鶴の一声によりチーム名がアレな感じになる.

[-00:00:15]
kagamiz が背徳と絶望のアカウントを作っていたにも関わらず, さたしゅんくんがユーザーid とpw すら把握していなかったので10 秒で伝える. やったぜ.

[00:00:00] コンテスト開始
kagamiz がA を解き, さたしゅんくんにB を頼む分担.
A を読むと簡単そうで, 穴の数の総和を調べるだけだな! (慢心)と思いコードを提出する.

[00:05:22] A WA
ファ!? スタートからWA で絶望する.
A でWA とかやばい...やばすぎると思って問題を再確認すると, それぞれの文字について穴が等しいかを判定すれば良いという話だった. つらみが溜まる. 書き直して提出.

[00:11:14] A AC
A 問題に10 分かかった上に1 WA とはもう冷えが止まらないが, さたしゅんくんがB をやってくれているのでC を読む. ああこれは直径ごにょごにょするだけですね... 書く.

[00:41:24] C AC
グラフの頂点は0-indexed なのに手が勝手に頂点をデクリメントしてバグに悩まされていたが無事AC. さたしゅんくんがB のlong long まわりで闇を抱えているようなので(A AC からC AC の英田までで3WA だしている) ちょっと話をしたあとにまた実装に戻ってもらう.

[00:44:30] B AC
ちょっと話をして整理するとバグが取れたらしくAC. 解法を話して整理するのは大事だという結論に至る.
ここで次の方針について話し合う. ぼくがD を読んで解く間に, さたしゅんくんに200 点問題で解けそうなものを見つけてもらい実装する作戦に.
ぼくがD を詰めている間, さたしゅんくんがF ができそうとのことだったのでF を頼む.
D, ヒープのサイズが小さいし適当な上界を見積もって大きさを全部試せばいいのではと思う. (が確信をもてない)

[01:28:07] F TLE
ぼくがノロノロD を考察している間にさたしゅんくんがF を書いてくれたが無慈悲なTLE. やばいと思い, 上界が不安だがとりあえず上限を1000 としてD を書いてsubmit.

[01:32:29] D AC
通ったーやった. ここからF とG を平行して考え出す.
n 時間くらい思考phase をはさみ, G の部分点, 二分探索頑張ればいけるのでは?という結論にいたりN 回くらいWA を出す.

...

[04:02:53] G AC
さたしゅんくんと解法を考え, 彼に実装してもらったところ50 -> 200 に. さすがである.
そして一緒にF を考える. マージソートっぽく辺を併合していく & 一度使われなかったものは未来永劫使わない, を実施すればと提案し, またまた実装をお願いする. その間L の部分点を書く.

[04:53:49] L WA(50)
まあ300 は無理なので... 残りの時間でさたしゅんくんがF を実装し終わることを祈る.

[04:56:58] F AC
もっともテンションが上がった瞬間だった. 終了3 分前にAC は格好良すぎた.
残りの時間は1 ページ目に食い込めるといいね~みたいな話をしていた.

  • まとめ-

分担として, 僕が色々片付けている間にさたしゅんくんに考えてもらうという感じになっていたが, うまく機能した気がする.
彼は的確に実装が出きるので, ぼくが"こんな感じにするとよさそう" と言ったことをうまくコーディングできていて, すごくよく連携が取れたのかなあと思う. 一緒に参加できてよかった.

後日自分でもコードを書こうと思います.