Toyota Programming Contest 2023 Spring 決勝 参加記

はじめに

Toyota Programming Contest 2023 Springの決勝に参加させていただきました。 JOI、ICPC意外のオンサイトは初めてでとても楽しかったので記録として残しておきます。

予選A

普段のABCよりARC寄りの重いセットと書かれていて、ARCが苦手な僕は不安でした。

Fで詰まって焦ったんですが、なんとか7完できたので国内51位という結構な成績で予選を通過しました。 普段より面白いセットでした。

予選B

kotamanegiさんやshinchanさんが無事通過するのを見届ける会だったんですが…

ガチカスをやってしまいました。今年はA[BRG]Cに全部出ようと思っていたのに早速折れてしまいました。大変申し訳ございませんでした。

WA_TLE様は優勝したし、kotamanegiさんやshinchanさんも無事通過したのでよかったです。]

↑ちなみに翌日にバチャやったらちゃんと100位以内入ってましたよ。ええ。

決勝まで

とりあえず部内で決勝/決勝イベントに通ってそうな人をSlackに集めました。

規定では北海道・沖縄意外は1泊がデフォルトになっていましたが、イベントは9:00-20:00と長く、関西圏からでは始発・終電に近い電車が必要、またはそれでも不可能という状況になってしまいます。 kotamanegiさんにAtCoderさんに問い合わせをしてもらったところ、困難な場合は前後泊もOKとの回答を頂きました。 結構な金額にはなってしまいましたが僕も2泊分で申請させていただきました。AtCoderさん、トヨタさんには大感謝です。

前日は大した予定もなかったのですが東京に行けることが珍しいので昼頃から観光することにしました。

ICPCのときに遊舎工房に行けなかったという未練があるので秋葉原に行く手も一つでしたが、東京に行くたびに秋葉原に行っているので今回は秋葉原に行かないことにしました。

関西では見れない&&一人で行っても寂しくないを満たす場所を考えた結果、絵画を見に行くことになりました。 国立西洋美術館に行ってみたかったのですが、ちょうど3/17までの間館内整備のため休館とのことだったので国立新美術館に行くことにしました。 「ルーヴル美術館展 愛を描く」という企画展を見ました。興味深いものを見れました。

まだ時間があったので、原宿まで歩いて「原宿レインボー」なる娯楽菓子を食べたり、WA_TLEさんと合流して明治神宮を歩いたりしました。

SCの勉強とかバイトとか他のお出かけとかそんなので最近競プロに全然触れれていなかったので、夜のゆきこに出ました。

bayashikoさん、前日にポジティブになれるような楽しい問題をありがとうございました。

決勝

ホテルに朝食はついていなかったので適当に朝マックを食いました。 張り切ってしまってめっちゃ早くついたのでkotatsugameさんとともに一番乗りの受付を果たしました。 意味ない。

赤橙黄の強い人たちが続々と会場にやってきて感動していたんですが、自分からはあまり話しかけられない(相手が自分を認知しているかがわからなかったため)ので自席で淡々ともすーんバチャをやってました。

ちょくだいさんが壇上で軽く開会宣言をした後、2分ほどの静寂の後コンテストは急に始まりました。 配点が高めだったので素直にA問題から見ました。

A問題

こういうのは縦と横を分けて考えて等差数列の和の積みたいな形になるはず！と思ったんですが意外とうまくいきません。

とりあえず$V$を$a$,$b$,$c$,$d$を使って表してみると、等差数列の和の形にそれが何列あるかを書けたものを2項という感じの式で表されます。つまり$b-a$,$a+b$,$d-c$,$c+d$と定数の積の和になります。 $b-a$,$d-c$を全探索で固定すれば条件を満たす範囲の$(a+b,c+d)$が定数個に定まることがわかったので慎重に式変形して列挙していきます。

少々式変形をバグらせて焦りましたが31分7秒時点でACしました。

B問題

とりあえず、$i$番目のクイズとと$j$番目のクイズが連続している時、$i$番目のクイズを$j$番目のクイズの前に解いたほうが嬉しい条件を求めると、$p_iS_i+p_ip_jS_j>=p_jS_j+p_jp_iS_i$になります。

これが全順序になることは証明していませんが、どうせなるだろうと思ってstd::sortの比較関数としてぶち込みます。

入力例3で変な答えが出てきましたが複数通りの答えがあり得る問題だったし検証するのが結構面倒なので雑に提出しました。WAでした。$p$が百分率なのを忘れてました。適当に100倍しました。ACしました。(49:43)

C問題

これはかなりすんなり解けました。

XORが除数に来て嬉しいことがあるわけないのでここを全探索するだろ。そんで計算量が調和級数になるやつだろって目をつけます。

$A\oplus B$の倍数$A$を全探索して$B=A\oplus(A\oplus B)$が$A\oplus B$の倍数化を判定すればいいだけです。AC(61:09)

D問題

ARCっぽいad-hocな匂いがしなくもないですが、与えられた規則が結構対称的な性質を持っているので頑張れば解けそうな見た目をしています。

とりあえず$P$が等差数列になってるときは同じ等差の数列で初項が$0,1,\dots,N-1$のものが各$N$個あることになります。 そうでないときも初項は$N$種が各$N$個であり、同じ初項を持つ列は全て異なる$a$で生成されていることがわかりました。

辞書順$K$番目を求める時の典型として2文字目…3文字目…と順に、ある文字で始まる列が何個存在するかを数え上げて前から確定していくというのがあります。 しばらくこの方針で考えていましたが2文字目からして何個あるかがわかりにくい感じになっていました。

次なる方針として、$(0,1,…N-1)$を適切な比較関数でソートすることにより、$i$が$j$より前に来ることと$f(i,B(i))<f(j,B(j))$(ただし$B(i)$は先頭文字が期待するものになるように$i$ごとに適切に選んだ$b$)が同値になるようにします。 さて、$f(a,b)$の階差数列は$b$によらないことから$P$の階差数列を$a$に応じてずらしたものと一致することになります。 初項が等しいなら階差数列のLCPまでは等しい数列になることから、その次の数値$c_i$を比較すれば順列の辞書順大小が高速にも止まりそうです。

同じ階差数列の途中からの部分を比較しているので、Suffix Arrayを使うのが計算量的にも良さそうですが、LCPを抜けた部分の$c_i$の大小が文字列のように一定ではないため実装が面倒そうです。 こういうときは信じてロリハにぶたんを気合で投げます！

…なぜか半分くらいのケースでWAになるんですよね。ジャッジの様子的にでかいケースで落ちてそうな。 自前のロリハライブラリを最近改修したところでバグの可能性を考えてei1333ライブラリに変えてみたり、衝突を疑ってハッシュを2重3重に持たせてみたりバタバタしてました。 しかもマジで衝突してたようで1ケース改善したりで、ずっとそっちを疑ってしまっていました。

結論として、ロリハが問題ではなく、$K$の入力をint型で取っていたせいでオーバーフローしていました。馬鹿すぎる！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

11ペナの末ACしました。(171:30)

残り

残り8分しかなかったのでトイレに行きました。 JOIや共通テストなどでもそうでしたが、オンサイトコンでやり切った瞬間急に尿意を催す癖があります。

残りの問題にさっと目を通しましたが無理そうでした。

結果

結果として、4完最弱の84位というなんとも言えない順位になりました。 6位から84位まで全員同じ点数ということなので悔いは残りませんでした。

それにしても上位陣の解答スピードはエグいですね。 僕も早解きは得意になってきてABCではこの頃50位を切ることが多くなりましたが、問題が難しくなるとやっぱり赤コーダー様達の足元にも及びません。

コンテスト後

お昼ご飯は叙々苑の焼肉弁当！これだけでテンション上がります。 さすがの美味さでした。

「rngからの挑戦状」というAtCoderオンサイトで昔は恒例だったらしい謎のクイズ企画を観戦して笑ったり、トヨタの社員さんとちょくだいさんの対談、kenkooooさんによるAtCoder Problemsに関する発表、pepsin_amylaseによるDiff推定の話などを聞きました。 いろいろ興味深かったです。

トークセッションに参加する以外にも気になる競プロerさんに挨拶したりして楽しみました。

イベント終了後は｢競プロer大宴会｣に参加しました。 トヨタコン参加者は暖色の学生が多かったですが、それ以外にもいろんな世代の競プロer達とお会いできて楽しかったです。

↑「最大の自然数本締め」で音が聞こえてちょくだいさんが「あ、みんな1なのね」って反応したのが面白かったです。(0の人のリアクションは聞こえないので当然1が目立ちますよね)

おわりに

初めての全年齢オンサイト、マジで最高でした！ AtCoderさん、トヨタさん、開催ありがとうございました！！