目次
AtCoder Grand Contest 029 A～D
A - Irreversible operation
問題
- $N$ 個のオセロの石が一列に並んでいて、初期状態で各石が白黒どちらかの情報が与えられる
- 以下の操作を可能な限り行う
- 隣り合う2つが左から順に「黒、白」なら、ともに裏返して「白、黒」にする
- 何回操作を行うことになるか、求めよ
解法
オセロでたとえられているが、要はバブルソートの交換回数の簡易版で、各白につき、左にある黒の個数分だけ操作を行うことになる。
よって「黒カウント変数」を持ち、左から以下を繰り返すことで求められる。
- 黒なら、カウントを1増やす
- 白なら、現在のカウントを答えに足す
s = input()
ans = 0
tmp = 0
for c in s:
if c == 'B':
tmp += 1
else:
ans += tmp
print(ans)
B - Powers of two
問題
- $N$ 個の$1$以上$10^9$以下の整数がある
- その和が2の冪乗（整数 $k$ を使って $2^k$ で表せるような数）となるようにペアを作る
- 最大でいくつのペアが作れるか
例
3 5 8 11 13
- 8 は単独では2の冪乗だが、この問題ではペアを作らないといけないので関係ない
- (3, 5) で8になるのでペアが作れるが、残りの3個をどう組み合わせてもそれ以上は作れない
- (3, 13), (5, 11) はそれぞれ16になるのでペアが2つ作れ、これが最大となる
解法
間違ったペアを先に作ってしまうと最大に出来ないというところが厄介。
グラフ理論の最大マッチングっぽさはあるのだが、普通の実装では $O(N^3)$ とかになるので $N \le 2 \times 10^5$ の本問ではとても間に合わない。
処理順序をちゃんと考えれば貪欲で解ける。大きい数からペアを決定していくとよい。
大きい数からの貪欲
$a_k$ とペアに出来る数を考える。
大きい方から貪欲に確定していくので、$a_k$ まで来た時点で、$a_k$ より大きい数が含まれる未確定ペアはもう残っていない。相方は $a_k$ 以下の数の中から探すことになる。
「$a_k+(a_k以下の数)$」の答えは、$a_k$ より大きいが、$2a_k$ より大きくはなり得ない。その中に2の冪乗は1つしかなく「$a_k$ より大きい最小の2の冪乗」一意に決定する。よって相方も一意に決定する。
その相方とペアを作れるだけ作る。
もし相方が、他のもっと小さい数ともペアが作れたとしても、それを作るためには $a_k$ とのペアを必ず解散しなければならないので、差し引きゼロとなる。
上記の例の (3, 5) は、1組を解散することでペアの両方が新たなペアを作れるからダメだったが、この方法では $a_k$ が必ずペアを作れなくなってしまうため、問題ない。
実装
PythonのCounterなどで同じ数字をまとめて計算してしまうと、同じ数字が沢山出てくるようなテストケースでは速く処理できる。
奇数は奇数同士、偶数は偶数同士としかペアにならないため、グループ分けして探すと少し速いかも？（ほとんど変わらない）
from collections import defaultdict
n = int(input())
aaa = list(map(int, input().split()))
def solve(count):
ans = 0
for a in sorted(count, reverse=True):
cnt = count[a]
if cnt <= 0:
continue
ma = 1 << (a.bit_length())
b = ma - a
if b in count and count[b] > 0:
if a == b:
pair = cnt // 2
else:
pair = min(cnt, count[b])
count[b] -= pair
ans += pair
return ans
count_e = defaultdict(lambda: 0)
count_o = defaultdict(lambda: 0)
for a in aaa:
if a % 2 == 0:
count_e[a] += 1
else:
count_o[a] += 1
print(solve(count_e) + solve(count_o))
C - Lexicographic constraints
問題
- $N$ 個の文字列$\{S_1,S_2,...,S_N\}$が辞書順に並んでいる
- $S_i$ の長さは $a_i$ であるが、具体的な中身はわからない
- このような文字列群の中で、使われている文字の種類として考えられる最小の値を求めよ
- 文字はアルファベットに限らない。無限に多くの文字があり、それについて辞書式順序が定まっていると考えてよい
- $1 \le N \le 2 \times 10^5$
- $1 \le a_i \le 10^9$
例
この場合、辞書式順序を満たし、使われている文字種は2つ
長さ 中身(一例) S1 3 aab S2 4 aabb S3 2 ba
以下の場合は、文字種2つでは構築できず、3つ目が必要
長さ 中身(一例) S1 2 aa S2 1 b S3 2 ba S4 2 bb S5 2 ca
解法
「$k$ 個の文字を使って構築することは可能か？」で $k$ を二分探索する。
$a_i$ が大きいのでシミュレーションは無理……と思いきや、できてしまう。
というのも、$10^9$ 個の文字が並んでいても、ほとんどは'a'（辞書順最小の文字）が並ぶだけで、実際に必要な「辞書順最小以外の文字」の数は限られるから。
$N=2 \times 10^5$ 個の文字列を区別するのは、文字数 $k=2$ であっても、$2^{18} \gt 2 \times 10^5$ より18文字程度でできてしまう。（もちろん途中で文字数がそれ以下になることもあるのでシミュレーションは必要だが、概算として）
実装
使う文字数 $k$ を二分探索に基づいて決める。決まったら、以下の方法で可能か試す。
スタック型のデータ構造で文字列を管理する。格納するアイテムは、[位置, 文字の辞書順] とし、辞書順最小の文字は省略する。文字の辞書順は、1から始まる整数として表現する。
位置: 0 1 2 3 4 5
現在の文字列: a a b c a d
↓
データ構造: [[2, 2], [3, 3], [5, 4]]
各 $a_i$ につき、前の文字列より辞書順が後となる中で最も近い文字列を求めていく。
$a_{i-1} \lt a_i$ の時
$S_{i-1}$ の末尾に辞書順最小の文字を繰り返し繋げるのが最適。（'abc'→'abcaaaa…'）
今回のデータ構造的には何もすることはない。
$a_{i-1} \ge a_i$ の時
$S_{i-1}$ の $a_i$ 文字目より後を切り落とし、$a_i$ 文字目を辞書順で次の文字にするのが最適
- たとえば $a_i=4$ の場合、'abcdefg'→'abce'
- 'abddabc'→'acaa' のように“繰り上がり”が発生することもある
繰り上がったときに桁あふれが発生すれば、$k$ 文字での構築は不可能（$k=4$ で 'dddd' を辞書順で次にしようとしてもできない）。二分探索に従い次の$k$を試す。
たとえば以下のように実装する。
- スタックで末尾アイテムの「位置」が $a_i$ 以下になるまでpop
- 末尾アイテムの、位置が$a_i$ かつ 文字の辞書順が$k$なら、繰り上がりが発生。popして $a_i$ を1減らして繰り返す
- ※ここで、$a_i$の意味は「文字の辞書順を1増やす位置」に変化している
- $a_i$ が0まで行ったらアウト（構築不可能）、終了
- 末尾アイテムの位置が $a_i$ なら、末尾アイテムの文字の辞書順を1増やす
- 末尾アイテムの位置が $a_i$ 以外なら、末尾に $[a_i, 2]$ をpushする
def solve(aaa):
l = 1
r = 200000
while l < r:
m = (l + r) // 2
if check(m, aaa):
r = m
else:
l = m + 1
return r
def check(d, aaa):
if d == 1:
return all(a1 < a2 for a1, a2 in zip(aaa, aaa[1:]))
l = 0
word = [[0, 0]]
for a in aaa:
if l >= a:
if not carry(d, word, a):
return False
l = a
return True
def carry(d, word, a):
while word[-1][0] > a:
word.pop()
while word[-1] == [a, d]:
word.pop()
a -= 1
if a == 0:
return False
if word[-1][0] == a:
word[-1][1] += 1
else:
word.append([a, 2])
return True
n = int(input())
aaa = list(map(int, input().split()))
print(solve(aaa))
D - Grid game
問題
- 高橋君と青木君が $H$ 行 $W$ 列のマス目を使ってゲームをする
- マス目上には $N$ 個の障害物が、それぞれ $(X_i,Y_i)$ にある
- (1,1) には障害物ははなく、1つの駒が置いてある
- ゲームのルール
- 高橋君から始めて、交互に以下の行動のいずれかを行う
- 駒を隣り合うマスに動かす
- ただし、駒の位置を $(x,y)$ としたとき、高橋君は $(x+1,y)$ にのみ、青木君は $(x,y+1)$ にのみ駒を動かすことができる
- 動かす先に障害物や外壁がある場合はこの行動をとることはできない
- 駒を動かさず、マス目を元の状態のまま行動を終える
- これも行動の1つと数える
- 2回連続で駒が動かされなかった場合、ゲームを終了する
- 高橋君はできるだけ多くの回数の行動 (駒を動かさないのも含む) を行ってゲームを終えたい
- 青木君はできるだけ少ない回数の行動を行ってゲームを終えたい
- 高橋君が行うことになる行動の回数は何回か求めよ
解法
何でお前800点問題なんだ……コンテスト中は点数に惑わされずちゃんと一通り問題に目を通さないとダメですね。（一般的な直交座標グラフとx,yが逆という罠はあったようだが）
求めるのは高橋君の行動回数だが、ゲームの支配者は青木君である。
たった2回連続で駒が動かされなかっただけで終わるので、高橋君が動かさなかったら、青木君は自分の手番でも動かさずにゲームを終了できる。よって高橋君は動かし続けるしかなく、選択の余地はない。
逆に青木君は、次に高橋君が動かそうとしても障害物に妨げられるような状況で高橋君に手番を回すのがよい。誘導する障害物は左下半分（後述）の中で自由に選べるので、最も $x$ 座標が小さいものを選ぶのが早く終わる。
→y ↓駒・・・・・ 駒は●で示した範囲なら x ●●・・・・ 青木君が希む任意のマスに行ける ●●●・・・ （障害物が無い場合） ●●●●・・ ●●●●●・
→y ↓駒・・・・・ ある行で、動かせる範囲の最も右端のマスに障害物（×）があると x ●●・・・・ 青木君が動かせないので、以降、動かせる範囲は1つずつ減る ●●×・・・ （右端以外にあるのは大丈夫、その下に行く前にゲームが終わる） ●●●・・・ ●●●●・・
→y ↓駒・・・・・ 青木君は、行ける範囲の中で最も上にある x └┐・・・・ 「障害物の1つ上のマス」に動かして、高橋君にターンを渡す ●│×・・・ ●└┐・・・ 範囲内に障害物が存在しなければ、 ●●×●・・ 一番下の外壁にぶつけるしかなく、答えはHとなる
import sys
def solve(obstacles):
offset = 0
obstacles.sort()
for x, y in obstacles:
if x > y + offset:
return x - 1
if x == y + offset:
offset += 1
return h
h, w, n = map(int, input().split())
obstacles = [tuple(map(int, line.split())) for line in sys.stdin.readlines()]
print(solve(obstacles))
