ももはらの日記

日記を書きます

CodeQUEEN 2024参加記

はじめに

こんにちは、ももはらです。この度、CodeQUEEN 2024 で3位になりました！

この記事では、来年まで嬉しさと悔しさを忘れないように、CodeQUEEN 2024 に参加するまでと当日感じたことを書こうと思います。

問題の内容のネタバレも含みますので、ネタバレが嫌な方は下記の問題を先に見るか、コンテストの章を飛ばして読んでいただければと思います。

atcoder.jp

 

参加するまで

CodeQUEEN 2023 にも実は参加しており、3位になっています。

 

Dが解けずにかなり悔しい思いをしました。理由としては下記の3つが大きいと思っています。

  • オンサイト順位表ではこの問題を解けた人はおらず、順位表から見るとかなりの難問に位置していた
  • 珍しく優勝を争っている立場というのに緊張していた
  • 当時1年競プロを辞めて復帰したてだった

 

そして、この年のコンテストではE問題が勝敗を分けました。

atcoder.jp

当日dokinさんが異常に早く通していたこの問題では、 max Σ(max(Bi)-min(Bi)) というスコアを素直に計算しようとするとセグ木などで実装が必要になるのに対して、max Σ(a - b) (a,b∈Bi)と変形してからDPするとめちゃくちゃ早く解けると教えてもらい感動していました。

mayocornさんは私と同じくセグ木解だったのですが単純に実装速度が早すぎて負けました。すごすぎます。

考察面でも実装面でも敗北し、来年はもっと上手く、もっと早く実装できるようにしたい！という思いで練習を重ねてきました。

練習内容としては主に下記を行いました。

  • できるだけABCに参加する
  • まよこんバチャに参加してみる
  • 競プロを辞めていた時期のABCをバチャする
  • æ°´diff〜黄diff以下埋め
  • FPSや高速ゼータ変換など新しいアルゴリズムを勉強してみる

その結果、去年参加時のレート1985から今年はレート2101まで伸ばした状態で参加することができました。

CodeQUEEN 2024 当日

お昼

obakedesuyoneさん、tenbaさん、ngtkanaさんと一緒にランチに行きました。

maps.app.goo.gl

お昼といいつつ、集合時間11時だったのでかなり遅刻しないかひやひやしていましたが、この会のおかげでごはんぬきや決勝に遅刻したりをせずに済みました。

あとご飯も美味しかったです。（おばけさんのお店選び力すごすぎます！）

会場

ふなわさんデザインのTシャツ可愛かったので早速着ました。今年は猫ちゃんいてかわいい！

あとtomoeさんのクリアファイルも可愛いです。名刺ももらってしまいました。家宝です！

 

そして順位表を見ると、去年参加してた方のレートが全体的に上がってて、みんなが強くなっていってるのがすごい嬉しくなったし、今年から参加の強い方も増えてて嬉しくなりました！

去年「今年が最後になるかも」って言ってた子が参加してくれててテンションあがったりしていました。

今年はコンテスト前の時間もかなり余裕を持たせてくれてて、いろんな方に話しかけに行けて楽しかったです。

 

コンテスト

コンテスト直前は一気に静かになって緊張が戻ってきました。

 

A〜D⭕️

序盤はかなり早く解け、Dまで解いた時点だと1位になっていました。

E⭕️

最初誤読をして一人当たりCi円だと思って貪欲で解いてしまい、サンプルを通して間違っていることに気づきました。
焦る中考察ができず順位表を見ると、EをmayocornさんFをdokinさんが通していたので、自分と解ける問題の傾向が近いmayocornさんを信じてそのままEで粘りました。
貪欲の時の影響で人主体で見ていたのを、部屋主体で見るように思考を変えたらDPできるようになり、無事ACできました。

F⭕️

dokinさんがかなり早く通していたのですが、実装が早い方針は浮かびませんでした。

平均値との差分の累積和を遅延セグ木で持ち0以上かを判定して頑張ることにして、ACしました。

G❌

まったくわからず、、とりあえずkを決め打ちぶたんして、構築は貪欲でoxoxoみたいにみるとoに数が大きい順に配置してから、x埋めてくとかいう方針で出してみました。6ケースWA。その後もWAとれずです。。

感想

去年が有志コンぽい問題が多かったのに対して、今年は全体的にABCっぽい問題が増えててかなり楽しく解くことができました。

そして今回特に記憶に残った問題はFでした。

atcoder.jp

dokinさんのFがあまりに早かったのでコンテスト直後に「Fどうやって解いたんですか！？」と聞きにいきました。

自分は1つめの遅延セグ木を使った方針でかなりバグらせながら通したのに対して、dokinさんは2つめの方針をとってかなり早く問題を通していました。

  • 遅延セグ木で平均値との差分（N*Ai-ΣAi）の累積和を管理して、minが0以上になる場所。差分更新して全ての位置を調べる。
  • 平均値との差分の累積和が最小になる位置の隣。

まだまだ考察面で及ばないなというのを強く感じましたし、dokinさんから「セグ木は絶対にバグらせるから使わないようにしている」と聞いて圧倒的強さを感じました。

また、コンテスト後にこの方針について話している際に、chokudaiさんが見にきてくれて「（TopCoder）赤になるまでセグ木はいらなかった。現代だと、データ構造ゲーが増えてきたが、当時はライブラリを持たずに手打ちのみで戦っていたのもあり、セグ木はあまり使わないようにしていた。」という言葉もいただきました。

強い人は考察力のみで解ける問題の幅が広いんだなとより凄さを感じました。

自分もより考察力を身につけていけるように来年まで精進したいです！

表彰

今年は凍結後も動きがあって、凍結時だと2位で表彰台は確定していたのですが心臓バクバクでした。そして4位が発表された時点で、2位ではないことが確定してこっそり凹んでいました。

去年に引き続き3位が取れてとても嬉しいのですが、今年は2位以上を目指していたのでかなり悔しくもあります。

去年からの目標の打倒mayocornさんは達成できたのですが、今年新たに現れたngtkanaさんに負けてしまったので来年は打倒ngtkanaさんです！

懇親会

ご飯が豪華！

前半ご飯を食べるのに夢中になっていました。美味しかった〜
AtCoderの女性スタッフさんが考えてくれたとのことで、感謝の気持ちでいっぱいです。

kenkooooさんとも少しお話しさせてもらえて、「今年は、りんごさんの采配で配点を後半重めにして、順位表凍結後も変動が生じるようにした」と言ったことを聞けました。確かに去年よりも心臓バクバクでした。采配能力が凄腕すぎます。

今年は本業が忙しすぎてスポンサー業務にあまり関わっていなかったのですが、スポンサーとして弊社クイーンが出題した問題が出されており、会場のいろんなところで議論が巻き起こっていました。会場出口のホワイトボードの前でりんごさんも含めて議論されているのをみて、すごい嬉しくなっていました。私まだ解けてなくて困っているのですが。。

女子部オフ会

今年は去年よりも参加者が増えてて、さまざまな方とお話しすることができて楽しかったです。

お蕎麦屋さんって蕎麦も美味しいですけど日本酒も美味しいですよね。

tabelog.com

おわりに

来年はもっといい順位取れるよう頑張りたいです！

Â