milkcoffee Penalty Contest 001 参加記

※※※ネタバレ注意!※※※

milkcoffee さん主催の第一回ペナコンに参加しました.

mojacoder.app

せっかくなので参加記を書きます.
普段とは違って(?)砕けた文体で書いたのでご了承ください.
なお,6/9 (水) 21:30 頃から書き始めているので記憶は新しいです.

18:00 〜 18:30 頃

リモートワークを終えて夕飯を食べながら YouTube を適当に観た.ショウヘイオオタニがまたホームランを打ったらしい.

順位表も時々チェックしていた.しばらくしても 1 問目を数人しか提出していなくて,問題が難しいのか慎重になっているのかどちらかだろうな,などと考えていた.

準備

ローカルに作業フォルダを準備.ランダムテスト用のファイル群もコピー配置して準備万端(結局使わなかったけど…). このとき既に 3 完している人がいたが 3 問目は誰も解いていなかった気がする.

作戦

サンプルケースをローカルに作った上で,自作のテストケースをたくさん作って慎重にやる作戦にした. できれば愚直コードを書いてランダムテストをしたかったけど,愚直を書くタイプの問題ではなかったので, 実際は考察しながら丁寧に丁寧にテストケースを作りまくった. 問題毎に作ったテストケースの数は下記の通り(サンプルケースを除く).

  • 1 問目:12 個
  • 2 問目:18 個
  • 3 問目:14 個
  • 4 問目:18 個

また,提出は 4 問まとめてにしようとしていた. というのも,ペナ数が抑えられれば 30 時間以下の差は気にしなくていいと思ったので. 他の人の提出状況からペナ率の情報も分かるので,最後の最後まで確認してから tourist 出しするのが理に適っていると思った.

1 問目:Under M

 N^{N} の下  M 桁ですか,なるほどこれは難しい,普通の 100 点ではないですね.

Python が楽そうだなと思ったけど,多倍長整数が使えるなら C++ でもいいかなと思い, MojaCoder で boost が使えるかどうかをサンプル問題(A + B)でチェック(許される範囲ですよね…たぶん). 使えたので,多倍長整数を使うことにした.

愚直に  N^{N}多倍長整数で計算して,文字列型に変換して,下  M 桁を解析するだけ( N \leq 100 なのでこれで十分). 罠は何だろうと考えて,とりあえずサンプル 2 のように  M N^{N} の桁数を超えるケースがあった. 他は思い付かないのでテストケースを色々作ってみる. 0 が続くケースとかはちょっと怖いけど, 文字列型に変換したあとに長さが取得できるので解析も対処も割と簡単で他に罠は無さそう. 多倍長整数を使うことでかなり楽が出来た気がする(想定解は何だろう).

2 問目:RGB walking

右と下だけでなく上にも左にも移動できるので自由度が高くて難しそう,というのが第一印象.

まずは Bishop よろしく, \mathrm{min}(H, W) = 1 のケースを考えてみる. まっすぐ移動するしかないので,これは  \mathrm{mod} \, 3 で考えれば簡単. それ以外の法則はすぐ見えないので,とりあえず  (2, 2) 〜 (5, 5) を全て書いてみたら  (2, 2) 以外は全て Yes にできた.

直感的にも,盤面が広ければ調整が効くから Yes にするのは簡単そう. コーナーケースを除いてすべて Yes では? 証明が難しい… 色々お絵かきしていて「 (h, w) の道順を拡張して  (h, w+1) の道順が作れる」という傾向に気がつく. これを基に改めてお絵かきしてみたが,やはり拡張する方法で上手く Yes が作れそうだった.

ここで, (2, x) のケースの盤面が狭くて自信がなかったので  (2, 3) 〜 (2, 7) までお絵かきして問題ないことを確認. これでヨシ!

3 問目:Slice Cube

パ研合宿のあの問題を思い出した(解けてない). めちゃくちゃ苦手なタイプの問題で,最初は解ける自信がなかった.

とりあえずお絵かき.うん,全然わからない.
こういう時は調査でしょう.「立方体 切断面」でググって神サイトを見つける.

www.geogebra.org

みんなこれ使ってそうだな〜などと考えつつ,しばらく遊んでみる.割と楽しい. その結果,六角形は作れなさそうで,三角形・四角形・五角形が登場することがわかった.3 択問題ですね.

適当に  L = 10 で固定して少し自信なさげにテストケースを作る. 三角形の出現ケースに特徴があることに気付く.これは最初に場合分けできそう. 点を動かして確認すると,三角形の出現条件の中で  X = Y = Z = 0 \, \mathrm{or} \, L のときに四角形になることに気がつく.危ね〜.

残りは四角形か五角形.ここからが難しかった.他のサイトも色々読んでみたがよくわからない. しばらくして,「辺 DH を z 軸に重ねたときに,3 点を通る平面と z 軸の交点の z 座標で判別できそう」ということに気が付いた. 点を動かしてみるとこの交点の位置によって四角形と五角形が切り替わるように見えたので.

ということで平面の式の計算方法を調べる(すっかり忘れているので…). 色々あったが,今回は 3 点の座標が分かりやすいので  ax + by + c = z とおいて代入して係数を求めることにした. すんなりキャンセルして係数が求まる.コードを書いてみると WA が大量に出る.  a = \frac{Y - Z}{L} をそのまま計算して使っていたので切り捨てになっていた… うわー.

今知りたいのは  (x, y) = (0, 0) としたときの  z 座標の値なので, a, b を経由せず  c を直接求めるようにしたら,  c = X - Y + Z と綺麗に求まってビックリした.これは面白い. あとはこれが  0 \leq c \leq L なら四角形で外側なら五角形になるはず.

あれ,まだ WA が出る.あー, X = 0 とか  X = L のときに四角形になってやがる. このコーナーケースも潰して実装したところ,手元のテストケースを全てパス. 手応えがあったのでこれにて完了.丁寧に作ったテストケースに救われました.

4 問目:Sqrt Equality

お前,見たことあるぞ.

Sqrt Inequality よろしく,移項と二乗計算を駆使してルートを消した状態で等号判定すればいい. これが 4 問目だなんて,案外楽勝だな(フラグ).

順位表で意外にペナが出ているが,このときはピンと来ていなかった.

値が大きいので,再び多倍長整数を使う.丁寧に式変形をしていく. 途中で片側がルートのみになったので,反対側が負数になっていないかチェックを入れる. これは Sqrt Inequality と全く同じ.特に難しいところはない.

 \sqrt{513 \times 3^{2}} + \sqrt{513 \times 28^{2}} = \sqrt{513 \times 15^{2}} + \sqrt{513 \times 16^{2}} などの テストケースもしっかり作って,全てパスした.やはり,あっさり終わってしまった.

tourist 出し・最後の戦い

何せ初めてだったのでめちゃくちゃ緊張したが,tourist 出しを決行.この時点でノーペナ全完が二人いた.

後ろから出していったが,いきなり 4 問目が WA になるのが見えてつい笑ってしまった. そのあとも WA が続くのか? と思いきや,1 〜 3 問目は耐えてくれて AC.3 問目がノーペナは嬉しかった.

さて,4 問目と最後の戦い.ミスの原因が分からない.式変形の過程を眺める. 二乗計算は 2 回やっていて,2 回目は片側がルートのみになるので負数チェックをしているが, 1 回目は  2 (\sqrt{AB} - \sqrt{CD}) = (C + D) - (A + B) となっていて,気にせずそのまま二乗していた.

…あ〜そういうことかあ… 反例は作れなかったけど,1 回目の二乗計算でも符号確認が必要そうということに気付いた. 他に原因は思い付かなかったので,確信度 70 % くらいでこれが原因だと思い,丁寧にチェックを追加実装.

順位的には 1 ペナに抑えられると結構良さそうな結果になりそうだったので, ここでもかなり緊張したが,エイヤで投げたところ AC を獲得. 20:40 時点で 1 ペナ暫定 3 位につけた.中々上手くやったのではないだろうか.

体感 diff

体感 diff を書きます.3 問目がめちゃくちゃ難しかったです.4 問目はコーナーケースが難しくて diff が上がっている感覚です.
ところで,全て緑以下想定ってマジですか… 3 問目は人によっては考察しやすいのかな? 自分にとってはかなり辛かった.

  1. 茶 600〜800
  2. 緑 1000〜1200
  3. 青 1800〜2000
  4. 水 1200〜1400

まとめ

面白いコンテストをありがとうございました.早く解説とテストケースが見たいです. 個人的には 2 問目 と 4 問目 が好きで,3 問目はよくこの問題作れるなあ〜と感心しました.

一通り書き終わって誤字脱字等のチェックを済ませ,現在,22:50 頃なので 1 時間 20 分ほど使ってこの参加記は作成されました(もっと早く書き上げたかったけどこんなもんか…).

追記

終結果は 4 位 (1 WA) でした.終了 30 分前くらいに 3 人目のノーペナ全完者が出たようで,残念ながら 3 位から陥落しました.とはいえ,自分は 1 ペナを出していますし,調べたところノーペナ全完者は 3 人とも暖色コーダーだったので納得の結果ではあります.そもそもこんな上位になるとは思っていなかったので良い記念になって嬉しいです.

以上