PCK(パソコン甲子園)2012予選

今年は出れて良かった~!!!去年は台風の影響でクソつまらない再予選受けたので。

P040 Ryu☆年(たつどし)で,id:refiute君と出ました。

相方の参加記: eristical

結果

まず結果から言うと、1~9を解いて9完/10問でした。たぶん80点/100点?

WAペナルティ数は2。最終提出は175分/180分なので激遅。

WA出した問題は問6のマヤと問7のすごろく。


コンテスト中の流れ

いつものようにアホみたいに細かく書くけど、時間については確認できるものが何一つないしソースも残ってないので曖昧。

もしかしたら時間軸バグりまくりかもしれない。雰囲気みたいな感じで。

[00:00]【問1】10問解いたら何点取れる?読む。
  • !?ってなる。複数データセットではないかとかいろいろ読む。
  • とりあえず問題印刷する。refiute君に任せる。
  • 提出するとき手が震える。何度も確認する。
[00:01] 【問1】Accepted.
  • とりあえず4点確保。
[00:01] 【問2】乗車券読む。
  • refiute君がただのぬるい場合わけということを教えてくれる。
  • ほんまか?みたいな確認をしまくる。
  • とりあえず8通り手元で全部試してあってるっぽいので提出。
[00:04] 【問2】Accepted.
  • ナイスrefiute!!
  • PCK予選ってこんなに簡単だったっけ・・・?読みやすさに問題作成委員の努力が感じられる。難読化好きな先生とかいそうだけど、リストラされたのか封印されたのか。
[00:04] 【問4】すべての数は6174に通ず読む。
  • refiute君が問4は今年のICPC予選のパロやでみたいな感じのこと言ってくれたので。
  • 書く。読解全くしてなくて、頭が回ってないけどコードだけが出来上がる。探す高々1万回(実際にはもっと小さくて余裕)なので、適当に実装。バグらない。サンプル一致。
[00:08] 【問4】Accepted.
  • refiuteには助けられっぱなしだなあ。
  • おっstandings見たら一位じゃん激アツ。ガンバロ。
[00:10] 【問3】家庭菜園読む。
  • refiute君が読解すましておいてくれた。等比数列らしい。あとアルゴリズムも教えてくれた。
  • とりあえず1つどれ取り除くか決めて等比数列になっているかを判定。解が複数あるとかありえなさそうだけど怖いのでmax取った。
  • サンプル合わない。なんでや!悩む。サンプル確認してみたら等差数列だった。
  • コードを等差数列っぽくして提出。
[00:20] 【問3】Accepted.
  • 順調である。ん?開成が【問5】パイプつなぎ職人の給料を通してる。これ難しそうなんだが~~~???
  • refiuteと貪欲っぽい(refiuteの主張)だとかDP(僕の主張)だとか議論する。
  • refiuteがマヤ暦チョーヤバイの実装するらしい。僕は問5詰める。時間だけが過ぎていく。
[00:40] 悲しみphase
  • 分からん。読解ミスってんね???→ミスってた。
  • アカン。サンプル読めば一瞬で間違い気づけたのに。これ総和取るだけや!!!
  • 最初は全部結合していると考えて、何個取り除くか決めるときに、ジョイントで小さいもの順から取り除いていけば良いので、それをO(N)通り試す。JOI2011-2012予選問3(ピザのトッピング)みたいな改善をすることによって最大値の取得がO(N)で出来る。
  • 提出。
[00:45] 【問5】Accepted.
  • よっしゃ~。安心感みたいなの感じる。
  • 僕がマヤやろうとしたが手が止まったので、とりあえずrefiuteにすごろくすすめられる。tozanのところも解いてるし
[00:50] 【問7】すごろくを作るを読む。
  • ウムムム。適当に全探索しよう。再帰だとめんどいな。
  • サンプル合わない。なんでやなんでや時間食う。
  • なんか問題文の全てを勘違いしていたことに気づく(Maxの意味とかNの意味とか)
  • これ問題文全く読んでないレベルでひどすぎ。
[01:00] 暫定書き上げ
  • バグらないのが出来たけど、サンプル合わない。
  • なんかrefiuteが問10は『凸包!』ライブラリ写させてと言っている。凸包ではなさそうという議論をする。
  • パソコン占領している。とりあえず引き渡す。紙面で詰める。
  • 問10は凸包よりも「制約的に2^16で餌置く位置を固定して線分を延長した交点とかから実際に確かめる方が確実そう」という話をする。それでもまあとりあえず凸包書いている。
[01:15] コーディング再開
  • ああこれやばそうだった。アルゴリズム変えよう。
  • 「全てのマスについてそこからゴールに可達であるかどうか判定した配列を用意して、その結果に基づいて探索する。」という方針でいく。
  • サンプル合った。提出。
[01:25] 【問7】WA.
  • ファ!?分からん。
  • 通してる人多い問8やろう。その間にソース印刷して、読んでもらおう。
[01:25]【問8】ビートパネルを読む。
  • ビットが見える。あっ制約BitDPぽい。refiuteがBitDPするまでもなくやるだけと言う。
  • とりあえず各タイミング毎に最適なマッチ数を足していくようにする。
  • サンプルの3番目が合わず絶望。3分くらい悩んで『一度光ったボタンはそのボタンが押されるまで光は消えることはありません』に気づく。やっぱりBitDPじゃないか(憤怒)
  • とりあえず適当に書く。サンプル合った。提出。
[01:40]【問8】Accepted
  • 激アツ。ナイスで~す♂。
  • とりあえず問7を紙デバッグしてもらう。初期化ミス説浮上。
  • 訂正して投げてみる。
[01:45]【問7】Accepted.
[01:45]【問6】マヤの大予言読む。
  • 経過日数計算ライブラリが手元にある。なので机上で詰める。詰めた(つもりな)ので交代。
[01:55]【問6】コーディング開始
  • マヤ暦か西暦かの判定は"."の数数えるだけで良い。
  • とりあえず西暦→マヤ暦は、経過日数計算ライブラリ適用した後、187万2000日でMODとって一瞬。
  • マヤ暦→西暦は、マヤ暦は高々187万2000日なので普通に2012年12月21日からループ。
  • うへぇ、てこずった。とりあえずサンプル一致したので提出。
[02:10]【問6】WA.
  • ええええ!?さすがにこのサンプル通ってWAするってやばくね?オーバーフロー?→サンプルに最大ケースがある・・・。
  • 悩む。refiute君にソース見てもらう。僕「refiuteが言ってた大の月・小の月間違ってるんじゃねーの????」→違う
  • ライブラリが1byte間違っていることを指摘される!!!なぜ気づく!なぜサンプル通るんだ。ごめんrefiute。
  • そこ直して提出。
[02:25]【問6】Accepted.
  • 再びハイタッチ。でかしたぞrefiute!!!
  • standings見たらtozanたちが問9通してる。WA数は2回でタイ。これは負けたなあと思う。
  • 問9さっきからチラチラ見てたけど簡単そうだったので手を出す。余った時間で問10実装すればいいな~とか思う。
[02:25]【問9】有限体電卓読む。
  • あっ、やっぱり構文解析だ。しかもただの四則演算だ。楽そう。20分もあれば通るだろ(舐め)
[02:40] 暫定的に書き上げ
  • 再帰がバグバグしている・・・。デバッグ辛いゾ~これ。
  • refiuteが問10やりたそうにしているが、これを意地でも通したいので僕はパソコンから離れない。
[02:50] やっぱりバグバグしてる
  • 構文解析うまくいってそうなのになんでスタックオーバーフローっぽい挙動してるんですかね・・・?
  • 悩む。まさかの二分累乗法が間違っていたことに気づく。pow(a*a%P,b/2)で呼び出すところをpow(a*a%P,b)とかしていた。
  • うわひどすぎ・・・。失意の中提出。
[02:55] 【問9】Accepted.
  • ハイタッチする間もなく、問10をrefiute君がまさかの説明した解法紙コーディングしていたので打ち込めと言う。
  • 僕は打ち込む作業に徹する。タイピング速度間に合わない。
[02:59.30] 脱力Phase
  • 諦めて、コンパイルエラーするソース提出したりした。
[03:00] コンテスト終了

感想

  • 日数計算はライブラリ持ち込んでて良かったなと思った。
  • FirstAcceptanceもらってたらしく嬉しい。
  • drafear&tacosufestivalチームが半端ない。7完していて激アツ。drafearの謎の解答能力マジで羨ましい。
  • (たぶん)2位はちょっと予想してなかったのでびっくり。幾何解けなかったの残念。
  • 僕はこういうセット好きですよ。問3曖昧だけどPCKだから曖昧で当然だろとか思って解いた。
  • 全体的に問題文が読みやすかった。が、僕はほとんどろくに問題文読んでません。
  • 去年と比べてrefiuteととても議論できたし、ほとんどコーディングは僕がしたにしろ、読解力低い僕に簡潔に問題説明してくれたり感謝しっぱなしだった。他人のソースのデバッグ力も高い。本選、彼と勝ちに行きたい。