競プロ参戦記 第11回「全列挙」 エデュフォ50 [ABCD]
エデュフォに参戦(？)しました。C問題にひたすら時間を費やして一つも提出できず、結果的にはゼロ完です。
そういうわけで参戦記というより練習記です。Dまで解説を書いていきます。問題概要は翻訳ではなく、私が簡潔に再構成したものです。
Educational Codeforces Round #50
問題リスト：
A. Function Height
問題概要：(なんかめちゃくちゃ長い)
簡単に説明すると、まず N 個の山が与えられます。はじめはいずれも高さ 0 です。いずれかの山の高さを 1 大きくする、という操作を K 回行うとき、最も高い山の高さの最小値はいくつでしょうか。
K/N の切り上げです。
Rust の整数の割り算は切り下げですが、整数の切り上げは (K + N - 1) / N と書くのがシンプルです。
提出：
B. Diagonal Walking v.2
問題概要：無限平面の格子点上を動く点 P がある。上下左右の四方向、または右上・右下・左上・左下の斜め四方向の隣の格子点に移動するのを1ステップと数える。この点が原点から点 (x, y) にちょうど k ステップで移動できるか判定せよ。移動できるなら、上下左右への移動回数の最小値を求めよ。
こういう問題のお約束みたいなものですが、一般性を失うことなく点 (x, y) は第一象限にあると仮定できます。というのも、もし第二象限にあるなら、平面全体を左右反転して考えればいいからです。上下の反転や斜めの反転 (直線 y=x を軸とする反転) もすれば 0≤y≤x にできます。
今回、移動する方向の順番は関係ないようです。
まず、移動可能かはさておき、上下左右の移動回数の最小化を考えました。具体例を確かめているうちに、上下左右の移動を3回以上行うのは最適でないことに気づきました。例えば →→→ は右下・右上・右と同じ移動でありながら、上下左右の移動回数を節約できます。同様に →→↑ = 右上・右下・上 などもいえます。
そういうわけで上下左右の移動はたかだか2回。じゃあ全列挙してしまえ。
後は、一定回数の斜め移動だけで原点から点 (x, y) にたどり着くか判定すればOK。
右上へ a 回、右下へ b 回、左上へ c 回、左下へ d 回移動するとしましょう。野生の勘により d = 0 とします。たぶん左下に進まない最適解がありそう。到達の条件を式で書くと：
k = a + b + c
x = a + b - c
y = a - b + c
という連立方程式です。これが解を持つかどうかは行列式を使って判定できたと思いますが記憶にないのでガッと計算すると、 k, x, y が偶数で一定の大小関係を持つ必要があることが分かります。(斜め移動の様子を思い浮かべれば、わざわざ連立方程式を書かなくても分かるかも？)
提出：
C. Classy Numbers
問題概要：0でない桁が3つ以下である非負整数を classy と呼ぶことにする。L 以上 R 以下の classy な整数を数えよ。(1 ≤ L ≤ R ≤ 10^18)
「桁」に関して一定の性質を持つ数を数え上げる問題は、桁DPで解くものです。(こういう決めつけはよくない。)
桁DPの解説はこちらの記事が参考になります：
問題文は L 以上 R 以下を数えろといっていますが、L = 0 でいいです。L-1 以下の classy 整数を数えて引けば、最終結果が求まりますから。
さて、動的計画法は DP 表を設計すれば勝ちです。まず桁数 i を用意します。必要ないことが多いですが、必要なさそうなら後で消すことにします。次に、問題の主旨である「0でない桁の個数」 r も数えておきます。そして、「R以下」かどうかを判定するため、上位桁が R と一致しているかも記録します。
今回はこれでいきましょう。
dp[i][r][0] = n ⇔ 上から i 桁に含まれる 0 でない桁の個数が r に等しい、R 未満の整数の個数が n
dp[i][r][1] = n: 同上、ただしこちらは「R に等しい可能性がある整数」の個数
厳密には整数の個数ではなく整数のパターンの個数ですが、それはそれとして。
遷移については、立てる数が 0 かどうか、R の i 桁目と等しいかどうか、を考えて数えていきます。詳細はコード。
提出：
明らかに牛刀解法でした。こんなの書いてたら時間なくなります。
冷静になって制約 R ≤ 10^18 に注目します。これは符号つき64ビット整数の最大値にぎりぎり収まる桁数なので、制約ではよく見る数字です。
さて、この範囲の classy 整数は何通りあるでしょうか？
概算すると、18桁のうち3つの桁を選んでそれぞれを 1~9 で埋める場合の数を考えて、C(18, 3) * 9^3 ぐらい (*)。おおよそ60万通りです。メモリに乗ります。
したがって、classy 整数を全列挙してから L 以上 R 以下のものを数える、という解法があります。単純な深さ優先探索なので簡潔に書けます。
(*): 0でない桁が2桁以下のケースは十分に少ないので無視しました。
D. Vasya and Arrays
問題概要：2つの数列 A, B が与えられる。数列からある区間を取り除き、代わりにその区間に含まれていた要素の総和を挿入する、という操作を考える。数列 A, B にこれらの操作を繰り返し適用して、数列を一致させられるか判定せよ。できるなら、その一致した数列の長さの最大値を求めよ。
例えば数列 (1, 1, 2, 3, 5) の区間に操作を適用すると、 1,2,3 を削除して 1+2+3 = 6 を挿入し、結果的に (1, 6, 5) になる、といった具合です。
数列の左端の数に注目します。A=(1, ...), B = (3, ...) のように左端の数が一致しないなら、どちらかの左端の要素は操作対象の区間に含める必要があります。A=(1, 2, ...), B=(2, 1, ...) のように、左端の区間に操作を行って左端の数を揃えられるなら、この操作はやるべきですし、最終的な数列の長さを最大化するにはなるべく小さい区間を操作したほうがよいです。
したがって、左端から区間を広げていき、和が一致するところで両方の数列に操作を行うのがベストです。後は再帰的に解けます。
提出：
おわりに
探索範囲が小さい問題は全列挙で解いてしまえ、というのが今回の教訓でした。残りの問題はまたいつか……
この記事が気に入ったらサポートをしてみませんか？