PCK2020予選問題解説

2022.05.07

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

動機

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

ちなみに

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

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

予選

問題1 緯度経度 / Latitude and Longitude

問題文

それぞれ $3600$ で割って、小数点以下を切り捨てます。 C,C++,Java 言語では、整数型どうしで $0$ 以上の値の範囲で割り算を書くと、小数点以下を切り捨てた結果が整数で得られます。

計算手順は次のようになります。

  1. 整数 $La$ , $Lo$ を入力する。
  2. 整数 $La2:=\frac{La}{3600}$ （切り捨て）
  3. 整数 $Lo2:=\frac{Lo}{3600}$ （切り捨て）
  4. $La2$ , $Lo2$ を出力する。

ちなみに、制約の範囲を度に直すと緯度 $22$ 度から $46$ 度、経度 $123$ 度から $154$ 度となり、おおよそ日本の東西南北端点（参考：国土地理院 https://www.gsi.go.jp/KOKUJYOHO/center.htm ）を境界とする範囲を表していることがわかります。

問題2 商店街へのお出かけ / Shopping Street

問題文

状況を図に表すと次のようになります。

ヤエちゃんが店にたどり着ける条件は $s \leq m$ 、 タケコちゃんが店にたどり着ける条件は $w-s \leq m$ です。これを用いて、出力の項の通りに処理すればよいです。

問題3 あいさつまわり / Courtesy Call

問題文

当然、両端の家も訪れる必要がありますが、両端の家に訪れるならそれまでの経路上ですべての家に訪れます。よって、両端の $2$ つの家以外は無視して計算しても同じです。両端の家は、家の位置をソートするなどして得られます。 $2$ つの家を訪れる順番は $2$ 通りしかないので、それぞれシミュレーションします。

問題4 カラフル円盤通し / Colorful Disk

問題文

計算量オーダー $O(N^2)$

上から $k$ 番目の円盤が真上から見える条件は、 $l=1,2,\leq k-1$ について上から $l$ 番目の円盤がそれより小さいことです。

各円盤についてこれを判定します。 $N^2$ 回程度の計算が必要ですが、 $N^2\leq 10^6$ ですから問題ありません。

計算量オーダー $O(N)$

また、 $l=1,2,\leq k-1$ における上から $l$ 番目の円盤の大きさの最大値と並べて計算することで、判定を高速化できます。

問題5 写真の回転 / Rotating Photo

問題文

入力を $1$ つずつ読みながらそのつど回転を処理するのでは、代入操作が $N^2Q=2 \times 10^{11}$ オーダーの回数行われるため、十分高速ではありません。

$r _ i$ で指定される回転量を、すべて足し合わせて一度に処理してもよいです。足し合わせて得た回転量を $R$ とします。

回転量 $R$ に $4$ を足したり引いたりすることは、つまり $360$ 度の回転なので結果に影響しません。よって、 $R$ が $0$ 以上 $3$ 以下になるように変形できます。

得られた $R$ は時計回りに $90$ 度回転する回数ですから、実際に $90$ 度回転を $R$ 回行います。

$y$ 行 $x$ 列（それぞれ $0$ から数える）のマスは、時計回り $90$ 度の回転で $x$ 行 $(N-1-y)$ 列へ移動することを利用して実装します。

問題6 テトラヘドロン / Tetrahedron

問題文

座標 $(x,y)$ について、 $x$ を $4$ で割ったあまり $x^{\prime}$ 、 $y$ を $2$ で割ったあまり $y^{\prime}$ に変えても答えが変わりません。色の位置関係を固定すれば、 $4 \times 2$ の配列を参照して答えがわかります。

色の位置関係は、各面に塗ってある色を表す長さ $4$ の文字列で表せるので、これを列挙します。入力形式からわかるように、これは $12$ 通りしかありません。

$4 \times 2$ の配列は、色の位置関係の文字列を参照するための番号を要素にします。

問題7 加工機 / Processing Machine

問題文

表面積の変化は、処理したマスの前後左右の側面 $4$ 箇所しかないので、これらの面積を処理前と処理後で計算し、差分を答えに足し引きすれば全体の表面積を高速に計算できます。

$H \times W$ の配列は大きすぎて使えませんが、連想配列を用いれば問題ありません。

全体の計算量は $O(C \log C)$ です。

問題8 高速道路網 / Highway Network

問題文

通る地点の指定がない場合を考えます。 $u_i \lt v_i$ より、地点の番号の昇順に動的計画法ができます。動的計画法の各ノードで経路の個数 $x$ と経路の長さの総和 $c$ を管理することで、長さ $w$ の道を通過することを $c \leftarrow c+xw$ として正しく遷移できます。

地点 $i$ を通るという指定があるとき、そのような経路は地点 $1$ から地点 $i$ 、地点 $i$ から地点 $N$ の部分に分けられます。よってこの $2$ つの範囲で動的計画法を行い、その結果 $(x_1,c_1)$ , $(x_2,c_2)$ から答えを $x_1c_2+x_2c_1$ として計算できます。

地点 $1$ からと地点 $N$ から動的計画法を $1$ 回ずつ行うことで必要な結果は得られるため、計算量は $O(N^2)$ になります。しかし、 $N$ はかなり小さいので、 $O(N^4)$ くらいなら大丈夫です。

問題9 倉庫番ロボット / Warehouse Robot

問題文

最短経路を構成しうる要素をできるだけ削って列挙し、ダイクストラ法を用いればよさそうです。

まず、棚の境界のうち頂点以外からはじめて棚から離れるような動きは不要です。図のように、頂点から離れ始めたほうが短い経路になります。

また、 $1$ 回の直線移動で $x$ 座標も $y$ 座標も $2$ 以上変化するような移動は考えなくてよいです。そのような移動のうち有効なものは斜め $45$ 度の移動のみですが、これは分割できます。

よって、最短経路を構成しうる経路は、考える座標の最大値 $N$ に対して $O(N^3)$ 個の経路に絞れることがわかりました。この経路を列挙し、ダイクストラ法を行えば必要な経路長が得られます。

全体の計算量は $O(N^3 \log N)$ です。

問題10 Copy and Sum

問題文

更新ありの区間和クエリなので、まずセグメント木が良さそうに見えます。今回は実際に遅延セグメント木で処理できます。

ノードの集約値は実際の総和のみ持ちます。遅延評価の情報は「 $B$ のどこからどこまでをコピーしてくるか」で管理します。伝播するときには指定範囲を半分ずつに分けます。遅延評価の適用は $B$ の累積和を参照すれば高速です。

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

問題11 パスポート / Passport

問題文

文字列の辞書順比較や連結が一瞬でできるとするならば、番号の大きい国から貪欲な動的計画法で計算できます（つまり、最も辞書順で小さいもの以外は破棄）。ローリングハッシュを用いることで実現可能（らしい）です。全体の計算量は $O((N+M) \log N)$ です。

また、平衡二分探索木を用いても処理可能です。貪欲な動的計画法で得た文字列すべてを（暗に）辞書順で比較した順序を平衡二分探索木で管理します。文字列を追加するとき、二分探索より $O( \log N)$ 回の比較が必要です。各比較は、先頭 $1$ 文字のみ実際に比較すれば、残りは動的計画法ですでに現れた文字列ですから、平衡二分探索木の操作で比較可能です。全体の計算量は $O((N+M) (\log N)^2)$ です。

問題12 色付き山小屋 / Coloured Mountain Hut

問題文

色ごとにまとめて計算するのがよいです。色 $i$ の小屋の個数を $K_i$ とし、これに対する処理をサイズ $K_i$ のクエリとみなします。

解法1（木の圧縮）

計算量を $O(N)$ として解きます。

指定された頂点たちの最小共通祖先関係を保って木を圧縮してできる補助的な木 を計算します。 cf: ア辞典 https://dic.kimiyuki.net/auxiliary-tree

辺に重みがつく代わりに、頂点数が $O(K_i)$ になります。この木上なら全方位木 DP を行えます。全方位木 DP は次の記事 https://algo-logic.info/tree-dp/ を参照。

よほどでなければ、 LCA の計算に $O( \log N)$ 時間を許したり、一般的なソートアルゴリズムを用いたほうがこの問題に対しては高速です。

解法2（重心分解）

重心分解を用いて、計算量を $O(N \log N)$ として解きます。

頂点 $i$ について計算するとき、頂点 $k$ $(k \lt i)$ による寄与と頂点 $k$ $(i \lt k)$ による寄与に分割します。すると、 incremental な問題を $2$ 回解くことに帰着されます。このとき、まったく同じ意味の問題が codeforces blog で解説されています。 cf : https://codeforces.com/blog/entry/81661

解法3（パスクエリ）

解法2 の incremental な問題をパスクエリに帰着することで、

  • heavy light decomposition を用いて計算量 $O(N (\log N)^2)$
  • link cut tree を用いて計算量 $O(N \log N)$

で解きます。

根付き木において、山小屋間の経路長は両端点の深さと LCA の深さから計算できることに注意し、 LCA $g$ を固定することを考えます。山小屋追加クエリでは、頂点が $g$ またはその子孫であればその頂点から $g$ までの距離を管理します。山小屋削除クエリでは、管理している値たちの最小値から答えを求めます。

よって、頂点 $v$ の深さを $d(v)$ 、管理する値を $a(v)$ とすると、問題は

  • 初期化： $a(v) \leftarrow \infty$
  • 追加( $v$ )：頂点 $v$ から根までのパス上の頂点 $u$ について $a(u) \leftarrow \min \lbrace a(u),d(v) \rbrace$
  • クエリ( $v$ )：頂点 $v$ から根までのパス上の頂点 $u$ において $a(u)-2d(u)+d(v)$ の最小値を求める
  • ロールバック：初期化状態に戻す

というクエリの問題になります。これは heavy light decomposition とセグメント木で処理できます。

タイトルとURLをコピーしました