CodeQUEEN2024で優勝しました

こんにちは、フォルシア株式会社エンジニアの宮本です。このたびCodeQUEEN2024というイベントに参加し、優勝することができました。この記事では当日のコンテストを振り返ります。

また、今年もフォルシアではCodeQUEENに協賛しスポンサー活動を実施しました。記事の最後ではスポンサーとして出題したクイズの解答も掲載したのでご覧ください。

• 昨年のブログ : https://www.forcia.com/blog/002760.html

CodeQUEENとは？

CodeQUEENは、AtCoder株式会社と合同会社AlgoParadeが共催する 女性向けプログラミングコンテスト です。コンテストの予選はオンライン、本選は全国の参加者が一堂に会して実施されます。

問題の形式はAtCoderと同じなので、競技プログラミングの力がいつも通り問われます。私は昨年度優勝することができ、今年は2連覇がかかっていました。しかし、ここ最近は競技プログラミングの成績が下降しており練習にもあまり時間が割けていなかったので、成績にはあまり期待せずコンテスト本選に参加しました。

競技プログラミングについて

競技プログラミングでは、与えられた入力に対して正しい答えを出力するプログラムを作成する問題が出題されます。『ゲームでどちらが勝つかを求める問題』『パズルの解法を求める問題』『ものの並べ方が何通りかを数える問題』など、色々な種類の問題があります。

競技プログラミングでは各問題に『実行時間制限』が与えられています。大抵の問題では全てのパターンを探索するプログラムを書いても実行時間制限に間に合いません。ちょうど、オセロの必勝法を求めるのに全パターン探索していたらいつまでも終わらないのと同じイメージです。問題を良く分析し実行時間に間に合うような効率的な解法を考えるのが競技プログラミングの面白さです。

以下の参加記では、競技プログラミングをやったことがない方にもなんとなくイメージが伝わればいいなと思い、一部の問題を図式化してみました。この記事を読んで興味を持ったら、ぜひ競技プログラミングに挑戦してみてください！

コンテスト本選の参加記

ネタバレを含むので、これから問題を解きたい方は読み飛ばしてください。

コンテストの本選では120分間で8問が出題されました。問題は後ろにいけばいくほど難易度があがり、その分配点が高くなります。最終的な得点の高い人が勝ち、同点の場合はタイムで順位が決まります。

CodeQUEENのような一発勝負のコンテストでは順位が大事なので必ずしもすべての問題を解こうとする必要はありません。現在の順位はリアルタイムで見ることができるので、まわりの様子をうかがいながら少しでも上の順位を目指します。

今回のコンテストでは後半に500点の問題が3問ありました。500点はCodeQUEEN参加者の上位層（青上位～黄色コーダー）で差がつく難易度なので、ここを何問拾えるかで優勝が決まると想定しました。一方、H問題の575点も全く手が届かない点数ではないので、他の参加者で解く人が現れると怖いなとも感じていました。

A問題～C問題

• https://atcoder.jp/contests/codequeen2024-final-N9tn8QqD/tasks/codequeen2024_final_a
• https://atcoder.jp/contests/codequeen2024-final-N9tn8QqD/tasks/codequeen2024_final_b
• https://atcoder.jp/contests/codequeen2024-final-N9tn8QqD/tasks/codequeen2024_final_c

序盤は比較的簡単な問題が並びます。油断して不正解のコードを提出すると5分のタイムペナルティを受けるので、間違えないように確実に解き進めました。

D問題 Attend Many Events

• https://atcoder.jp/contests/codequeen2024-final-N9tn8QqD/tasks/codequeen2024_final_d

D問題では『ダイクストラ法』でグラフ上の2点間の最短距離を求めたあと、『動的計画法』で最適化問題を解きます。字面で書くと難しそうですが、いずれも競技プログラミングでは標準的なアルゴリズムです。また、問題の設定から解法の自由度はあまり高くない（＝初手で2点間の最短距離を求める以外にはやりようがない）ので、解法を考えるもの慣れていれば難しくありません。

私はダイクストラ法の実装方法を忘れて調べながら書いたので、この時点で他の参加者におくれをとってしまいました。

F問題 Divide the Cake

• https://atcoder.jp/contests/codequeen2024-final-N9tn8QqD/tasks/codequeen2024_final_f

E問題は難しそうだったので、同じ得点のF問題を先に解くことにしました。いちごを取り合う対戦ゲームで勝つプレイヤーを答える問題でしたが、問題文をよく読むとゲーム自体にはほぼ戦略性がなく、配列処理のアルゴリズムを高速化することがメインです。この手の高速化はデータ構造を利用することが多く実装が複雑になりがちですが、今回は偶然良い方法を思いつきあっさりと解くことができました。

F問題を10分程度で正解できたことで優勝が大きく近づいたと感じます。

E問題 AtCoder Hotel

• https://atcoder.jp/contests/codequeen2024-final-N9tn8QqD/tasks/codequeen2024_final_e

E問題はお客さんをホテルの部屋に割り当てていき、料金の和を最小化する問題です。それぞれのお客さんには「〇ランク以上の部屋に泊まりたい！」という要望があり、要望を満たすように部屋に割り当てていく必要があります。問題の雰囲気から最大流問題に帰着するかシンプルな動的計画法の問題かのいずれかと踏みましたが、順位表を見るとすでに解かれていたので動的計画法にヤマを張って考えました。

要望の厳しい客を高いランクの部屋から順に割り当てていく動的計画法を組み、20分程度で正解しました。

G問題 Quintuple Scoop Ice Cream

• https://atcoder.jp/contests/codequeen2024-final-N9tn8QqD/tasks/codequeen2024_final_g

G問題は「人間だとすぐに解けるパズルをコンピューターで自動化して実装する」タイプの問題でした。この手の問題は実装方針の自由度が高い一方、下手なやり方をすると不正解を連発する沼に入ってしまいます。

今回は「最もシビアな状況でとるべき行動を手順化し、楽な場合も同様の手順で解く」方向性で、沼にはまらず正解することができました。

H問題 Good bye, AtCoder Land.

• https://atcoder.jp/contests/codequeen2024-final-N9tn8QqD/tasks/codequeen2024_final_h

残り時間30分以上の状態で最終問題に取り掛かり始めましたが、正解することはできませんでした。

結果発表

500点問題をすべて解けたのが功を奏し、優勝することができました。1問でも間違えていれば優勝できなかったので、かなり運がよかったと思います。

戦略が偶然うまくいっただけで再現性がなく、このままだと来年優勝するのは厳しそうです。基礎的な思考力、アルゴリズムの引き出し、実装力を高めて再チャレンジしようと思います。

まずは下がり続けているAtCoderのレートをなんとかするところからがんばります！

スポンサー活動

スポンサー活動では会場内にブース出展し、訪れた方に向けて会社説明などを行いました。コンテストメンバー3名 + スポンサー3名の計6名全員女性で参加したのですが、人数が多かった分ブースを盛り上げることができました。

※ 私ではないです（ねんのため）

目玉企画はクイズです。配布したチラシの裏面に問題を掲載し、解けた人には景品としてコースターをプレゼントしました。誰にも解いてもらえずブースに人が来ないのではと心配でしたが、とてもありがたいことに当日は20名くらいの方に問題を解いてもらえました。

フォルシア以外にもいくつかの企業がスポンサーとしてブース出展しており、アンケートや福引などわくわくする企画が目白押しでした。競技プログラミング界隈への訴求力向上に関して悩みを持っている企業も多く、お互いに情報交換することができました。

クイズの解説

さて、チラシに掲載したクイズの答えを発表します。

A問題　大きな数の計算

解説

答えは39です。

N の 一の位で場合分けします。

① Nの一の位が0,2,4,6,8のとき

f(N) は偶数なので一の位は1ではありません。

② Nの一の位が5のとき

f(N) は5の倍数なので一の位は1ではありません。

③ Nの一の位が1のとき

f(N) は N を繰り返し掛け合わせた値なので、一の位は必ず1になります。

④ Nの一の位が3 か7のとき

『f(N) の1の位が3 ⇔ f(N-1) が4の倍数』が成立します。
ここで、N-1 は偶数なので、f(N-2) が2以上であれば f(N-1) は必ず4の倍数です。
したがって、N = 3 の場合を除き、f(N) の一の位は必ず1になります。

⑤ Nの一の位が9のとき

『f(N) の1の位が9 ⇔ f(N-1) が偶数』が成立します。
ここで、N-1 は偶数なので、f(N-1) も必ず偶数です。
したがって、f(N) の一の位は必ず1になります。

すべて合わせると、一の位は1になるNの個数は39個とわかります。

B問題　数当てゲーム

解説

答えは33です。

途中までゲームが進行した状態で、1以上1000以下の各整数 K は以下のいずれかの状態になっています。

• 状態① : K = X と仮定した際、これまでの質問のうちある連続する2つの質問が正しくない
• • このとき、K = X の可能性は完全に排除されます。
• 状態② : 状態①以外で、K = X と仮定した際に直前の質問が正しくない
• • このとき、次の質問次第で K = X の可能性が排除されます
• 状態③ :状態①、状態②以外
• • このとき、K = X か否かについては情報がありません。

ここで dp[i][j] を以下で定めます。

• dp[i][j] = 状態②もしくは状態③の整数が i 個、状態③の整数が j 個の状態から最善を尽くしたときの質問回数

はじめは全ての整数が状態③なので、 dp[1000][1000] を求める動的計画法により、解答を求めることができます。

なお、この問題の解法にはより効率的なアルゴリズムもあり、たとえば 1以上1000000000以下の整数から2個に絞り込むまでにかかる回数も高速に求めることができます。

この記事を書いた人

宮本 唯

新卒3年目エンジニア。北海道のウニが好き。