AC(12/3):ば～ちゃるこんてすと？にでました。
こんばんは。今日ぶんのアドカレ書いてないことを思い出し(23:22)急いで書いています。書き上げることに注力するので何の面白みもない記事になる点はご容赦ください。そもそも間に合うか怪しい。追記(24:45) 間に合いませんでしたがこれを12/3ぶんとします。
ついさっき(23:00)まで競プロのVirtual Contest(過去問を利用した仮想コンテスト)に出てました。こうして仮想コン(通称ばちゃ)に出るのは初めてだったのでボコボコにされるんじゃないかとビビりつつも出題範囲が300点だらけでちょうどよかったのでありがたく参戦することに。
コンテスト開始(23:00)
開始時刻になると待機画面から順位表に遷移。zaki_johoとかいう名前を見て震える。彼は先日東京で行われたマラソン大会で賞金を得たすごい計算機ヤクザです。僕に競プロを勧めてくれた張本人であり、よく競プロ関連の知見もくれるので頭があがりませんが、同時にハラスメントもよく受けます。仲良しです。
他のメンツも計算機ヤクザがさらに2名となっており完全に四面楚歌コースとなっていました*1。
とにかく虚無らないようにお祈りしながら問題を見ていきます。
前半戦
まずは全部の問題をさらーっと読む。
- A - 正方形のチップ２:最近の企業コンで似たようなのを見たし解けそう。
-
C - Ordinary Beauty:O(1)やん何とかなりそう。
-
B - PackDrop:長い。。後回し。
-
B - ニコニコレベル:文字列。よく見るC問題という感じ。
-
B - 2525文字列分解:↑と同じ。制約がO(|s|^2)に耐えてるぶん逆に不穏。
よっしゃやるかと正方形のチップをやろうとします。先述の通り企業コンで類問を見たことあったのでその方針で何とかならないか考えますがしばらくして全然違うやんけとなり一度解散します。Ordinary Beautyへ移動(21:10)。
O(1)の数学っぽいので睨めばすぐ解けると思って睨むもすぐに解けない。とりあえず(m-1)コの隣接が一様なので美しさの期待値は個々の隣接の美しさの期待値の和でよさそうだ*2というとこまで考え、d=0の時は1/nでOKだとなったけどd!=0で変だったので泥沼にならないように一時撤退。ニコニコレベルへ移動(21:20)。
制約からO(|T|)くらいでなんとかしたい。サンプルから"25"はOKで"52"はダメということなどに気を付けながら愚直に前から見ていくように実装。
- Tを前から調べ'2'か'?'を見つける
- '2'の後に'5'か'?'が来ていなかったら4へ
- '5'の後に'2'か'?'が来ていたらカウンタ++、そうでなければ4へ
- 一度"2525..."で連続することを確認したらもう見る必要がないのでカウンタが途切れたところまで1の探索の先頭をスキップさせてから1へ戻る
こんな感じで思い当たり次第条件や処理を書き加えていった結果ゴミのようなコードが完成しました。動かしてみて、2*("25"の数)だけスキップすると先頭の'?'の可変性に対応できていないことに気が付くので探索の先頭の位置の偶奇で場合分けしてそれぞれで同じ処理をするように変更(ほぼコピペすることで量が2倍に。ゴミコードがさらにゴミとなる)。
まぁ理屈は合ってるだろうし通るっしょと投げてAC(21:34)。
後半戦
Ordinary Beautyに戻りしばらくしてd!=0の場合の式のガバに気が付きます(なぜかこっちの場合だけ数列の範囲を0~nにしてた)。AC(21:49)。
ここから虚無が始まる。
ニコニコレベルが通った喜びから正方形のチップではなく2525文字列分解に進んだものの、この選択が明暗を分けることになりました(実際はどうかは知りません)。
サンプルを睨んで
- '2'と'5'の数が等しくないとダメ
- 前から見て'2'のストックがない状態で'5'をツモるとダメ
ということが分かったのでとりあえずそれだけ書きます(22:10)。
それから例外ケースでないものについて考えると、
- 2のストックがある状態で過剰に2をツモると分解数が増えるのではないか
- 2のストックがありかつ5を連続でツモる場合も分解数が増えるのではないか
という考察から、例外でない場合はmax('2'の最大連続数, '5'の最大連続数)が分解数の最小値だろうと見当をつけます。サンプルもそうだし！！！
ということで実装。O(|s|^2)でも間に合うので最大連続数も愚直に数える。動かしてみるとサンプルと適当に考えた自前サンプルについて正解してくれてニッコリ。これでどうや俺が3完や、見てるか計算機ヤクザ～～～？？？？つって提出。
は？(22:55)
1つめのWAは2の連続数を見てなかったので2個めのやつで通ると思い連投したけど通らず。何でつってたら終了時刻の23:00が来ていました。
スタンディング見てなかったけど終わってみたら他の2人と全然違うの解いてて笑っちゃった。正方形チップやるべきだったっぽい。
とにかくこうしてペナルティ10分*2で実質最下位になってコンテストは終了。何がダメだったんでしょうね。
あとOrdinary Beautyは数学ヤクザのmdは絶対解くだろうなと思ってたけど解いてなくて不思議がってたんだけど真相はこうでした。
やっぱdrinking_codingはだめですね
— Md (@Md19970824) December 3, 2018
なるほど～つって笑ってた。おつかれさまでした。最後に、コンテスト立ててくれたemonosukeありがとう。
感想
ちょうどいい難易度で楽しかったです。またバチャやりたいけど今日参加してたメンツはわりとshojinで過去問埋めてるからメイツになりえなさそうで悲しい。
さて、、明日は連続体力学のレポート提出日と待ちに待ったフランス語再再再再履の中間試験2回目が待っているので楽しみで夜も眠れません。
それでは今日はここまで。また明日。明日は虚無そうだなぁ。
