ARC144 参加記 (兼 A,B,Cの雑な解説)

はじめに

ABCに比べてARCは考察のウェイトが重めで、特定のアルゴを知っているか否か、というより、解法に至るプロセスが大事だと考えている。そのあたりの整理の意味を含めて、自分が解けた問題まで、当日のプロセスを振り返ってみる。
例によって形式的な書き方はあまりしない（できない）ので、そういうのが欲しい方は公式解説を読んでほしい。

最初は解説のつもりで書いていたが、あまりにも内容が雑なので変えた。

A. Digit Sum of 2x

前提として、ARCのA問題は、ぱっと見何言ってんの？って思うぐらいに複雑な問題に見えて、法則に気づくと実装も楽なケースが多い。そういう意味で、問題をきちんと理解し、法則に気づけるかどうかというのがポイントだと思う。
この点を踏まえて、問題を整理していく。

f(x)は、xの各桁の数の合計であって、この合計値がNとして与えられている。

このxは、実験してみると結構自由にとれることがわかる。例えば、

f(9)=f(333)=f(111111111)=9

という感じになる。

さて、この自由にとれるxを二倍にしたときに最大となるMを求める、
というお題に対して対応していく。

2倍になったときに最大になっている、あるいは、最大にならないxを考えてみる。
とりあえず小さい数字から実験する。

f(1)=1 => f(2)=2
f(2)=2 => f(4)=4
f(3)=3 => f(6)=6
f(4)=4 => f(8)=8
f(5)=5 => f(10)=1
f(6)=6 => f(12)=3
f(7)=7 => f(14)=5
f(8)=8 => f(16)=7
f(9)=9 => f(18)=9

こうしてみてみると、4まではf(2x)=2f(x)になっているが、5以降はf(2*x)<2*f(x)になってしまっている。より具体的に言えば、2倍にしてしまったときに桁上がりが発生した場合は、2倍を下回ってしまう。
これは数字が大きい場合でも、各桁で桁上がりが発生してしまうようなxを選んでしまうと各桁が2倍を達成できなくなる。

これら事実から、M=2*N、xは各桁が0~4で表されることがわかる。

あとはこの条件を満たすxのうち、最小のものを決める。まず、とにかく桁数を小さくしたいので、xの各桁の取りうる最大値=4で埋めていく。すなわち、"4"*(N//4)である。そのうえで、余りは4より小さいので、先頭につければいい。

B. Gift Tax

「ARCは考察が重いと言ったな？あれは嘘だ。」

と言うぐらい、問題文に使うべきアルゴリズムが書いてある問題である。最小値の最大値というのは二分探索が想定解となるときのよくある表記方法で、こう書いてあったらまず二分探索を疑っていい。アルゴリズムを覚えるときは、その中身と同時に、どういう問題で出るのかは把握しておこう。

というのを何かで読んだことがある。
さて、私はそこに気づかなかったので（は？）、考察の流れを振り返ってみる。

問題の設定として、最小値を大きくしたいので、（あえて曖昧な表現をすると）雰囲気としてはなるべく全体を大きくしたい方向である。
ここで、出来る操作は「a増やして、b減らす」なわけだが、a<bなので、操作をすればするほど全体の合計値は小さくなっていく。
したがって、なるべく無駄に操作はしたくない。
例えば、A1<A2<A3だとして、A1を増やしたい時に下記のような操作をすると、

操作1: A1'=A1+a A2'=A2-b
操作2: A2''=A2'+a A3'=A3-b
結果: A1'=A1+a, A2''=A2+a-b, A3'=A3-b

となるがa<bなので、A2''<A2になる。A1>A2''なら最小値が減少してしまう。
従い、

操作1': A1'=A1+b A3'=A3-b
結果: A1'=A1+b A2=A2 A3'=A3-b

の方が無駄がなく、同じ要素を増加・減少させるような操作は回避すべきことがわかる。

この無駄を回避するためには、「操作ごとに操作対象の要素を決める」というよりは、
「最初から増加させる要素、減少させる要素を決めておく」のがよさそうである。

では、この増加させる要素、減少させる要素を決めてしまいたいが、
これは到達したいゴールを決めておいて、ゴールより小さい要素・大きい要素という決めるのがよい。
下記の図でいうところを赤線を決めて、赤線より下のものを増やす・上のものを減らす、というイメージだ。
（ソートされているが別にソートしてなくてもいい）

実はこのゴールは問題の解そのものである。
この解の探し方は試していくのがよい。適当にゴールを決めて、そのゴールを達成できればもっとゴールを切り上げればいいし、達成できないなら切り下げる。

ここまでくると二分探索を発想しやすいんじゃないかと思う。

探索する区間は全要素の最小値から全要素の最大値+1、
実現できるかどうかの判断は、実は増やす操作と減らす操作は独立にできるので、

(ゴールに以上にするまでに必要な増やす操作の回数)-(ゴールを満たす限りに減らせる回数)

が0回以上になればいい。これはゴールからの差をaなりbなりで割ればいい。
あとは、floorとceilに気を付けて実装すればOK。

C. K Derangement

この問題の厄介なところは、サンプルに出てこない辞書順最小の法則が存在していて、
それを見つける必要があることだと思う。私は手元で実験しつつWAで（は？）確認していった。

さて問題を眺めていると、要は添え字の位置から一定程度離れた位置の数字を選べばいいと書いてある。

まず存在しないケースを考えてみる。
条件に対して一番苦しそうなのは真ん中にある数字である。
端までもっていっても、N/2しか離すことができない。よってN/2<Kなら存在しなさそうである。

他に条件があるかはぱっと見わからなかったが、入出力例を見ていると、1~Nの配列をK回巡回シフトしていることがわかる。
いくつか実験をしてとりあえずK回巡回シフトさせれば解は存在しそうだったので、上記条件以外に解が存在しないケースはなさそうである。

提出した。WAだった。
https://atcoder.jp/contests/arc144/submissions/33263778

さて問題文をよく読むと、辞書順最小と書いてある。
よく考えたら600点問題だしこんなに簡単なわけはなかった。もう少し真面目に実験してみる。

Nに対して相対的にKが大きい時には制約が厳しいイメージになり、巡回シフトしかなさそうだが、
逆にKが小さいときは制約的に緩い方向になる。とするとこの辺りをもう少し重点的に考えてほうがよい。

このような可能性に気づいた時点で、DFS当たりで愚直解法をコーディングして試すのが良いだろう。
下記みたいな実装をしてあげるとN=12ぐらいは割と現実的な時間で終わる。

python

from itertools import permutations

N, K = map(int, input().split())

ret = (N,) * N
for pat in permutations(range(1, N + 1)):
    ok_flag = True
    for i, p in enumerate(pat):
        if abs(p - (i + 1)) < K:
            ok_flag = False
            break
    if ok_flag and ret > pat:
        ret = pat
print(*ret)

※ARC-Cに取り組む人は愚直解法はある程度さらっとかけると思っている。
　ここに苦労するなら悪いことは言わないので難易度を落とした問題で数をこなして慣れるのがいいと思う。
　ARC-Cを考えている時間より、それらを練習する時間のほうがレートがは上がる。
　ただ競プロはぱちんこなので、やっぱ天井上がるほうに賭けるほうが楽しいよね？

さて、残念ながら当時の私にはその発想はなかったので、ひたすら手元で書いていった。

N=4 K=1: 2 1  4 3
N=4 K=2: 3 4 1 2
N=8 K=2: 3 4 1 2  7 8 5 6

眺めていると、2K毎にブロックがあって、その中で前半K個と後半K個をスワップをさせていることが分かる。
もう少し考えてみると制約がなければ、1..Nまでの配列が辞書順最初であって、ここからなるべく離さないほうがよく、

• スワップさせるにしてもなるべく小さい単位でさせるほうがいいこと
• 冒頭の存在しない条件から、K*2個要素があれば、条件を満たす部分列は生成できること

から考えると自然な条件ではある。
よって、前のほうから2K個の塊毎にスワップさせて、最後の塊が2Kを下回りそうなら、一つ前の塊とまとめて巡回させる。

と発想して提出した。WAだった。

もう少し冷静になろう。これぐらいの難易度なら300~400点ぐらいで済みそうである。
気分転換に順位表を眺めると、赤や橙コーダでもC問題でWAをそこそこ出している。

WAを出すと「解法の方針がまるっきり違う」可能性を考えがちだが、
上記事実から、「上位勢でも気づきづらいケースが存在していて、自分もそのケースに気づけてない」のではないか、と仮説を立てて、
現行の方針を継続する判断をした。（といいつつここでめっちゃ時間を使っている。）

まあ、魔法のようにそのケースを思いつけるわけでもないので、
実験する値を大きくして眺めることを続けていく。

N=9  K=3: 4 5 6 7 8 9  1 2 3 
N=10 K=3: 4 5 6  1  8 9 10   2 3  7
N=11 K=3: 4 5 6  1 2  9 10 11  3  7 8
N=12 K=3: 4 5 6  1 2 3  10 11 12  7 8 9

こうして見てみると、先ほど提出した発想とは特に後半で乖離があることに気づく。
2K毎の塊が作れない場合でも、残りの個数で巡回シフトさせるよりうまい方法があるようである。
先ほどの提出だと2K毎に塊を作っていくので、最後に残る要素数は3K個から4K個である。

3K個は全体を巡回シフト、4K個は2K個ごとにスワップしているので、想定通りだが、
3K<x<4Kを満たすx個のときは想定外の分割が発生していることが分かる。
一方で、4 5 6はK個の塊だし、最後からK個の要素(8-9-10とか10-11-12)は塊のままである。
であれば、あとは残りの部分をよしなにしてあげればいい。

ポイントは後ろのK個の要素を手前に持ってきているので、逆にK個なるべく大きい数字から持ってくる必要がある、ということである。

という感じで実装して提出したらACできた。めでたしめでたし。

今回の問題で学ぶべきこと

• とりあえず実験して法則のとっかかりを探す
• 最大値の最小値は2分探索のド典型
• 同時に行う操作を独立にして考える
• 5分のペナルティの価値を考えて、詰まるぐらいなら間違いの確認・思考の切り替えのために提出する
• 順位表から読み取れる事実がないか考える

終わりに

整理しながら、数理的な考察というよりも自分は割と雰囲気・イメージで解いているのがよく分かった。
もう少し図を入れたかったが力尽きた。厳密かつ分かりやすい解説を書いている人マジ半端ない。