怠惰の累積和

技術/競プロ/怪文書/虚無

PCK2019 予選参加記

はじめに

 　2019/9/14 13:30(JST)から行われたPCK2019に僕とBwambocos(@babcs2035)の2人でチーム「Rate-Mikan」で出場しました。結果から言うと、8完2WAでした。以下に競技開始の少し前からの流れを大まかに書いていきます。尚、記憶が曖昧な為、もしかしたら時系列がぶっ壊れているかもしれないです。なので簡単に矛盾点を見つけられるかもしれないです。あとこれはいつもの事なんですが、脳死状態で文章を書いているので誤植がINF個ありそう。あとあと、Bwambocosっていちいち書いているのが面倒なのでBwamと略します。

 

競技開始前

　当日は文化祭だったが、競技開始1時間くらい前から部活の展示担当をサボり、蟻本を朗読したり、PCKの過去問を鑑賞したり予選下馬評の会場を見て「予想でもKMB86強いな～」と思うなどしていた。競技開始40分くらい前になり、コンピューター部の展示部屋から戦いの教室へプリンターとかPCとか考察用紙とか必要なものを運び込んだ。10分くらい学校のWifiに繋がらないトラブルがあり、キレた(Wifiを管轄している学校の部署を呼んで直してもらった)。

 

競技開始

　競技が開始されたので、前日に立てた作戦通りに、まずはDとEを印刷して、Bwamに渡す。僕はその後Aを見る。音読用の問題背景の文章を読んでいたら10秒くらい過ぎました。ただの加算なので書いて(PCKでは同完数内ではまずWAの数でソートされるので一応)テストケースを全部試して提出した。開始したばかりでジャッジが詰まっており、中々結果が出ない。まあ合っているだろと思いBを見る。

　場合分けコンテストであることが自明なので書く。書いてる途中で若干頭が無くなりよく分からなった(は?)。書いたので提出。

　Cを見る。えぇ。ただの2冪数の全探索なので書く。書いた。提出。ここでAとBがACな事を知る。しばらくしたらCもACだった(ジャッジが遅すぎる)。まあここまで0WAでよかった。

　BwamがDとEを見終えたのでPCを渡す。その際にFとGを印刷して、僕はFを見る。載っている図がgcdの説明でよく見る図みたいだなあと思った。各正方形の長さはフィボナッチ数列になって増えていっていることは分かるし、横方向と縦方向を分けて考えて良さそうかも。ただ縦横それぞれについて正負で大分規則性が違いそうだなあとなる。

 

えー

 

　なんか詰めきれないのでGを見てみる。lcm必須案件なことが分かる。当然答えの上界は2^N-1になるし、1≦N≦20なのでそこまで大きい数にはならなそうだからこの数からあり得ないケースを引いていって答えを求める方針で行きたい気持ちになる。

　BwamがDとEを提出。どっちも結果がすぐに返ってこない。BwamもFを見る。よく覚えてないけど2人して分からなくなった。4方向に分けて累積取って1足すと境界値になることは分かったりしたが所詮1次元での話なので今回の問題では意味がない。

　DとEはACだったらしい。同率1位。

 

　分からないのでFを飛ばした。G。ソートして順にLCM取っていけばよくない?となる。通す。

　Hを見る。なんか右端左端に寄せるのでよさそうってBwamが言ったけど、駒が追い越しできないことを完全に見落としていた僕がよくわかんないことを言ってしまう。ごめんなさい。確かにあなたの言う通りです。

　HができそうらしいのでIを印刷する。見る。幾何です。しかも3次元。なにこれ。とりあえず1人で考える。太陽と天空の城ツガル(この名前、怒られそう)のz座標が与えられていて、地面はz=0なので、ツガルが地面に作る影の領域は相似を使ってN時間かけると求められそうだなあとなる。

　出来た多角形内の適当な1点を選び、与えられるQ個の点それぞれについてその点と先ほど選んだ点を結ぶ直線と多角形の各辺の線分交差判定をすれば解くことはできそうだけどO(NQ)になり、確実にTLEしてしまう。

　多角形に点が含まれるかどうかの高速な判定ができれば勝てそうとは思ったので蟻本を開くけど無さそう。

　その頃BwamがHを提出する。WA。僕はI、BwamはHを考える。順位表を見ると、Iの提出率及び正解率が異常だった(はず)。魔境なのか?とは思ったけどワンチャンいけるので考える。Bwamが改善したHを提出する。WA。しかしforで探索する範囲を間違えて1つ少ない探索をしている説が浮上し、試しにそのような選択が最適であるケースを作って実験する。答えが異なるので探索範囲を変えて提出。AC。はいプロ。

　Iを2人で見る。Bwamも3次元ヤバいとか言ってた気がする。順位表を見てIを飛ばさない?というような空気になる。

　僕がこのセンスのない絵を描いてIの考察が終了した。

f:id:severrabaen:20190914214423j:plain

　なんか配点が同じだった(気がする)ので一応JとKとLを印刷する。たまに2枚目が白紙で出てくる。なんなのこれ(仕様なんですけどできれば問題PDFに白紙を追加しないでほしかった)。

　Lは問題名を見て来年はダンジョン4という問題が出ることを期待して読むのを止めた(PCKではこの3年連続でダンジョン1、2、3という問題名で問題が出ている)。

　Jを見るとグラフ問にならないかなあとかいう発想が生えた(なんか有効辺張って色々やればできそう)。Bwamも同じことを思ったらしい。ただ、Nは2冪じゃないし色々面倒だなあとなる。

　ここで時計を見ると残り時間が約30分だった。上記の通り現在は7完。順位表を見ると8完チームがまあまあ多いため、これは8完しないとヤバそうという感じになるため、Fを見る。4方向に10^6以下のフィボナッチを分けると1つ当たり高々9つになることが判明したため、シミュレーションできそうとなる。whileで回してひたすらシミュレーションする処理をBwamが書く。僕は横でデバッグ用の諸々を用意していた(ちなみに用意していたこれ、一部ミスっていた(ア(まあ後で割とすぐ気づいた)))。デバッグする。なんか挙動がおかしい。見た感じwhileの条件が間違ってそうと思ったので指摘してみる。違った。書き直す。デバッグ。合ってるっぽい。提出時間切れになるよりは提出した方が良いのは明らかなので提出。

 

 

。

 

。

 

。

 

 

 

AC。

　この時点で残り時間が12分くらいだったので他の問題を通すことは無理だろうと判断し(9がエグいのが割と堪えた)、もう凍結されている順位表を見たりしていた。凍結されている順位表では7完0WAで19位だった。8完になったのでもう少し上になっていてほしい感がある。

 

競技後

　16:30になり、競技が終わった。監督をしていた顧問と若干話したが文化祭での生徒の強制下校時刻が迫っているので話も早々にまたプリンターやPC等を持って民族大移動をした。

　コンピューター部の展示部屋に戻ると順位が実況されていた(去年はホワイトボードには書かれてなかった気がするけど)。尚、636チームになっていますが、本当は701チーム(単純に実況する人が0完が何人いるかを見ていなかったらしいので0完同率が圧縮されているから)。

 　差し入れとして置いてあったお菓子を食べて(某きのこと某たけのこもあったけどたけのこ派なのでたけのこを食べた)、適当に片づけをして、学校を出た。

　夕食を新宿で食べた。当初焼き肉の予定だったけど急遽ロイヤルホストになった。黒×黒ハンバーグというものを食べた。美味しかった。

 

おわり。