パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）D,E,F問題メモ
D - Sum of difference
問題
解法
絶対値は「非負ならそのまま、負なら正負逆転」という操作と言い換えられ、「絶対に非負」という保証を作ってしまえば外せる。
そのためには、常に Aj≥Ai となればよくて、これは Ai を昇順にソートすれば保証される。
ソートしても、「A の全てのペアについて |Aj−Ai| を求めて合計する」という処理内容は一緒で、
|Aj−Ai| は、i と j を入れ替えても答えが変わらない。なのでソートしても問題ない。
これで N−1∑i=1N∑j=i+1(Aj−Ai) を求めればよくなった。
このような「全ての2数ペアについて何らかの計算結果の総和を求める」系は、「1つの数が答えにどれだけ足されるか」というように個々の数に分解できないか考える。
すると、それぞれの数は「自分より大きい数とのペアでは Ai 側になり負で作用する」「自分より小さい数とのペアでは Aj 側になり正で作用する」ので、
自分より大きい数と小さい数の個数（＝ソート順で何番目か）がわかれば個々に分解できる。
自分と等しい数がある場合がちょっと気になるが、気にせずソート順を基準にして扱えばちゃんと打ち消されるので問題ない。
Python3
1 2 3 4 5 6 7 8 9 10 11 |
import sys
n, *aaa = map(int, sys.stdin.buffer.read().split())
aaa.sort()
ans = 0
for smaller_than_a, a in enumerate(aaa):
larger_than_a = n - 1 - smaller_than_a
ans += (smaller_than_a - larger_than_a) * a
print(ans)
|
E - Throne
問題
円周上に N 個の椅子が並べられていて、1つは玉座
高橋君は最初、玉座から時計回りに数えて S 個隣の椅子に座っている
次の移動を繰り返して玉座に座りたい
高橋君が玉座に座ることができるか判定し、できる場合は最小の移動回数を求めよ
T 個のテストケースに答えよ
2≤N≤109
1≤S<N
1≤K≤109
解法
N=12 S=3
○👑○
○ ○
○ Ｓ
○ ○
○○○
椅子の個数で移動を考える。
椅子の位置を考えると、9,21,33,...,9+12k 個（k≥0）移動すると玉座に座れる。
移動を考えると、K,2K,3K,... 個移動した位置に座れる。
この2つが一致する非負の最小の数を求めれば、それを K で割った値が答え。求めるのには中国剰余定理が使える。
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
from math import gcd
def chinese_remainder(rrr, mmm):
n = len(rrr)
r0 = 0
m0 = 1
for i in range(n):
r1 = rrr[i] % mmm[i]
m1 = mmm[i]
if m0 < m1:
r0, r1 = r1, r0
m0, m1 = m1, m0
if m0 % m1 == 0:
if r0 % m1 != r1:
return 0, 0
continue
g = gcd(m0, m1)
if (r1 - r0) % g:
return 0, 0
u1 = m1 // g
im = pow(m0 // g, -1, u1)
x = (r1 - r0) // g * im % u1
r0 += x * m0
m0 *= u1
if r0 < 0:
r0 += m0
return r0, m0
buf = []
t = int(input())
for _ in range(t):
n, s, k = map(int, input().split())
r, m = chinese_remainder([n - s, 0], [n, k])
if m == 0:
print(-1)
else:
print(r // k)
|
ちゃんとライブラリ整備しとこうね。
検索して出てくるコードは「2つのmodが互いに素を前提としているか」「答えが求まらないときにエラーにならないか」が一定じゃなくて、どれ使えばいいかわからん問題が発生する。
上記のコードは AtCoder Library を移植して、inv_gcd() に相当する機能はPython3.8より使える負の指数の pow() に置き換えたもの。
解法2
公式解説の方法。
kK≡−SmodN と立式して、modN における K のモジュラ逆数 K−1 を求め、k≡−SK−1modN とすれば求められる。
これもPythonなら負の指数の pow() を使えばここまで簡単になるんだね。
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 |
from math import gcd
t = int(input())
for _ in range(t):
n, s, k = map(int, input().split())
g = gcd(n, k)
if s % g != 0:
print(-1)
continue
n //= g
s //= g
k //= g
print(-s * pow(k, -1, n) % n)
|
F - Rook on Grid
問題
H×W の盤面の i 行目 j 列目を (i,j) とする
盤上にははじめ、(1,1) に将棋の飛車がいる
他に M 個の障害物がそれぞれ (Xi,Yi) にある
飛車が2回の移動で到達できるマスの個数を求めよ
1≤H,W≤2×105
0≤M≤2×105
解法
全てのマスについて考える 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
from operator import itemgetter
class FenwickTree:
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)
def sum(self, i):
s = 0
i += 1
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def add(self, i, x):
i += 1
while i <= self.size:
self.tree[i] += x
i += i & -i
def debug_print(self):
result = []
for i in range(self.size):
result.append(fwt.sum(i) - fwt.sum(i - 1))
print(result)
h, w, m = map(int, input().split())
row = [w] * h
col = [h] * w
for _ in range(m):
x, y = map(int, input().split())
x -= 1
y -= 1
row[x] = min(row[x], y)
col[y] = min(col[y], x)
for i in range(1, h):
if row[i - 1] == 0:
row[i] = 0
for j in range(1, w):
if col[j - 1] == 0:
col[j] = 0
col_s = sorted(enumerate(col), key=itemgetter(1))
fwt = FenwickTree(w + 1)
ans = 0
p = 0
for j, c in col_s:
for i in range(p, c):
fwt.add(row[i], 1)
ans += row[i]
p = c
ans += fwt.sum(j)
print(ans)
|