パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）D,E,F問題メモ

パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）

中国剰余定理は何回見てもアルゴリズムが覚えられんのよね。

D - Sum of difference

• $N$ 個の整数 $A_1,...,A_N$ が与えられる
• $\displaystyle \sum_{i=1}^{N-1} \sum_{j=i+1}^{N}|A_j-A_i|$ を求めよ
• $2 \le N \le 2 \times 10^5$
• $|A_i| \le 10^8$

絶対値は「非負ならそのまま、負なら正負逆転」という操作と言い換えられ、「絶対に非負」という保証を作ってしまえば外せる。

そのためには、常に $A_j \ge A_i$ となればよくて、これは $A_i$ を昇順にソートすれば保証される。

ソートしても、「$A$ の全てのペアについて $|A_j-A_i|$ を求めて合計する」という処理内容は一緒で、 $|A_j-A_i|$ は、$i$ と $j$ を入れ替えても答えが変わらない。なのでソートしても問題ない。

これで $\displaystyle \sum_{i=1}^{N-1} \sum_{j=i+1}^{N}(A_j-A_i)$ を求めればよくなった。

このような「全ての2数ペアについて何らかの計算結果の総和を求める」系は、「1つの数が答えにどれだけ足されるか」というように個々の数に分解できないか考える。

すると、それぞれの数は「自分より大きい数とのペアでは $A_i$ 側になり負で作用する」「自分より小さい数とのペアでは $A_j$ 側になり正で作用する」ので、 自分より大きい数と小さい数の個数（＝ソート順で何番目か）がわかれば個々に分解できる。

自分と等しい数がある場合がちょっと気になるが、気にせずソート順を基準にして扱えばちゃんと打ち消されるので問題ない。

Python3

E - Throne

• 円周上に $N$ 個の椅子が並べられていて、1つは玉座
• 高橋君は最初、玉座から時計回りに数えて $S$ 個隣の椅子に座っている
• 次の移動を繰り返して玉座に座りたい
  • いま座っている椅子から時計回りに数えて $K$ 個隣の椅子に移動する
• 高橋君が玉座に座ることができるか判定し、できる場合は最小の移動回数を求めよ
• $T$ 個のテストケースに答えよ
• $2 \le N \le 10^9$
• $1 \le S \lt N$
• $1 \le K \le 10^9$

N=12  S=3
   ○👑○
 ○      ○
○        Ｓ
 ○      ○
   ○○○

椅子の個数で移動を考える。

椅子の位置を考えると、$9,21,33,...,9+12k$ 個（$k \ge 0$）移動すると玉座に座れる。
移動を考えると、$K,2K,3K,...$ 個移動した位置に座れる。

この2つが一致する非負の最小の数を求めれば、それを $K$ で割った値が答え。求めるのには中国剰余定理が使える。

• $N$ で割ると $N-S$ 余り、$K$ で割ると $0$ 余る数を求めよ

Python3

ちゃんとライブラリ整備しとこうね。

検索して出てくるコードは「2つのmodが互いに素を前提としているか」「答えが求まらないときにエラーにならないか」が一定じゃなくて、どれ使えばいいかわからん問題が発生する。

上記のコードは AtCoder Library を移植して、inv_gcd() に相当する機能はPython3.8より使える負の指数の pow() に置き換えたもの。

公式解説の方法。

$kK \equiv -S \mod{N}$ と立式して、$\mod{N}$ における $K$ のモジュラ逆数 $K^{-1}$ を求め、$k \equiv -SK^{-1} \mod{N}$ とすれば求められる。

これもPythonなら負の指数の pow() を使えばここまで簡単になるんだね。

Python3

F - Rook on Grid

• $H \times W$ の盤面の $i$ 行目 $j$ 列目を $(i,j)$ とする
• 盤上にははじめ、$(1,1)$ に将棋の飛車がいる
• 他に $M$ 個の障害物がそれぞれ $(X_i,Y_i)$ にある
• 飛車が2回の移動で到達できるマスの個数を求めよ
• $1 \le H,W \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$

全てのマスについて考える $O(HW)$ は制約上無理。行ごと・列ごとに考えた結果を上手く集約する。

移動は↓→か→↓しかない。

□□□□□
□□■□□
□■□□□
□□□□□
□□■■□
□□□□□
■□■□□
□□□□■
□□□□□

まず、↓→を考える。
これは、各行で一番左に出てくる障害物まで取れる。1個も無い場合は全部取れる。その個数を整理する。

この内、1列目にある障害物はちょっと特殊で、障害物以降の行には行けない（回り込むには3手必要）ので、1回でも0が出てきて以降は全て0にする。

□□□□□  5
□□■□□  2
□■□□□  1
□□□□□  5
□□■■□  2
□□□□□  5
■□■□□  0
□□□□■  4 → 0
□□□□□  5 → 0

そんで、ここで求めた数字分は全部取れる。

↓→→→→  5
↓→■□□  2
↓■□□□  1
↓→→→→  5
↓→■■□  2
↓→→→→  5
■□■□□  0
□□□□■  0
□□□□□  0

あと取りたいのはここ（◇）。これは→↓で取る。今度は列についてさっきと同じことをしたいが、重複して数えないようにする必要がある。

  j  0 1 2 3 4  row
    ↓→→→→   5
    ↓→■◇◇   2
    ↓■  ◇◇   1
    ↓→→→→   5
    ↓→■■◇   2
    ↓→→→→   5
    ■  ■  ◇   0
            ■   0
                 0
col  6 2 1 4 7

ある列でたとえば $col[3]=4$ の時、「上から4行までの中で、$row$ の値が $3$ 未満」の行数が、新規に取れる◇となる。この場合は2個。

全体では $row$ の値が $3$ 未満の行はもっとあるのだが、$col[3]$ の処理時点では含まれないようにしたい。
そのためには、$col$ の値が小さい方から処理していくとよい。

幅 $W+1$ のFenwick木で、「今までで、$row$ の値が $x$ 未満の行が何個あったか」がすぐ取得できるように管理する。

Python3