[AtCoder 参加感想] 2019/02/16:ABC 155

問題F（コンテスト後）→ ■

全体感想

言語アプデまで、atcoderの問題を解くのは控え中（アプデ後の環境で練習を重ねたい）。代わりに 最近は本を読んで勉強しつつ、環境構築とか、ライブラリのテストの環境とか、その辺の整備に興味を持っています。

ABCコンテストはレートもつかないので、今日はお試しにガラッと環境を変えてプレイしていました。今まで、作業ディレクトリの生成、実装コードのテスト・クリップボード貼り付けなどを自前実装でやっていましたが、online-judge-tools と atcoder-cli を導入。エディタも競プロ界の標準っぽさそうな、vscodeを（将来採用したいかは分からないけど）とりあえず試してみました。

いろいろ試したりしつつ問題Aから10分以上かかっていたりとのんびりペースです。最近のABCの様子なら十分間に合うかなと思っていたのですが、15分ほどタイムオーバーしてしまいました。

全完が2桁人数しかいないセットなら、全力で取り組んでみたかったところ。ちょっと間が悪かったですね。

問題A – Poor

3通り調べる。こんな方法をとってみました。

def is_poor(A, B, C):
    for _ in range(3):
        A, B, C = B, C, A
        if A == B != C:
            return True
    return False

「データを入れ替えて同じロジックを呼ぶ」は実装の簡略化としてたまに使えます。（グリッドに対して縦・横での計算が必要 → グリッドを転置して再計算する、など）

問題D – Pairs

最近のABCコンテストでも、類題はありました。

ABC 149-E （私の解説）

この問題の上位互換です。この問題を経験している前提がないと、普段のDよりも難しかったということでしょう。未だ解いていない方は、先にこちらを学習すると良いと思います。

やはり二分探索です。判定問題を解くために必要な課題は「定数 $c$ に対して $A_iA_j \leq c$ となる $(i,j)$ を数え上げよ」というものです。変更点は、2つです。

(1) $i < j$ という条件下での数え上げである。
(2) 掛け算で、負の数もあり。

(1) について考えましょう。ところで、過去問での経験があるように、順序制約のない $(i,j)$ の数え上げの方が簡単です。それを利用することを考えると、$i=j$ の場合の個数を引いて $2$ で割ればよいと分かります。「〇〇だと解ける」ということを知っておくことは、思考の材料として有用ですね。

(2) について考えましょう。もう $i < j$ は忘れてよいです。各 $i$ ごとに、$A_iA_j \leqq c$ となる $1\leq j\leq N$ を数えます。$i$ は固定しているわけなので、$a=A_i$ として落ち着いて $ax\leqq c$ を調べます。$a=0$ のときは 解なしまたは任意の $x$。$a > 0$ なら、$ax\leqq c\iff x\leqq \frac{c}{a}\iff \lfloor\frac{c}{a}\rfloor$ です。

$a < 0$ のときは、$ax\leqq c\iff (-a)x\geqq (-c)$ です。この否定をとると、$(-a)x < (-c)\iff (-a)x \leq (-c-1)\iff x\leq \lfloor\frac{-c-1}{-a}\rfloor$ となって、全体から $\lfloor\frac{-c-1}{-a}\rfloor$ 以下のものの個数を引けばよいと分かります。切り捨てとか切り上げとかややこしいので、私はこのくらいの式変形を計算用紙に書いて解きます。

符号で場合分けすることは思い至ると思いますが、$A_i$, $A_j$ 両方の符号を見始めると実装量が増えてややこしくなると思います。$1$ 次不等式を解くとき、$x$ の係数 $a$ の符号は重要ですが、$c$ の符号は気にしませんよね（これは中学数学です）。よって、$A_i$ の符号でのみ処理を分けて、あとはソート済配列における二分探索（あるいは尺取り）をすれば事足ります。

問題E – Payment

貪欲法解法

E : 繰り上がり条件は
s[i]>=6 || s[i]==5 && s[i+1]>=5
です

— tatyam (@tatyam_prime) February 16, 2020

わー、びっくり！証明していきましょう。

$f(3456) = \min\{f(345)+6, f(346)+4\}$ でしたが、$f(n), f(n+1)$ の差は計算せずとも高々 $1$ です。なぜなら、自分が 1円玉をひとつ増やすことで $f(345) + 1\geqq f(346)$ が、相手が 1 円玉をひとつ増やすことで $f(346) + 1\geqq f(345)$ が証明できるからです。

したがって、この場合には、$f(3456) = f(346) + 4$ としてしまうことができます。

このような観察をすると、順番に戦略を一意に決めていくことができてしまいます。$1$のが $5$ の場合以外は上と同様です。

$1$ の位が $5$ のときが厄介なのですが、$10$ の位も見ます。例えば下 2 桁が 35 なら、\[ f(100x+35) = \min\{f(10x+3)+5,f(10x+4)+5\} = \min\{f(x)+3+5,f(x)+4+5\} = f(x)+3+5\] となります。$f(10x+3)$ の計算では、上記のように、$1$ の位の戦略が確定することを利用しています。

下 $2$ 桁が $05,15,25,35,65,75,85,95$ なら同様の式変形でよいです。最後に \[\begin{align*}f(100x+45) &= \min\{f(10x+4)+5,f(10x+5)+5\}\\ &= \min\{f(x)+4+5,\min\{f(x)+5+5,f(x+1)+5+5\}\}\\ &= \min\{f(x)+9,f(x)+10,f(x+1)+10\}=f(x)+9,\\f(100x+55) &= \min\{f(10x+5)+5,f(10x+6)+5\}\\&=\min\{\min\{f(x)+5+5,f(x+1)+5+5\},f(x+1)+4+5\}\\&=\min\{f(x)+10,f(x+1)+9\}=f(x+1)+9.\end{align*}\]

となって、この場合にも戦略を確定してしまってよいことが示されました。

問題 F – Perils in Parallel

ソートしたりすると、区間がそれぞれ $L$ 番目・$R$ 番目の間の爆弾に対する操作としてよいです。

課題：使える $(L,R)$ たちと数列 $B$ が与えられる。はじめ $B$ は全て $0$ であるとする。「$b_L,\ldots,b_R$ すべてに一斉に $1$ 加える（ただし $\pmod{2}$ ）という操作で所望の状態にせよ。

区間加算という操作を、上手く疎な処理に分解する扱う方法に、imos法があります。$[L,R]$ に一斉に $1$ を加える操作を繰り返すときに、「$a_{L}$ に $1$を、$a_{R+1}$ に $-1$を加える」としておきます。全ての操作が終わったあとに累積和をとれば、全部の操作をやったことになります。なお、今回は $\pmod{2}$ なので、$-1$ を加えることは $1$ を加えることと読み替えられます。

数列 $C$ を $B$ の差分として、次の課題に帰着されます。

課題：使える $(L,R)$ たちと数列 $C$ が与えられる。はじめ $C$ は全て $0$ であるとする。「$c_L$ と $c_R$ に $1$ を加える」操作で、数列 $C$ を所望の状態にせよ。

これを、「$L,R$ 間に辺を貼ったグラフを考える」ことで解決するのは、私は過去問で経験がありました。

課題：グラフ $G=(V,E)$ がある。各辺に $0$ または $1$ の重みを割り当てる。各頂点に対して、接続辺の重みの和の偶奇を所望の状態にせよ。

「$L,R$ 番に $1$ 加える操作」を「辺」に見立てるので、各頂点の次数がいい感じになればよいです。連結成分ごとに次数の総和が偶数であることが必要です。

この必要性のもとで、実際に構成が可能です。局所的な条件（ある頂点だけの要求）を満たすのは簡単なところがポイントで、全域森の根から処理していくという定跡が使えます。この方法の偉いところは、「ある連結成分の未処理部分の連結性」が保存されているところです。我々の考察した必要性「連結成分ごとの次数の総和が偶数」が維持された形で構成をすすめることができます。

結局、考察の上でも実装の上でも、典型を３つくらい重ねたような問題でした。個人的には、どのパートも迷わず正しい方向に進めたので、成長が感じられて良かったです。