PCK2021予選問題解説

データ構造/アルゴリズム実装コンテストであるところのパソコン甲子園2021の予選の問題の解法解説をします。

※この記事には全問題の解説が揃っていません

2022/05/19

• 問題13 の解法を更新しました。
• 問題3 の計算式の $\max$ を $\min$ に修正しました。

2022/06/12

• 問題6,7 の解説の計算式を修正しました。

動機

本選解説より予選解説のほうが需要あるのでは……

ちなみに

次は、予選のルールを一部省略したものです。

• 2人で1チーム、使えるPCは2台まで（つまり同時コーディング可）
• 180分
• 次の優先順位で成績を比べ、順位とする。
  • 正解した問題の点数の合計の大きい順
  • 不正解数の小さい順
  • その得点に到達した時刻の早い順
• 利用可能な言語は C,C++,Java

予選

問題1 マウスの移動距離 / Mouse Movement Distance

問題文

$4[\text{ミッキー}]=1[\text{mm}]$ なので、 $d[\text{ミッキー}]=\frac{d}{4}[\text{mm}]$ です。 $d$ は $4$ の倍数なので、 $\frac{d}{4}$ は整数です。

よって、プログラムは次のようになると思われます。

1. 整数 $d$ を入力する。
2. 整数 $x:=\frac{d}{4}$ （整数範囲で計算できる。）
3. $x$ を出力する。

問題2 ミニ 絵合わせゲーム / Mini Picture Matching Game

問題文

ゲーム終了とはすべてのカードが除かれることなので、ゲームが終了できる必要十分条件は同じ絵柄が書かれたカード $2$ 枚の組が $2$ つあることです。

解法1

入力を昇順ソートすると、同じ値があれば連続します。昇順ソートされたものにおいて、ゲームが終了できる条件は前 $2$ つが同じかつ後ろ $2$ つが同じことです。

昇順ソートには標準ライブラリのものを用いるのが良いです。

解法2

同じカードの組が $2$ つある様子を列挙すると、 AABB ABAB ABBA の $3$ 通りしかありません。 $3$ 通りそれぞれを判定します。

問題3 ダイアル錠 / Dial Lock

問題文

入力の前に $0$ を足すことで、実際の移動の様子を表現します。

$0 \rightarrow 3 \rightarrow 7 \rightarrow 4$

この移動は次の $3$ 段階に分解できます。

$0 \rightarrow 3, 3 \rightarrow 7, 7 \rightarrow 4$

この $3$ 段階それぞれ独立に、ダイアルを回す方法を選べます。

任意の入力についてこのように分解すると、結局

$a \rightarrow b$ $( 0 \leq a,b \leq 9 )$

の場合のみ考察すればよいです。移動 $1$ 回分なので、 $2$ つの回転方向を試し、音が鳴る回数が少ないほうを選べばよいです。ここで、

• $2$ つの回転方向それぞれの音が鳴る回数を足し合わせた値は $10$ である
• $9,0$ の間を跨がない方の移動で音がなる回数は $a-b$ の絶対値である

という事実から、移動 $1$ 回分のときの答えは $\min\{ |a-b|, 10-|a-b| \}$ と表せます。

以上から、次のアルゴリズムを得ます。

$N$ と、 $a_1$ から $a_N$ を入力する。
$a_0$ に $0$ を代入する。
$\mathrm{ans}$ を $0$ で初期化する。
$i=0,1,2,\ldots ,N-1$ について、以下を行う。
　　$\mathrm{ans}$ に $\min\{ |a_i-a_{i+1}|, 10-|a_i-a_{i+1}| \}$ を加算する。
$\mathrm{ans}$ を出力する。

問題4 乗り継ぎ / Connecting

問題文

まず、問題文がわかりにくいので整理します。

アイヅからシオカワまで $N$ 本、シオカワからキタカタへ $M$ 本の電車があります。

キタカタ駅到着に $h$ 時 $m$ 分の時間制限があります。

シオカワ発の電車をすべて確認すれば、シオカワ駅到着の時間制限が分かります。アイヅ駅も同様です。

この過程で、有効な電車が見つからなければキタカタ駅に到着できません。

以上で、必要な判定ができました。

問題5 デジタル時計 / Digital Clock

問題文

デジタル時計の表示の変化を表現するために、「時刻（ $h$ 時 $w$ 分）が与えられたとき、次の時刻（つまり $1$ 分後）を求めよ。」という問題を考えます。基本的には $w$ に $1$ を加算し、 $w$ が $60$ 以上になった場合に特殊な操作をすれば解けます。

これを用いて、 $1$ 分ごとに「 $h$ 時 $w$ 分 $\rightarrow$ $h^{\prime}$ 時 $w^{\prime}$ 分」という表示の変化を列挙できます。桁に分解することで「数字 $\rightarrow$ 数字」になります。

「数字 $\rightarrow$ 数字」は全部で $100$ 通りしかないので、手計算で求めてプログラムに書き込めます。

問題6 ミックススパイス１ / Mixed Spice１ , 問題7 ミックススパイス２ / Mixed Spice２

問題文1 , 問題文2

$x_i$ の最大公約数が $1$ という制約から、スパイス生産の最小単位は「 $1 \leq i \leq N$ についてスパイス $i$ を $x _ i$ グラム」です。

$K$ 単位作る場合、スパイス $i$ の購入量は $( \max \lbrace 0, K x _ i – b _ i \rbrace )$ グラムですから、 $K$ を固定すれば合計の必要な金額がわかります。

よって、「 $K$ 単位作ることができるか」の判定が計算量 $O(N)$ です。したがって $K$ の値で二分探索すれば、作ることができる最大量は、答えの $K$ に対して計算量 $O(N \log K)$ で求まります。

問題8 募金街道 / Fundraising Street

問題文

わかりません

問題9 奇数の精と偶数の精 / Odd and Even Spirit

問題文

$10$ 進整数とその末尾の数字は、偶奇が一致します。よって、 $1$ つの整数に対しては偶数の精は末尾に近いほうから奇数の数字を、奇数の精は末尾に近いほうから偶数の数字を消すのが最適です。奇数の精は一度奇数を作れば、その数についてそれ以上数字を消す必要はありません。

偶数の精の戦略は、各数で消しゴムをうまく分けて、奇数の精が使う必要がある消しゴムの長さを最大化することです。各整数は「消しゴムを $w$ 回使うと、奇数の精に消しゴムを $v$ 回使わせられる」という性質をたくさん持っていますが、これはナップザック問題における品物と同じ性質です。

よって、この問題はナップザック問題の変種になります。よって、 $i$ 番目までの品物のみ考え、重さ $w$ 以下となるときの価値の最大値を $\text{dp}[i][w]$ として動的計画法で解きます。 $1$ つの品物の代わりに、いくつかの品物から $1$ つ選ぶことになりますが、動的計画法のテーブルの設計上問題ありません。

$a_i$ の桁数の最大値の制約を $A$ として、全体の計算量は $O(NX(X+A))$ です。

問題10 蜘蛛の巣上の最短経路 / The Shortest Path on the Spider’s Web

問題文

問題文同様、同心円 $i$ と放射状の線分 $j$ の交点を地点 $(i,j)$ と表します。

まず、 $xy$ 平面上で地点 $(i,j)$ の座標を求めます。三角関数 $\sin$ , $\cos$ を用いて $(i\cos(\frac{2 \pi j}{N}),i\sin(\frac{2 \pi j}{N}))$ とすればよいです。

「あと $k$ 回線分を生成できる状態で地点 $(i,j)$ にいる」という状態を、過程 $(i,j,k)$ と呼びます。

すでにある線分と、生成する可能性がある線分、および各線分の長さを列挙することで、過程 $(i,j,k)$ を頂点とするグラフを作れます。この上でダイクストラ法を用いて答えが求まります。

計算量は $Z=NMK+N^2K$ として $O(Z \log Z)$ です。

問題11 決まりを守る漁師 / Fishermen Following the Rules

問題文

座標 $(i,j)$ と値 $A _ {i,j}$ の組を、 $A _ {i,j}$ でソートします。これを踏まえて、長さ $HW$ の $01$ 列をデータ構造で管理し、 $1$ 点変更、左から $K$ 番目の $1$ がある位置を求めるクエリを用いて問題を解きます。

網の左上の位置を $(1,1),(1,2),\ldots,(1,W-C+1),(2,1),\ldots$ のようにして走査すれば、 $1$ 点変更は $O(H^2W)$ 回になります。

追加/削除のクエリは $O(H^2W)$ 回、左から $K$ 番目を求めるクエリは $O(HW)$ 回ですから、平方分割の要領で $H$ 個のバケットに分けて $1$ の個数を管理すると全体の計算量は $O(H^2W+HW\log(HW))$ です。

問題12 回転マスゲーム / Rotating Mass Game

問題文

ある区間について集約したデータについて、クエリに答えたり一度に回転したりする上では生徒が並んでいる順番を無視しても問題ありません。また、各生徒の状態は東西南北のどちらを向いているかの $4$ 通りのみです。よって、遅延セグメント木の各ノードで、

• $4$ 状態それぞれ何人の生徒が含まれるか
• 回転クエリの遅延伝播

を管理すれば、クエリを処理できます。

計算量は $O(N + M \log N)$ です。

問題13 通勤路 / Commuting Route

問題文

実用上の解法

アイヅ町を表すグラフは木です。

経路上（始点と終点を除く）の各地点では、横道にそれてどこかで折り返して戻ってくることしかできません。 $1$ つの地点から横道が $2$ 個以上あるとき、そのうち $1$ 個しか使えません。

各地点から横道にそれる方法の個数は、折り返す頂点と対応付けることで

• その地点から、始点側の部分木と終点側の部分木を除いた部分の頂点数

と同じだとわかります。よって各地点で独立に求めて掛け合わせると、とりあえず答えになります。

適当に根をとって根付き木にします。頂点 $v$ の親を $p(v)$ とします。また、頂点 $v$ の部分木の頂点数を $s(v)$ とします。

根以外の頂点 $v$ で値 $s(p(v))-s(v)$ を管理します。各地点で独立に求めていた値のほとんどは $s(p(v))-s(v)$ にあてはまります。例外は地点が始点と終点の共通祖先である場合の高々 $1$ つです。

パスクエリの範囲を高速に計算します。クエリはもちろん $s(p(v))-s(v)$ の総積です。また、 heavy light decomposition を用いて LCA 、および $u-v$ パス上で $u$ に隣接する頂点をそれぞれ計算量 $O( \log N)$ で求められることに注意します。

クエリで指定される $2$ 頂点 $u,v$ （順不同）の位置関係で場合分けをし、クエリに答えます。

• $u$ が $v$ の親のとき、答えは $1$ 通りです。
• $u$ が $v$ の祖先のとき、 $u-v$ パスから $u$ 側の $2$ 頂点を除いた区間の総積が、求める答えです。
• $u$ と $v$ の LCA を $g$ とします。 $g$ が $u$ でも $v$ でもないときを考えます。 $g-u$ パス上で $u$ に隣接する頂点を $u^{\prime}$ 、 $g-v$ パス上で $v$ に隣接する頂点を $v^{\prime}$ とします。 $g$ だけ個別に求めます（値は $N-s(u^{\prime})-s(v^{\prime})$ ）。あとは $(g,u)$ と $(g,v)$ に対する答えを用いて計算できます。

あとはパスクエリ本体についてですが、 $\mathrm{MOD}=998244353$ は十分大きい素数なので、掛け合わせる要素には逆元があります。よって、この逆元を前計算すると、パスクエリは累積和同様にクエリ当たり計算量 $O(1)$ になります。前計算は $1,2,\ldots ,N$ の逆元から計算でき、計算量は $O(N)$ です。

以上で、全体の計算量は $O(N + Q\log N )$ になり、十分高速です。

理論上の解法

LCA および level ancestor は計算量 $O(N+Q)$ のアルゴリズムが存在します。

lowest common ancestor : cf. ｼﾞｮｲｼﾞｮｲｼﾞｮｲ https://joisino.hatenablog.com/entry/2017/08/13/210000

level ancestor : cf. 37zigenのHP https://37zigen.com/level-ancestor-problem/

よって、この問題の計算量を $O(N+Q)$ とできます。しかし、非常に複雑な実装が必要であり、このため実行時間が改善しない可能性も大きく、この問題のために実装するものではないでしょう。