【Ruby】GCJ2021予選のB問題, C問題の解説
最初に
Google社主催の世界的なプログラミングコンテストの予選を通過したので、
そのB問題・C問題の簡単な解説の記事です。
最近は競プロをやっていませんでしたが、
「Google社主催の世界的なプログラミングコンテストの予選を通過した」と言いたいがために、
英語を読んだりするのが面倒だなと思いつつGCJの予選の問題のB問題・C問題を解きました。
正確にはB問題・C問題じゃなくて「Moons and Umbrellas」「Reversort Engineering」というタイトルの問題。
A問題を解いてないないのは、
予選を通過するための条件が30ポイントで、
B問題・C問題を解けば30ポイントを達成できるので、
必要最小限に解いたためです。
問題
Qualification Round 2021 - Code Jam
実際のコンテスト会場が、こちらです。
問題の概要(日本語)
Google Code Jam 2021 Qualification Round 問題文和訳 - HackMD
日本語での簡単な概要を書いて下さってます。
問題の解説・考え方
B問題 Moons and Umbrellas
問題の概要等
Hidden(コンテスト後に合否がわかる)の+αの方は解いてないです。
以下、Hiddenのコストがマイナスの場合は、考えないものとします。
CJ?の3種類の文字で構成される文字列が与えれ、?にはCかJのどちらかを入れる。
CJでX、JCでYのコストがかかるので、コストが最小になるように?を埋めたときの最小スコアを求める。
考察など
サンプルなどを試して、実験する。
簡単な文字列で考えてみる。
まず?のないテストケースの「4 2 CJCJ」だと、CJが2つあり、JCが1つある。
そのため、4 * 2つ + 2 * 1つ = 10がコストとなる。
次に?が1つのテストケース「1 3 C?J」で考える。
このとき、?にCを入れてもJを入れても、CJが1つ生じるので、コストは1 * 1つ = 1となる。
他のケースも考えてみる。
「??C」というケースだと、全部Cを入れてしまえば、CJもJCも生じないので、コスト0のものが作れる。
逆に、Jを入れてしまうと、JからCに切り替わるタイミングが作れてしまい、コストがかかる。
(ここで、文字列の両端にある連続する?の部分は切り落として無視してよさそうとわかる)
左から見ていったときに、JからCに切り替わる部分やJからCに切り替わるタイミングでコストが生じる。
そのため、Jの連続部分やCの連続部分は、1つのCや1つのJに置き換えて良さそう。
C?????Cのように同じ種類の文字で挟まれたケースでは、同じ文字を埋めてしまえば、コストは生じない。
逆に、C?????Jのようなケースだと、どこかでCからJに切り替わるタイミングが1つ生じる。
?????の連続部分も、切り替わる箇所は多くても1つだけなので、?も圧縮して考えても同じ。
Rubyだと、文字列にはsqueezeというメソッドがあり、連続部分を圧縮した文字列を作ります。
s = "??J???CCCJJJ???"
s.squeeze!("CJ?")
p s # "?J?CJ?"
(よく考えると、この問題ではsqueezeの引数は不要だった)
圧縮しなくても解けると思いますが、先に圧縮してしまうと問題が単純になっていいと思います。
圧縮後のコストの求め方
そして、圧縮した上で(さらに両端の?を取り除いて)、
CJもしくはJCの部分と、CとJに挟まれた?で文字が切り替わる部分で、別々のコストを求めました。
色々なやり方があると思いますが、CJもしくはJCの部分を単独で求めるとき、
each_consを使って2つずつ見てくと、コードがスッキリする気がします。
実際のコード
testcase_count = gets.to_s.to_i
(1..testcase_count).each do |testcase_number|
x, y, s = gets.to_s.split
x = x.to_i
y = y.to_i
s.squeeze!('CJ?')
s = s.chars
s.shift if s[0] == '?'
s.pop if s[-1] == '?'
ans = 0
s.each_cons(2) do |c1, c2|
if c1 == 'C' && c2 == 'J'
ans += x
elsif c1 == 'J' && c2 == 'C'
ans += y
end
end
s.each_with_index do |c, i|
if c == '?'
if s[i - 1] == 'C' && s[i + 1] == 'J'
ans += x
elsif s[i - 1] == 'J' && s[i + 1] == 'C'
ans += y
end
end
end
puts "Case ##{testcase_number}: #{ans}"
end
ここで、squeeze!のあとに、charsで文字の配列にしてるのは、
文字列を操作するより、配列にした方が、速いことが多く、
またeach_consやeach_with_indexなどが使え扱いやすいためです。
出力はコストだけでなく、決まった形式で出力する必要があるので、注意しましょう。
C問題 Reversort Engineering
問題の概要
構築問題。
ひっくり返してソートしていき、そのときひっくり返す長さの総和がコストとなる。
1からNの順列をソートするときに、コストがCになるような、1からNの順列を(構築して)答えよ、という問題。
詳しくは、問題Aと合わせて、元の本文を(翻訳するなりして)読んで欲しいです。
サンプルのテストケースで確かめると理解しやすかったです。
考察
考察：構築が不可能なケースとは
まず、ソート済みの順列であっても、
1つの要素をひっくり返すというプロセスがN - 1回あるので、N - 1のコストが最低かかります。
もし、これよりも低いコストがかかるような列は作れません。IMPOSSIBLEです。
反対に、最大コストがかかるケースを考えてみます。
どのような順列であっても、ひっくり返すプロセスがN - 1回あります。
1から5の順列で簡単に実験したら、それぞれのプロセスで5, 4, 3, 2のコストがかかる順列を構築できました。
アバウトな説明ですが、N個の順列で、最大コストはN, N - 1, N - 2, ……, 2の総和になりそうです。
等差数列の総和で単純に(2 + N) * (N - 1) / 2が最大コストで、これよりもコストがかかる順列は作れません。IMPOSSIBLEです。
まず、コード上で、これらの不可能なIMPOSSIBLEケースを外します。
考察：どのように順列を構築できるか
次に、上記の不可能なケース以外だと、どのように順列を作れるか考えてみます。
例えば、サンプルの「4 6」のケースだと、1から4の順列でコスト6のソートをさせたいです。
1から4の順列のソートは最低3かかります。わかりやすくするために、最低コストの分は割り引いて、6から3を引いて、あと3のコストをどの時点で使う必要があるか考えてみます。ひっくり返す長さnより1少ないコストが生じるものと置き換えて考えていきます。
最低コストを割り引くと、それぞれの逆にするプロセスで、3~0, 2~0, 1~0のコストで変動できそうです。
どのひっくり返すプロセスにコストを割り当てるか考えたときに、少ない方から考えると調整できそうです。それに、プロセスの逆から、つまり、ソート済みの方から考える方がスタート地点で定まってよさそうです。
とりあえず、逆向きから出来るだけ大きくひっくり返すようにして、最後に微調整を加える方向でいきます。
1から4の順列のソート済みのケースは、1, 2, 3, 4です。
調整後のちょうど使うべきコストが3です。
1, 2, 3, 4
↓ 調整後コスト1(調整前コスト2 == ひっくり返す長さ)
1, 2, 4, 3
↓ 調整後コスト2(調整前コスト3 == ひっくり返す長さ)
1, 3, 4, 2 ※ここでソートすべきコスト使いきった。
↓ 調整後コスト0(調整前コスト1 == ひっくり返す長さ)
1, 3, 4, 2
うまく作れそうです。
この例では、ちょうどコストを使い切りましたが、コストを使いからない場合もあるので、そこで調整が必要です。実際のコードでは、調整前の残コストとひっくり返せる最大長の小さい方を求めることで、コストが中途半端に残ったときの微調整に対応してます。
実際のコード
ACできるコードは以下です。
testcase_count = gets.to_s.to_i
(1..testcase_count).each do |testcase_number|
n, c = gets.to_s.split.map(&:to_i)
min = n - 1
max = (2 + n) * (n - 1) / 2
if c < min || max < c
puts "Case ##{testcase_number}: IMPOSSIBLE"
next
end
c -= (n - 1)
a = (1..n).to_a
rs = 2
i = n - 2
while 0 <= i && 0 < c
s = [rs, c + 1].min
c -= (s - 1)
a[i, s] = a[i, s].reverse
rs += 1
i -= 1
end
puts "Case ##{testcase_number}: #{a.join(" ")}"
end
ちょっとコードは、コストのところで色々と微調整してて、わかりにくいですね。
iがひっくり返し始める位置で、cが調整後の残コストで、rsがひっくり返せる最大長(調整前のコスト)です。sが実際にひっくり返す長さ。
何度もひっくり返すのは制限時間に不安を少し感じましたが、順列の大きさやテストケース数が少ないので、ソート済みの順列から実際に配列の一部分を逆順にしてもACできました。
Rubyでは、一部分の配列を逆順にしたいときは、a[i, s] = a[i, s].reverseのように書けるようです。比較的シンプルに書けて、便利。
余談
IMPOSSIBLEのような出力をするときは、typoしないようにコピペするといい気がします。
最後に
解答の方針をだすことは考え始めると比較的スンナリいくのですが、その割には実装が面倒だったかなという印象です。
AtCoderの緑色・水色以上であって、英語の問題をなんとか出来て、考えれば予選を通過できるように思います。
あと、難しければGCJの予選は相談などがOKらしいので、相談するとよさそう。
Discussion