目次
AtCoder Grand Contest 041 A～C問題メモ
A - Table Tennis Training
問題
- $2N$ 人が $N$ 卓で卓球を繰り返し行う
- 卓は順に $1～N$ のランクがついている
- ランク $i$ の卓で試合を行った2人のうち、勝者は $i-1$、敗者は $i+1$ へ移って次の試合を行う
- ただし、卓1の勝者は卓1に留まり、卓 $N$ の敗者は $N$ に留まる
- 今、友人同士である2人がそれぞれ卓 $A,B$ にいる
- 2人が出会うまでに必要な最小の試合数（2人同士の対戦は含まない）を求めよ
- $2 \le N \le 10^{18}$
解法
このような移動では、基本的に2人の距離の偶奇は変わらない。$A-B$ は偶数ならずっと偶数、奇数ならずっと奇数である。
この距離を0にしたい。
偶数なら、ランクの小さい方が負け続け、大きい方が勝ち続ければ2ずつ縮まり、$\frac{|A-B|}{2}$ が答え。
厄介なのは奇数の時で、卓1で勝つか、卓 $N$ で負けることでのみ、2人の距離の偶奇が調整される。
- 最初にランクが小さい方が卓1で勝ってから負け続ける（大きい方は勝ち続ける）
- 最初にランクが大きい方が卓 $N$ で負けてから勝ち続ける（小さい方は負け続ける）
この2つの両方を試し、小さい方を答えればよい。
def solve(n, a, b):
if a > b:
a, b = b, a
if (b - a) % 2 == 0:
return (b - a) // 2
top = (b + a - 1) // 2
c, d = n - a - 1, n - b + 1
boo = (c + d + 1) // 2
return min(top, boo)
n, a, b = map(int, input().split())
print(solve(n, a, b))
B - Voting Judges
問題
- $N$ 問の問題があり、投票で $P$ 問を選ぶ
- 既にいくらかの票は入っており、$i$ 番目の問題には $A_i$ 票入っている
- 残り $M$ 人のジャッジが投票する
- ジャッジはそれぞれ独立に、好きな $V$ 問を(重複無く)選び、それに1票ずつ入れる
- $M$ 人全ての投票が終わった後、得票数の上位 $P$ 問が選ばれる。同率の場合は任意に選ばれる
- $N$ 問の内、選ばれる可能性のある問題の数を求めよ
- $2 \le N \le 10^5$
- $1 \le V,P \le N-1$
解法
$A_i$ は、あらかじめ降順にソートしておき、改めてindexを振り直しておく。
最初から上位 $P$ 位以内の問題は、$M$ 人が全てその問題に投票すれば勝ち残れる。
それより下位の問題が選ばれるような状況を考える。
畢竟……這い上がれないッ……！ 誰かを蹴落とさなければ……現在の上位 $P$ 問の……誰かをッ……！
狙われるは……必然ッ……！ そう、最も弱い問題 $P$ !!
$M$ 人全てから得票しても$A_P$ に届かない問題は、選ばれる可能性が無い。
その間にある問題 $i$（$A_P-M \le A_i \lt A_P$）については、少し考える必要がある。
M=5 P=3
Ai 10 9 8 | 6 5 3 | 2 1
最初から | ? ? ? | 5人全員が投票し、3位以内の問題に誰も投票しなくても
上位P以内| | その中の最低"8"に勝てないので敗退確定
問題 $i$ は、$M$ 人全てから得票するとして、最終得票可能数は $A_i+M$ となる。
問題 $i$ が選ばれるためにライバルとなる問題は、$P ～ i-1$ である。 $1～P-1$ とは競っても仕方ないし、$i+1～N$ には必ず勝てる。
Ai 10 9 | 8 6 | 5 | 3 2 1
争わ | rival| i | M人のジャッジの票が全て入っても、
ない| | | (同じく全ての票が入った) 5に勝つことは無い
↓ ↓ →M票獲得して問題ない
M票獲得して問題ない
ライバル全員に勝つか同点で終われば、選ばれる可能性はある。 ライバル以外にはどれだけ票が入ってもいい、もっと言うとライバルに入らないよう、票を喰ってくれた方がありがたい。
ライバル以外の問題に、$M$ 人全てが投票するのが最適である。このような問題の数を $s$ とする。
$s \ge V$ であれば、ライバルには1票も入らないことが可能なので、通過できる。
そうで無い場合、ライバルのどれかに、ジャッジ1人あたり $V-s$ 票、合計 $M(V-s)$ 票入る。
ライバルも、$A_i+M$ 票までなら獲得してよい。これを「猶予」とすると、ライバル全員の猶予の合計が $M(V-s)$ 以下であればよい。
M=5
rival i
票 8 6 5
10 ・ ・ □ ■: 初期状態の得票(Ai)
9 ・ ・ □ □: iが最大可能な得票
8 ■ ・ □ ・: 猶予
7 ■ ・ □
6 ■ ■ □
5 ■ ■ ■
...
1問あたりの得票が $M$ 以下であるという制約はあるが、今回の場合、その制約は必ず満たされるので考慮しなくてよい。
from collections import Counter
def solve(n, m, v, p, aaa):
aaa.sort(reverse=True)
count = Counter(aaa)
scores = sorted(count.keys(), reverse=True)
tmp_cnt = 0
for pi, s in enumerate(scores):
c = count[s]
tmp_cnt += c
if tmp_cnt >= p:
ans = tmp_cnt
rival = s
htm_cnt = tmp_cnt - (p - 1) # higher than me excluding top p-1
htm_sum = s * htm_cnt
break
else:
raise RuntimeError
# print(ans)
# print(rival)
# print(htm_cnt, htm_sum)
for s in scores[pi + 1:]:
c = count[s]
upper = s + m
if upper < rival:
break
v4mtm = v - (n - htm_cnt) # remaining vote for higher than s excluding top p-1
if v4mtm <= 0:
ans += c
else:
space = upper * htm_cnt - htm_sum
if space >= m * v4mtm:
ans += c
htm_cnt += c
htm_sum += s * c
return ans
n, m, v, p = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(n, m, v, p, aaa))
C - Domino Quality
問題
- $N \times N$ のマス目状の盤面があり、ここにいくつかのドミノを置いていく
- ドミノは縦または横に、隣り合う2マスをぴったり覆うように置く
- 重ねては置けない
- 以下の条件を満たすような置き方を1つ構築せよ。無理ならその旨を示せ
- ある列(行)について「その列(行)の1マス以上を占めるドミノの枚数」を、その列(行)の「クオリティ」とする
- 全ての列・行でクオリティが等しい
- $2 \le N \le 1000$
解法
小さい盤面の組み方が分かれば、それをつなぎ合わせれば任意の盤面を作れるので、小さい盤面を全探索しましょう、という問題。
偶然上手くいくことはあっても、理屈立てて成立する盤面を見つけるのは難しい（？）。
たとえば3×3と4×4で共通するクオリティを持つ盤面を作ることができれば、7×7の盤面を作れる。同様にこれを繰り返すと、6,8,9,10,… などどんどん広げられる。
■■■・・・・ ■■■・・・・ ■■■・・・・ ・・・■■■■ ・・・■■■■ ・・・■■■■ ・・・■■■■
なので、小さめのいくつかの $N$ で共通するクオリティを持つ盤面を見つけたい。
ところで、ドミノ1枚置くと行＋列のクオリティの総和は3増える。
０１１ ０・・・ １・□□ ０・・・
なので、3の倍数で無い $N$ で成立するクオリティがあるとすれば、それは3の倍数であるはずである。
小さい盤面なので6以上は考えづらいので、「共通するクオリティは3」と固定して、$N=2～8$ あたりを探索する。
すると、4以上の全てで可能であることが見つかる。
def search(field, xs, ys, n, q, c, r):
if r == 0:
return field
for i in range(n):
if xs[i] >= q:
continue
can_vertical = i < n - 1 and xs[i + 1] < q
for j in range(n):
if ys[j] >= q:
continue
if field[i][j] != 0:
continue
if can_vertical and field[i + 1][j] == 0:
field[i][j] = field[i + 1][j] = c
xs[i] += 1
xs[i + 1] += 1
ys[j] += 1
result = search(field, xs, ys, n, q, c + 1, r - 1)
if result is not None:
return result
field[i][j] = field[i + 1][j] = 0
xs[i] -= 1
xs[i + 1] -= 1
ys[j] -= 1
if j < n - 1 and ys[j + 1] < q and field[i][j + 1] == 0:
field[i][j] = field[i][j + 1] = c
xs[i] += 1
ys[j] += 1
ys[j + 1] += 1
result = search(field, xs, ys, n, q, c + 1, r - 1)
if result is not None:
return result
field[i][j] = field[i][j + 1] = 0
xs[i] -= 1
ys[j] -= 1
ys[j + 1] -= 1
return None
def search_main(n, q=3):
print(n, q)
field = [[0] * n for _ in range(n)]
xs = [0] * n
ys = [0] * n
remain = n * 2 * q // 3
result = search(field, xs, ys, n, q, 1, remain)
if result is None:
print(None)
else:
for row in result:
print(' '.join('{:02d}'.format(x) for x in row))
search_main(3)
search_main(4)
search_main(5)
search_main(6)
search_main(7)
4の盤面をナナメに繰り返し、4～7で最後の1つの埋め方を調整すれば、$N$ が大きくなっても4以上の全てで可能であることがわかる。
また、$N=3$ については個別に可能であるパターンがある。（これはまぁ手探りでも見つかる）
def solve(n):
if n <= 2:
print(-1)
return
if n == 3:
print('aab\nc.b\ncdd')
return
field = [['.'] * n for _ in range(n)]
r = n % 4
repeat = [n, n - 5, n - 6, n - 7]
for i in range(0, repeat[r], 4):
field[i + 0][i:i + 4] = 'aacd'
field[i + 1][i:i + 4] = 'bbcd'
field[i + 2][i:i + 4] = 'efgg'
field[i + 3][i:i + 4] = 'efhh'
if r == 1:
field[n - 5][n - 5:n] = 'abc..'
field[n - 4][n - 5:n] = 'abc..'
field[n - 3][n - 5:n] = 'deeff'
field[n - 2][n - 5:n] = 'd.ghh'
field[n - 1][n - 5:n] = 'iigjj'
elif r == 2:
field[n - 6][n - 6:n] = 'abc...'
field[n - 5][n - 6:n] = 'abc...'
field[n - 4][n - 6:n] = 'd.eeff'
field[n - 3][n - 6:n] = 'dghh..'
field[n - 2][n - 6:n] = '.g.ijj'
field[n - 1][n - 6:n] = 'kk.ill'
elif r == 3:
field[n - 7][n - 7:n] = 'abc....'
field[n - 6][n - 7:n] = 'abc....'
field[n - 5][n - 7:n] = 'def....'
field[n - 4][n - 7:n] = 'def....'
field[n - 3][n - 7:n] = 'g..hhii'
field[n - 2][n - 7:n] = 'g..jjkk'
field[n - 1][n - 7:n] = '.llmmnn'
print('\n'.join(map(''.join, field)))
n = int(input())
solve(n)
