データ構造/アルゴリズム実装コンテストであるところのパソコン甲子園2022の予選の問題の解法例を解説します。
はじめに
なお、私は PCK 運営とは全く関係ありませんし、特別な許可などもとっていませんし、想定解を知りません。
公式が解説を出したら記事を非公開にします。（紛らわしくならないように）
予選
問題1 ２０周年
$2003$ 年が第 $1$ 回で毎年開催なので、 $x$ 年は第 $(x-2002)$ 回です。
プログラムは次のようになると思われます。
- 整数 $y$ を入力する。
- 整数 $a:=y-2002$
- $a$ を出力する。
問題2 体温測定
平熱は 36 度 9 分以下（ 37.5 よりも小さい）らしいので、次の図の通りに値の範囲で出力を変える必要があります。
整数でない値の表現には double 型を用います。
ただ、小数での比較による分岐は往々にして不正確になる(補足1)ので、比較対象の値を $10$ 倍して整数で処理するのが確実です。 $d_1.m_1$ は $d_1\times 10+m_1$ 、 $37.5$ は $375$ で置き換えます。
問題3 負けが勝ち
勝利条件を考えると、次の戦略が得られます。
- $3$ 回のじゃんけんのうち、そのままの状態で勝った回数が負けた回数よりも多ければ、「負けが勝ち」を宣言するべきではない。
- $3$ 回のじゃんけんのうち、そのままの状態で負けた回数が勝った回数よりも多ければ、「負けが勝ち」を宣言するべきである。
- それ以外は、どちらにしても勝てない。
$a$ を 勝った回数 、 $b$ を 負けた回数 とすることで、次の計算手順を得ます。
- $a=b=0$ とする。
- $3$ 回繰り返す：
- $x$ , $y$ を入力する。
- 勝ち負けを判定する。
- $x$ が勝つなら、 $a$ に $1$ を加算する。
- $x$ が負けるなら、 $b$ に $1$ を加算する。
- $a\gt b$ ならば $0$ を出力する。
- $a\lt b$ ならば $1$ を出力する。
- それ以外は、 $2$ を出力する。
$x$ と $y$ の組み合わせは $9$ 通りなので、勝ち負けの判定は単純な条件分岐で処理することも困難ではありません。このようにして、正しい計算手順が得られました。
なお、この問題の変換方式において、手 $a$ が手 $b$ に勝つ条件が (a+1)%3==b のように表せることはよく知られています。
問題4 グループ
“グループ”と”グループの切れ目”は交互になるので、グループが $2$ 個以上ある場合はグループの切れ目も同じ数だけあります。よって、 $c_i$ ( $i=0,1,\ldots ,N-1$ ) に現れる $0$ の個数を $a$ とすると、出力は $\max\lbrace 1,a\rbrace$ と表せます。
より直接処理する方法もあります。「手をつないだ後、グループに関する情報を得る」という問題はしばしば disjoint set union と呼ばれ、単純かつ効率的なデータ構造があります。 (Wikipedia)
問題5 パスタの茹(ゆ)で具合
いくつか例を確認しましょう。
- (1) 「茹で足りない」の時間以下なら、「茹で足りない」です。
- (2) 「茹ですぎ」の時間以上なら、茹ですぎです。
- (3) 「ちょうどよい」時間が $2$ つ以上あるなら、その中間は「ちょうどよい」です。
- (4) 以上の推論からわからない部分は、「判断できない」です。
(4) に疑問が残るかもしれません。扱う点が実数、特に整数であることに注意すれば、次の $2$ 点から (4) を証明できます。
- (5) 実験を行った点のうち、隣接しながら判定結果が異なる点が $2$ つあり、その中間のある点について知りたい場合、判定結果の境界はその左右どちらにもとれる。
- (6) 「茹で足りない」の判定が得られなかった場合、どれだけ短い時間であっても「茹で足りない」と「ちょうどよい」の可能性を排除できない。「茹ですぎ」側も同様。
「ちょうどよい」については、「ちょうどよい」の判定が出た点の最小値と最大値を管理すれば、その間のみ「ちょうどよい」と判断できます。「茹で足りない」「茹ですぎ」については、両端に $\pm 1,000,000,000,000$ などの値を設定することで同様に処理できます。結局、各判定結果に対して実験した時間の最小値と最大値をとれば、質問がその間に入っているかどうかで判定できることになります。
問題6 スプリットタイム
$1$ 周ずつ経過時間を計算します。失敗回数も同時に数えることができます。 $1$ 周分のアルゴリズムは次のようになります。
- $T$ 秒かかる。
- 目標経過時間超過なら
- 失敗回数に $1$ 加算する。
- そうでなければ
- 失敗回数を $0$ にする。
- 目標経過時間まで待つ。
- 失敗回数が $2$ なら、持久走は終了する。
問題7 税の徴収
行動する徴税官は、徴税官のうち最も小さい番号の位置にあるものです。これを見つけることは優先度付きキューを使うと高速です。
“まだ徴収していない家で、行動する徴税官よりも番号が大きいもののうち、最も番号が小さいもの” 、これは平衡二分探索木で高速に処理できます。 C++ では std::set<int> 、 Java では java.util.TreeSet<Integer> が該当します。ただし、今回は行動する徴税官が番号最小なので、最小値を優先する優先度付きキューでも高速に処理できます。
問題8 一方通行迷路ゲーム
書き換えが起こらない場合、明らかに有向グラフの最短路問題になります。幅優先探索で高速に解けることが有名です。
現在いるマスの位置と、到達までに書き換えたマスの個数の組に対応して有効グラフの頂点をとります。元々のマスの情報に従って進む場合と、書き換えによって任意の方向に進む場合に応じて辺を追加します。このグラフで同様に最短路問題を処理することで、書き換えが $0$ または $1$ 回の最短路が求まります。
同じマスを何度も通る場合は最適ではなく、 $1$ 回書き換えたマスに戻ってくるような経路については別のよりよい経路をとれます。よって書き換えたマスの位置を覚えておく必要はないというわけですね。
問題9 パスワードをお忘れですか？
$0000$ から $9999$ まで試し、条件を満たすパスワードを列挙できれば出力は簡単ですね。
+ , - , * , () が現れる計算式の処理（構文解析）は出題例がすでに複数あるので、参考になるブログもあると思われます。以下では実装方針の例を示します。
() は再帰関数で処理します。 ( を読み込んだら関数を呼び出し、 ) を読み込んだら返ります。
- と + は構文解析上では同一視できます。 () を含まない計算式を前から読み上げたとき、次のような形の式は即座に計算してもよいです。
- $a$
*$b$ $\rightarrow$ $a\times b$ - $a$
+$b$+$c$ ( $a$ の直前は*ではないとする) $\rightarrow$ $a+b$+$c$
よって、 () を含まない計算式を読み上げるのに記憶すべき情報は
- $a$
+$b$*(後の式)
という形しか要りません。 $a=0$ , $b=1$ で初期化すれば計算式を読み上げながら計算できます。
問題10 テレポート移動網
問題8 一方通行迷路ゲーム が解けたならすぐ分かると思いますが、 $1$ つのテレポーターを複数回使うなら $1$ 回だけ使うほうがよいので、テレポーターを動かしたことは覚えておく必要がありません。
テレポートの始点をコスト $C$ で移動することを、その地点までコスト $C$ で歩いていくことに置き換えることができます。すると、移動するものがあなたしかいないので、移動コストを重み付きグラフで表せば最短路問題として解けます。ダイクストラ法により、計算量は $O((N+M)\log (N+M))$ になります。
問題11 農地開発
収支の値の範囲が限られています。あり得る値は $2,000,001$ 種類しかないので、その種類数を $X$ とおきます。また、そもそも農園が $N+Q$ 個あったとして解いても同じなので、その値を $N$ ということにします。
農園は $N$ 個ならば道は $N-1$ 個で、連結なので、農園を頂点、道を辺とするグラフは木です。
木の $u$ , $v$ 間の最短経路に関する問題は、適当な頂点 $r$ をとって $r$ , $u$ 間、 $r$ , $v$ 間 , $r$ , $\text{LCA}(u,v)$ 間の問題に分解することですべてを $r$ 基準にすることができます。 $\text{LCA}$ は最小共通祖先（Lowest Common Ancestor）であり、 binary lifting などの前計算により $1$ 回あたり計算量 $O(\log N)$ で計算できます。
また、「 $k$ 番目」は二分探索で求めます。すなわち、適切に $x$ をとって収支が $x$ 以下の農園を数え、個数が $k$ 以上かどうかで答えの範囲を狭めます。
解くべき問題は次のようになります。（この問題が呼び出される回数は $O(N\log X)$ です。）
- $r$ (一定) から $v$ へ至る最短経路において、収支が $x$ 以下の農園はいくつあるか？
各頂点に、収支の値ごとに農園の個数を管理するようなセグメント木があれば、これを処理できますが、メモリが足りません。
$r$ からある頂点に至る過程で、道を $1$ つ通るごとにセグメント木の更新は $1$ 点のみです。このようにして、 $O(N)$ 回の更新で各頂点のセグメント木の状態を経由することができます。必要な情報は、その過程の適切なタイミングでセグメント木のクエリを呼ぶことで得られます。二分探索によって $O(\log X)$ 回この過程を繰り返すので、計算量は $O(N\log (N)\log (X))$ になります。正解するためにはおそらく十分高速です。
さらに、セグメント木の状態を保存しながら、更新した部分を複製するようにすれば、任意のタイミングのセグメント木にアクセスすることができます。このようなデータ構造は永続セグメント木 (より広くいうと、永続データ構造) と呼ばれます。セグメント木は配列で表現されることが多いですが、永続化ではそうはいかず、ポインタで構造を表現することになります。セグメント木の探索を再帰関数で表し、ノードを書き換える代わりに新しいノードを生成すれば永続化されます。
ノードを動的に生成するデータ構造は、他と比較すると一般に低速ですが、問題によってアルゴリズムを高速化することで正解が得られます。セグメント木から得られる値を二分探索に使用しますが、二分探索の境界値をセグメント木の形にフィットさせることで、二分探索とセグメント木のクエリを同時に計算することができます。永続セグメント木を用いることで、計算量は $O(N(\log (N)+\log (X)))$ になります。この方法について、実装例を用意しました。
どの場合も入力全体をすべて先に読み込むことで、木の構造および収支の大小関係全体を先に処理することもできます。収益が $0,1,\ldots ,N-1$ であるような問題に置き換えるようにすると、計算量中の $\log (X)$ を $\log(N)$ に変化させることができます。