ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder AGC022-C Remainder Game 思考メモ

概要

以下の記事に乗っかって、私が「Remainder Game」を解いたときの方針について書いてみます。

競技プログラミングの強みと「典型力」について - chokudaiのブログ

AtCoder Grand Contest 022 C - Remainder Game を解くときに考えたこと - pepsin-amylaseのブログ

私はこのコンテスト本番に参加してないので(AGC022の翌日にAtCoder登録しました)、後からのんびり解きました。時間はお昼ご飯タイム込みで100分くらいかかっています。

公式解説PDFではグラフ理論を使っていますが、私の解答では使っていません。ただ結局はグラフ探索っぽいDPになっているので、本質的にはそんなに違わないのかもしれません。

提出コード

Submission #2324376 - AtCoder Grand Contest 022

Rubyです。この問題をRubyで通しているの、これを書いている時点で私だけでした…

Rubyで95msなので、わりと速い?かもしれません。

考察

問題文の最もメインとなる記述は以下です。

正の整数 k を選ぶ。数列のそれぞれの要素 v について、アオキは v を「vk で割った余り」に置き換えるか、v をそのままにするかを選べる。この一連の操作のコストは(書き換えた要素の数によらず)2^{k} である。

整数の剰余の性質からすぐに分かることは以下です。

  • v より大きな k で割ることでは、数字は変化しない。
  • v 以下の k で割った余りは、vより小さく、k より小さい。

なので、ある数 ij に変化させようと思うと、i より大きな k を用いても意味がありません。また、今まで選んできた k 以上の数を用いても意味がありません。

言い換えると、選ぶ k の列としては、i 以下の数からなる(狭義の)単調減少数列のみを考えれば十分であることがわかります。

というわけで、ij に変化させることができる手続きの列を、必要な全ての i, j について列挙してしまおうと考えました。入力となる数は50以下とそこまで大きくないので、全列挙でも間に合う可能性があると考えました。余りを取る手続きは数を小さいほうに遷移させていくので、小さい数について求めた手続き列が、大きい数についての計算で使えます。動的計画法(DP)を使います。

というところでまずはDPの実装を始めました。コストについて考えるのは後回しにします。

DPを書く

# dp[i][j]: iをjに変化させることができる手続き列の集合。
# 例えば3を0にするには、3%1=0, 3%3=0, 3%2=1,1%1=0の3つがあるので
# dp[3][0] = [[1],  [3], [2, 1]] となる
# (ただし、実際には[2, 1]は「無駄」なので含まない。本文参照)
# 手続きが存在しない/見つかっていない場合はdp[i][j] = nilとする
dp = Array.new(max_a+1){Array.new(max_a+1)}
 
(0..max_a).each do |i|
    dp[i][i] = [[]]
end

# dp[i%k][j]を使ってdp[i][j]を更新する。
# iに手続きkを行ったあとdp[i%k][j]に含まれる手続き列を行えば、iをjに変化させることができる。
# i>j かつ i>=k の範囲しか意味を持たないので、ループ範囲を絞れる 
(1..max_a).each do |i|
    (0..i-1).each do |j|
        (1..i).each do |k|
            if dp[i%k][j]
                dp[i][j] ||= []
                dp[i%k][j].each do |pro|
                    dp[i][j].push([k] + pro) unless dp[i][j].include?(pro)
                end
            end
        end
    end
end

dp の定義とループでやっていることについては、コード中のコメントで簡単に補足しています。

このDPにおいては「無駄なパターンを数え上げないこと」が大事で、無駄なパターンが増えるとどんどん後のほうでパターン数が爆発していきます。全列挙と言ってはいますが、明らかに無駄なものは存在します。それを弾いているのが以下のコードです。

dp[i%k][j].each do |pro|
  dp[i][j].push([k] + pro) unless dp[i][j].include?(pro) # ここ
end

prodp[i%k][j] に含まれる手続き列で、これの先頭に k を加えれば dp[i][j] の要素が出来上がります。ただ、k を加えなくても、元の手続き列で ij に変化させられる場合、この k を含んだパターンを使うことはコストの無駄なので、加えなくて良いです。

実際の例を挙げます。例えば3を0にするには、3%1=0 3%3=0 3%2=1,1%1=0 という手続き列のパターンがあり、これを全て含めると dp[3][0] = [[1], [3], [2, 1]] となります。ただし、[1] だけで十分なのに、[2, 1] とわざわざ2を使うのは無駄です。上記の処理では、こういったものを弾いています。

最初はこの処理を入れておらず、無駄にパターンが増大しているせいで処理時間とメモリを大量に消費していました。無駄が多いことは、実際に dp の中身をデバッグ出力しているうちに気付きました。

10以下の範囲で列挙した dp は、以下のようになります。

f:id:betrue12:20180424221143p:plain

分かりやすいものだと、dp[6][0] = [[1], [2], [3], [6]] です。6の約数のどれで割っても余りが0になります。この他にも例えば [4, 2] なども条件を満たしますが、[2] だけで十分なので入っていません。これは先述の「無駄なパターン」に該当します。

ところで、今回パターンの全列挙を行っているのは、この1回のDPで求めた結果を最後まで使うためです。対して公式解説PDFの方法では、部分問題を何度も解くかわりに、1回の部分問題はグラフの到達可能性という簡単な問題となっています。

実際の入力から最適コストを計算

DPによって、ij に変化させることができる手続きの列を列挙できました。というところで、実際の入力を扱います。入力 a, b のペアそれぞれを、手続きの列にマッピングします。

arr_of_procs = N.times.map{|i| dp[a[i]][b[i]]}

どれかのペアについて dp[a[i]][b[i]]nil である場合は、ab に変化させる手続き列が存在しないということなので、-1を出力して終了します。

ここからどのように最適コストを求めればよいか考えます。

手続き k のコストは 2^{k} です。これは、手続き k を行ったときのコストが、手続き 1, ..., k-1 のコスト合計より高いことを意味します。つまり、代わりに小さな数値をいくら使うことになろうとも、大きな数値は使いたくないわけです。

この考えのもとで、使う数を決めている部分が以下です。

use = 0
arr_of_procs.each do |procs|
    need = procs.map{|pro| pro.max}.min
    use = [need, use].max
end

minmax がごちゃごちゃして分かりにくいので…実例を挙げます。例えば、dp[13][2] = [[7, 4], [8, 3], [11]] です。これらの手続き列のうち、最もコストが低いのは [7, 4] です。要素の数に関わらず、最大値が一番小さい手続き列が、最もコストの小さいものになります。つまりこのペアにとっては、次に k=7 が選ばれることが最も嬉しいです。

各ペアについてこのような数を求めていき、その最大値を使う…というのが、上のコードでやっている処理です。

使う数が決まったら、コスト加算とともに、その k= use による手続きを行います。

if use > 0
    cost += 2**use
    arr_of_procs.each do |procs|
        procs.each do |pro|
            pro.delete(use)
        end
    end
end

実装コードでは、全ての手続き列から use を削除しています。ただ、a[i] %= use と置き換えて dp[a[i]][b[i]] を代入し直したほうが、分かりやすくて速いと思います…

これを繰り返していくと、いずれかの手続き列が [] になります。こうなると、そのペアについてはそれ以上の手続きは不要です。(手続きによって a, b の2つの数が一致したということを意味します。)なので、そのペアを取り除いていきます。全てのペアが取り除かれた時点で手続きは終了です。

arr_of_procs.length.times do |i|
    arr_of_procs[i] = nil if arr_of_procs[i].include?([])
end
arr_of_procs.compact!
break if arr_of_procs.length == 0

最後にコストを出力して終わりです。

さいごに

かなり長くなりました。読んでくださった方、ありがとうございました。

私自身、公式解説PDFだけだとなかなか理解が追いつかない問題も多く、思考過程や実装などを解説した他の方の文章は非常に助かっています。この文章も、誰かの参考になれば幸いです(実装が競技プログラミングではマイナーなRubyというのが申し訳ないですが…)