目次
AtCoder Grand Contest 025
2問目から700点は反則だぜ。
A - Digits Sum
問題
- 正整数 $A$ と $B$ があり、和 $N$ がわかっている
- $A$ の各桁の和＋ $B$ の各桁の和の、考えられる最小値を求めよ
例
N = 155 の時 A = 96, B = 59 -> 9+6+5+9 =29 A = 123, B = 32 -> 1+2+3+3+2=11
解法
繰り上がりが発生すると効率が悪い。
繰り上がりをなるべく発生させない $A$ と $B$ を選ぶ時、$N$ の $i$ 桁目が $N_i$ なら、同じ桁の $A_i+B_i=N_i$ となる。
よって、基本的には $N$ の各桁をそのまま足した値が答えとなる。
しかし例外があって、$A,B$ とも1以上なので、$N$ が 10000 など10の冪乗の時は上手いこととれない。
その場合のみ、5000+5000=10000など、繰り上がりを発生させるしか無くなる。
from collections import Counter
n = input()
c = Counter(n)
c.pop('0', None)
if len(c) == 1 and '1' in c and c['1'] == 1:
print(10)
else:
print(sum(int(f) * m for f, m in c.items()))
B - RGB Coloring
問題
- $N$ 階建てのタワーを赤緑青の3色で塗る。塗らなくてもよい。
- 各階は1色で塗り、色によってそれぞれ得点が決められている
- 赤なら $A$ 点
- 緑なら $A+B$ 点
- 青なら $B$ 点
- 無色なら 0 点
- 得点の合計値をちょうど $K$ 点になるように塗るのは何通りあるか。
解法
方針
3色はややこしいので、2色にしたい。
緑が丁度赤＋青なので、赤と青の2色のみで重複を許して塗って、重複した箇所は緑で塗ったことにすればよい。（赤じゃなくて黄色なら気付きやすかったね）
こうすることで、$Ax+By=K$ が成り立つ整数 $x,y\ (0 \le x \le N, 0 \le y \le N)$ の組について、
赤を $N$ 階の中から $x$ 階選んで塗るので ${}_NC_x$ 通り、青を $N$ 階の中から $y$ 階選んで塗るので ${}_NC_y$ 通り、それぞれ独立なので、${}_NC_x \times {}_NC_y$ 通りの塗り方がある。
これを全ての $x,y$ の組について足し合わせればよい。
実装
答えが膨大になりMODで答えるので、$1!$～$N!$ の逆元を求めておかないとTLEになる。
$${}_NC_x \equiv N! \times x!^{-1} \times (N-x)!^{-1} \mod{MOD}$$
また、$Ax+By=K$ が成り立つ $x,y$ を求めるには、拡張ユークリッドの互除法を用いる。
どちらも頻出ではあるが整数論アルゴリズムを2つを用いる、解法を思いついても実装が大変な問題。（と思ったら、制約的にユークリッドの互除法は無しで全探索でも行けたみたい）
def prepare(n, MOD):
f = 1
for m in range(1, n + 1):
f *= m
f %= MOD
inv = pow(f, MOD - 2, MOD)
invs = [1] * (n + 1)
invs[n] = inv
for m in range(n, 1, -1):
inv *= m
inv %= MOD
invs[m - 1] = inv
return f, invs
def ex_euclid(x, y):
c0, c1 = x, y
a0, a1 = 1, 0
b0, b1 = 0, 1
while c1 != 0:
m = c0 % c1
q = c0 // c1
c0, c1 = c1, m
a0, a1 = a1, (a0 - q * a1)
b0, b1 = b1, (b0 - q * b1)
return c0, a0, b0
def solve(n, a, b, k):
MOD = 998244353
fn, invs = prepare(n, MOD)
if a < b:
a, b = b, a
c, x, y = ex_euclid(a, b)
d, m = divmod(k, c)
if m != 0:
return 0
ac, bc = a // c, b // c
x, y = x * d, y * d
f, x = divmod(x, bc)
y += ac * f
if y > n:
f = (y - n - 1) // ac + 1
x += bc * f
y -= ac * f
# print(x, y, a * x + b * y)
ans = 0
base = fn * fn % MOD
while x <= n and y >= 0:
tmp = base * invs[x]
tmp %= MOD
tmp *= invs[n - x]
tmp %= MOD
tmp *= invs[y]
tmp %= MOD
tmp *= invs[n - y]
ans += tmp
ans %= MOD
x += bc
y -= ac
return ans
n, a, b, k = map(int, input().split())
print(solve(n, a, b, k))
C - Interval Game
問題
- 数直線が1つと、$[L_i,R_i]$ の区間が $N$ 個ある
- 青木君は順番に区間を指定する
- 高橋君は数直線上におり、指定されるたびにその区間に入るように移動する
- 最初
0におり、全ての区間指定が終わった後も0に戻る
- 高橋君はなるべく移動を最小に動く
- 青木君はなるべく移動を最大に指定する
- 高橋君が動く距離はいくらか
解法
左右になるべく大きく移動させる貪欲で解ける。
一瞬貪欲は思い浮かんだが、「本来左に移動させるために使う区間を、先に右で使っちゃうかも」とか考えて躊躇してしまった。
よく考えたら、左に移動させるのが最適になるような区間は、それより先に右に移動させるのに使う候補に出てくるはずが無い。実際に試すの大事。
区間
0
A |-------|
B |----|
C |--------|
D |-------------------------|
===========================================
貪欲に左に移動させる際に選ぶのは、最も $R_i$ が小さい区間
v
A |-------|
B |▬▬|
C |--------|
D |-------------------------|
===========================================
貪欲に右に移動させる際に選ぶのは、最も $L_i$ が大きい区間
v
A |-------|
B |-済-|
C |▬▬▬▬|
D |-------------------------|
===========================================
繰り返し
v
A |▬▬▬▬|
B |-済-|
C |---済---|
D |-------------------------|
===========================================
もうこれ以上右に移動させられる区間が残ってないので終了
v
A |---済--|
B |-済-|
C |---済---|
D |-------------------------|
杞憂が杞憂であることの確認
貪欲法で区間Aを左に移動させるのに選ぶということは、その瞬間高橋君は $R_A$ より右にいたことになる。
この時、区間Aが既に右に移動させるのに使われていることがあるか？
その場合「残りの区間の中で区間Aの $L_A$ が最も大きかった」瞬間があったということになる。つまり、最大限高橋君を右に移動させられる区間がAであり、それ以降高橋君を $L_A$ より右に移動させられる区間は残っていない。当然、$R_A$ より右にも移動できない（$L_i \lt R_i$）。
これは、1文目と矛盾する。
よって貪欲法で、右に移動させるのに用いた区間を後から左に移動させるのに用いることはあり得ない。めでたしめでたし。
（だからといって貪欲で解ける証明はよくわかってないのだが）
import sys
def get_checks(lefts, rights, used):
def left_check(pos):
while lefts:
e, i = lefts.pop()
if not used[i]:
break
else:
return None
used[i] = True
if pos >= e:
return None
return e
def right_check(pos):
while rights:
e, i = rights.pop()
if not used[i]:
break
else:
return None
used[i] = True
if pos <= e:
return None
return e
return left_check, right_check
def simulate(left_first=True):
ans = 0
pos = 0
_lefts = lefts.copy()
_rights = rights.copy()
used = [False] * n
left_check, right_check = get_checks(_lefts, _rights, used)
funcs = [left_check, right_check] if left_first else [right_check, left_check]
dir = 0
while True:
e = funcs[dir](pos)
if e is None:
break
ans += abs(e - pos)
pos = e
dir ^= 1
ans += abs(pos)
return ans
n = int(input())
lefts, rights = [], []
for i, line in enumerate(sys.stdin.readlines()):
l, r = map(int, line.split())
lefts.append((l, i))
rights.append((r, i))
lefts.sort()
rights.sort(reverse=True)
lf = simulate(True)
rf = simulate(False)
print(max(lf, rf))
D - Choosing Points
問題
- $0 \le i,j \lt 2N$ の $4N^2$ 個の格子点 $(i,j)$ を考える
- ここから $N^2$ 個の格子点を選ぶ
- 選んだどの2点を取っても、距離が $\sqrt{D_1}$ でない
- 選んだどの2点を取っても、距離が $\sqrt{D_2}$ でない
- このような格子点の集合の一例を示せ
解法
「格子点を2色で塗りわけ、同じ色同士で塗られた点は絶対に距離が $\sqrt{D_1}$ にならない」という塗り方は、偶奇に着目すれば意外と単純らしい。
2点のx軸距離、y軸距離をそれぞれ $s,t$ として、$D_1=s^2+t^2$ である。
D1が奇数
$s$ と $t$ の偶奇は異なる。よって、以下に示す塗り分け方ができる。
○●○●○● ●○●○●○ ○●○●○● ●○●○●○ ○●○●○● ●○●○●○
D1が4で割って2余る
$s$ と $t$ はともに奇数である。よって、以下に示す塗り分け方ができる。（横でも可）
○●○●○● ○●○●○● ○●○●○● ○●○●○● ○●○●○● ○●○●○●
D1が4の倍数である
$s$ と $t$ はともに偶数である。なので、隣り合う2×2のマスは同じ色で大丈夫。
○○？？△△ ←色はわからないが、同じ記号は同じ色 ○○？？△△ ？？◇◇？？ ？？◇◇？？
ここで盤面を縮小して、$(s,t,D_1) <= (\frac{s}{2},\frac{t}{2},\frac{D_1}{4})$ にしてやる。
そうすると、$D_1$ が奇数か、4で割って2余るパターンに持ち込める。$D_1$ が4で割ってもまだ4の倍数なら、再帰的に縮小する。
D_1/4 が奇数 D_1/4 が4で割って2余る ○○●●○○ ○○●●○○ ○○●●○○ ○○●●○○ ●●○○●● ○○●●○○ ●●○○●● ○○●●○○ ○○●●○○ ○○●●○○ ○○●●○○ ○○●●○○
これを $D_2$ の条件についても調べ、いずれも $(i,j)=(0,0)$ と同じ色になる点を列挙すると、それが答えとなる。
def check_odd(i, j):
return (i + j) % 2 == 0
def check_even(i, j):
return i % 2 == 0
def solve(n, d1, d2):
s1, s2 = 0, 0
while d1 % 4 == 0:
d1 >>= 2
s1 += 1
while d2 % 4 == 0:
d2 >>= 2
s2 += 1
f1 = check_odd if d1 % 2 else check_even
f2 = check_odd if d2 % 2 else check_even
lim = n ** 2
buf = []
for i in range(2 * n):
_i1 = i >> s1
_i2 = i >> s2
for j in range(2 * n):
if f1(_i1, j >> s1) and f2(_i2, j >> s2):
buf.append('{} {}'.format(i, j))
if len(buf) == lim:
return buf
n, d1, d2 = map(int, input().split())
print('\n'.join(solve(n, d1, d2)))
