AtCoder Regular Contest 111 A,B,C,D,E問題メモ

AtCoder Regular Contest 111

序盤はグラフ問題の嵐！

A - Simple Math 2

• 正整数 $N,M$ が与えられる
• $\left \lfloor \dfrac{10^N}{M} \right \rfloor$ を $M$ で割ったあまりを求めよ
• $1 \le N \le 10^{18}$
• $1 \le M \le 10^4$

床関数みたいな不連続な関数は計算しづらいので、なんとか除いて考えたい。

巨大な数の割り算では、あまりを計算する問題が競プロでは頻出。
$10^N$ みたいな巨大な数でも、ダブリングを使えばあまり“は”求められるので、それを使ってどうにかできないか考える。

$10^N$ を $M$ で割ったあまりを $k$ と置くと、$\left \lfloor \dfrac{10^N}{M} \right \rfloor = \dfrac{10^N-k}{M}$ となる。

これの $M$ で割ったあまりを考えたいので、$\dfrac{10^N-k}{M} = aM+b$ とおいた時の $b \ (0 \le b \lt M)$ が求まればいい。

これは $10^N-k=aM^2+bM$ とすると $\mod{M^2}$ の世界で計算しても答えが変わらないことがわかる。

なので、($10^N$ を $M^2$ で割ったあまり) から $k$ を引いて、 $M$ で割れば（必ず割り切れる）答え。

Python3

まぁ、$k$ を引かなくても切り捨て除算で正しい答えが求められるので結果的には必要なかった。

B - Reversible Cards

• $N$ 枚のカードの裏表に数字 $a_i,b_i$ が書かれている
• 各カード、好きな面を上にできるとき、上になっているカードに書かれている数字の種類数の最大値を求めよ
• $1 \le N \le 2 \times 10^5$

直感的に、他のカードで使われた数字はなるべく使わないようにしたい。

その方針に則ると、例えば $(a_i,b_i)=(1,2),(2,3),(3,4),(4,1)$ というカード群では1枚決めれば自動的にすべて決まる。
$(1,2)$ で $1$ を使うと仮決定したら $(4,1)$ で $4$ を使うことになる。そしたら $(3,4)$ で $3$ を使う……という連鎖反応が発生する。

これをシミュレートしようとすると、

• たとえばあるカードで $1$ を仮決定する
• $1$ が書かれた他のカードのもう片方の面に書かれた数字が決まる
• さらにそれらの数字が書かれた他のカードのもう片方の面に書かれた数字が決まる
• …

これは、$(a_i,b_i)$ を辺としたグラフで $1$ から順に辺をたどっていく様子とそっくりである。
そして実際、この問題はグラフに置き換えることができる。

グラフで考えると、連結成分が分かれている数字は影響しないので、連結成分ごとに考えればよい。

1つの連結成分内を考えると、比較的どんな形状でも、適当な頂点を決め打てば連結成分内のほとんど全種類の数字を上にすることが可能とわかる。

連結成分のサイズを $n$ とする。
唯一、木の場合のみ、辺（カード）数がそもそも $n-1$ 本しかないので $n-1$ 種類しかとれない。

他は $n$ 種類全てを上にすることができる。
木でないなら閉路があるので、その閉路（の適当な1つ）を1周させることで閉路上の頂点は全て使える。 そうすれば閉路から生えたヒゲの部分も、連鎖的に全て使えるように決まる。

なので、木かどうかを連結成分ごとに調べて$n$ または $n-1$ を合計していけばよい。
木判定は、探索してもいいし、Union-FindでUnionに用いた辺の本数をカウントしておくなどでもよい。

Python3

C - Too Heavy

• $N$ 人の人と $N$ 個の荷物
  • 人 $i$ の体力は $A_i$
  • 荷物 $i$ の重さは $B_i$
• 各人は荷物を1つずつ持つ。はじめ、人 $i$ は荷物 $p_i$ を持っている
• 以下の操作を繰り返して、人 $i$ が荷物 $i$ を持っている状態にしたい
• 操作
  • 人 $i$ と $j$ を選び、この2人が持っている荷物を交換する
  • ただし、一度でも自身の体力 以上 の荷物を持った人は、疲れてしまい $i,j$ として選べない
  • 特に、最初から $A_i \le B_{p_i}$ だった人は1度も交換できない
• 可能か判定し、可能なら最小手数の一例を示せ
• $1 \le N \le 2 \times 10^5$

まず可能かどうかは、初期状態で「自分の番号と違う荷物を持っていて（$i \neq p_i$）、かつ1回も動かせない（$A_i \le B_{p_i}$）人」がいれば不可能。

そうでない時を考える。

軽い荷物はいくらでも回せるが、重い荷物は無駄に交換すると疲れてしまう人を発生させかねないので、なるべくはやく最終的に持つべき人へ納めたい。

つまり、「$B_i$ の大きい $i$ から順に、$i$ と（今荷物 $i$ を持っている人 $j$）を選び、交換させる」という方針がたつ。

この直感的な方針を考察すると、最小手数で、必ずうまくいくことがわかる。

$B_i$ の大きい順に $i$ を考え、その時点で荷物 $i$ を持っている人を $j$ とする。

まだ確定していない荷物は、$B_i$ より軽い。つまり、$j$ が交換後に持つことになるのは、必ず $B_i$ 以下の重さの荷物である。

初期状態のチェックで $i=p_i$ でない $i$ については全て $A_i \gt B_{p_i}$ であるとわかっている。
そこから人 $i$ が持つ荷物は軽くなっていく一方なので、最終的に自分の荷物を持つ直前まで、動かせなくなることはない。

従って、「誰かが自分の荷物を持つ前に疲れてしまう」ことは発生しない。

順列 $p_1,p_2,...$ を $1,2,...$ にスワップで並べなおす手数は、操作順によらず、決まっている。

まず、初期状態はいくつかのサイクル（$i→p_i→p_{p_i}→...$ と辿っていって $i$ に戻るようなループ）に分かれている。

このサイクルのサイズを $n$ とすると、この部分を最終状態にする最小手数は $n-1$ となる。

i   1  2  3  4
p   3  4  2  1

 ↓ どれか1つをFIXさせると

i   1  2  3  4    FIXした1つ + サイズが1減ったサイクル になる
p   1  4  2  3    これより手数を減らす方法はない

今回、どれか1つをFIXさせ続ける、という操作しかしないので、この理屈通りとなり、最小手数が保証される。

順列が出てくる問題は添え字で混乱しやすい。

冷静に、「今、人 $i$ が何の荷物を持っているか」「今、荷物 $i$ が誰に持たれているか」を管理する。

Python3

D - Orientation

• $N$ 頂点 $M$ 辺の単純な無向グラフと、各頂点に書かれた数字 $c_1,c_2,...,c_N$ が与えられる
• 以下の条件を達成できるように、全ての辺を、向きを決めて有向辺にする一例を示せ
  • 頂点 $i$ から辿っていける頂点数は、$i$ を含め $c_i$ 個
• 必ず解があるような入力のみが与えられる
• $1 \le N \le 100$

$i→j$ の方向に有向辺をはったら、$j$ から行ける頂点は全て $i$ からも行けるので、$c_i \ge c_j$ となるはずである。

よって、両端の $c$ が異なる辺は、大→小に張ればOK。

同じ場合が問題。

これは、$i$ から $c$ が同じ頂点だけをたどっていって、$i$ に戻ってこれるような状態、つまり強連結成分となっていなければならない。

８ → ８ → ５ → ５ → １
 ↖  ↙     ↑    ↓
   ８       ５ ← ５

なので、「直接辺でつながっている、$c$ が同じ頂点グループ」を1つの連結成分として、それごとに辺の張り方を考えればよい。

ただ、この辺の張り方がわからなかった。

以下のようにするといいらしい。

• 適当な頂点を根として、DFSで行けるところまでいく
  • このとき使った辺の向きは、通過した向きにする
• 使わなかった辺（後退辺）は、必ず「根 - $i$ - $j$」が一直線になるので、$j→i$ の向きで張る

DFSが突然出てくるが、まぁ有向グラフの強連結成分分解や、橋の判定などをする際に使われるので、そこから着想して考慮できてもよかったな。

「橋」というのは、無向グラフにおいてそれを除くと1つの連結成分が2つに分かれてしまう辺のこと。
今回の制約では、$c$ が等しい連結成分内においては、橋があると有向にした時に強連結を維持できなくなり矛盾するので、無いことが保証されている。

この橋を検出するアルゴリズムが、適当な頂点を根としてDFSして、「自分より下のどの頂点からも、自分より上に戻れない」ような辺が橋である、というもの。

• 橋（bridge）検出アルゴリズム - nupiocaの日記

    ○ <-,
    ｜   |
    ○ --'
    ｜     ←橋
    ○ <-,
    ｜   |
,-> ○   |
|   ｜   |
|   ○ --'
|   ｜
`-- ○

理由もまぁ見たまんまなのだが、このアルゴリズムを使えば、確かに今回の問題にも適用できることがわかる。

なんかBFSでもDFSでもいい場合に書くDFSは非再帰で書くのは楽だが、今回はちゃんとDFSでないといけなくて、それを非再帰で書くのは少しややこしい。
今回の制約くらいなら再帰で問題ないが、非再帰で書くやり方も覚えとかないとな。

Python3

E - Simple Math 3

• 整数 $A, B, C, D$ が与えられる
• 次の条件を満たす正整数 $i$ がいくつあるか求めよ
• 条件
  • $A+B \times i$ 以上 $A+C \times i$ 以下の整数の中に、$D$ の倍数は存在しない
• 1つの入力につき $T$ ケース与えられるので、全てについて答えよ
• $1 \le T \le 10000$
• $1 \le A \lt D$
• $0 \le B \lt C \lt D$
• $2 \le D \le 10^8$

floor sumについて知っていないと自力でたどり着くのは少し難しそう？

ほぼ、公式解説の写経になってしまうが。

ある2数 $X,Y$ の間（両端含む）に $D$ の整数が存在しないことは、言い換えると、2数を $D$ で（切り捨てで）割った商が等しいといえる。
厳密には、$X=Y$ かつそれが $D$ の倍数だったときなどを考慮すると $\left \lfloor \dfrac{X-1}{D} \right \rfloor$ と $\left \lfloor \dfrac{Y}{D} \right \rfloor$ が等しければよいといえる。

つまり、$\left \lfloor \dfrac{A+B \times i-1}{D} \right \rfloor$ と $\left \lfloor \dfrac{A+C \times i}{D} \right \rfloor$ が等しくなる $i$ の個数が答えとなる。

また、$i$ が大きくなれば確実に $D$ を含むようになっていく。
具体的には、連続した $D$ 個の整数の中には必ず1つは $D$ の倍数を含むので、 $(A+C \times i)-(A+B \times i) + 1 \lt D$、つまり $i \lt \dfrac{D-1}{C-B}$ となり、$i$ の上限が決まる。

逆に言うと、この範囲の $i$ については整数の範囲が $D$ 未満のため、含むとしても1個の $D$ の倍数しか含むことは無い。

つまり、$\left \lfloor \dfrac{A+C \times i}{D} \right \rfloor - \left \lfloor \dfrac{A+B \times i-1}{D} \right \rfloor$ は、0か1に限られることになる。

と、いうことは。$K=\dfrac{D-2}{C-B}$ として、以下が「$i$ の候補の中で、条件を満たさないものの個数」となる。

• $\displaystyle \sum_{i=1}^{K} \left(\left \lfloor \dfrac{A+C \times i}{D} \right \rfloor - \left \lfloor \dfrac{A+B \times i-1}{D} \right \rfloor \right)$

これは、ばらしてやると、

• $\displaystyle \sum_{i=1}^{K} \left \lfloor \dfrac{A+C \times i}{D} \right \rfloor - \sum_{i=1}^{K} \left \lfloor \dfrac{A+B \times i-1}{D} \right \rfloor$

このように、「ある一次式 $f(x)=ax+b$ について $f(0)～f(N)$ をそれぞれ $M$ で割ったときの整数部分の総和を求める」というのを高速に計算できるアルゴリズムがある。

• sum of floor of linear の解説するよ - えびちゃんの日記

これを使って求めて、$i$ の候補の個数 $K$ から引けば、それが答えとなる。

Python3