ABC313復習

第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313） - AtCoder

■結果

• ABC3完
• 3完なのに緑パフォ(970)と良いランクだった。（確かにDが難問！）

■Ａ問題（To Be Saikyo）

人iを超えるために必要なレベルを人1を基準に走査。
最大値は0を初期値として超えたら更新。（所要時間約7分。）

n = int(input())
p_list = list(map(int, input().split()))

p1=p_list[0]
max_x  = 0

for ii in range(1,n):
    x = p_list[ii] - p1 + 1
    max_x=max(max_x,x)
print(max_x)

■Ｂ問題（Who is Saikyo?）

自分より強い人が居ないと確定している人が何人いるか確認する。
人iの自分より強い人を示す配列を準備して値-1で初期化。入力の強さ情報で更新。この際に誰がより強いかは気にしない。自分より強い人が居れば-1でなくなる。
最後に-1はいくつ残っているか確認して1人ならその人の番号を出力。（所要時間17分。）

n,m = map(int, input().split())
ll = [-1] * n

for ii in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ll[b] = a

if ll.count(-1) !=1:
    print(-1)
else:
    print (ll.index(-1)+1)

けんちょんさん解説。問題を最強者を始点とするグラフか否かの判定問題とし、全頂点に到達できる特定の頂点はあるか、頂点N個からDFS/BFSで辿ってみる。処理重いけど汎用的。

■Ｃ問題（Approximate Equalization 2）

操作で誰かを+1/-1するので整数列Aの合計は不変量。（なのだが使い道を思いつかなかった。）
操作後は全員が平均値か平均値+1になるはず。（ということにする。理屈でなく何例か試して。）
ということは各人と平均か平均+1との差をとると各人に対して何回の操作が必要か判る。
+1/-1操作がペアなので、+1必要な操作回数と-1必要な操作回数を別々に合計し、大きい方が最低必要な操作回数になる。（所要時間34分）

n = int(input())
a_list = list(map(int, input().split()))

avg = sum(a_list) // len(a_list)

high = 0
low = 0
for ii in range(n):
    if a_list[ii] > avg + 1:
        high = high + (a_list[ii] - (avg + 1))
    elif a_list[ii] < avg:
        low = low + (avg - a_list[ii])
    else:
        pass
print(max(high, low))

公式解説。論証過程に理解が追い付いてないが、結論とコードのシンプルさは天才的。

「Aiが小さい順にi=1,2,…,Nを並び替えたとき、先頭のN−r個のiについてBi​=p、末尾のr個のiについてBi=p+1とするのが最適に思われます」

■Ｄ問題（D - Odd or Even）

まず、複数の回答を比較することで、あるAiとAjが同じかどうか判定する手立てはあることに着目。(? 1 2 3 = 0 かつ ? 2 3 4 = 0 なら A1=A4と判る。)
1/0の確定は直ぐには難しそうなので、A1=aとして残りをa,bで埋めていく。
しかし、1/0を確定する方法に気を取られて質問の順番が定まらず時間切れ。
下記を参考にさせて頂いて質問の順番を整理。

A1..Akを含む質問q1、質問q1からA1を除外してAi(i>=k)を追加した質問q2、質問q1にAkを追加してAi(1<i<k)を除外した質問q3の順でa,bを確定する。
最後に質問q1の答えを再確認してaが0/1のどちらか確定させる。

n, k = map(int, input().split())


def get_answer(q):
    print("?", *q, flush=True)
    return int(input())


a = ["?"] * n
start = 0
a[start] = "a"

q1 = set()
for ii in range(k):
    q1.add(ii + 1)
t1 = get_answer(q1)

for ii in range(k, n):
    q2 = (q1 - {start + 1}) | {ii + 1}
    t2 = get_answer(q2)
    a[ii] = "a" if t1 == t2 else "b"

for ii in range(1, k):
    q3 = (q1 - {ii + 1}) | {k + 1}
    t3 = get_answer(q3)
    a[ii] = "a" if (t1 == t3 and a[k] == "a") or (t1 != t3 and a[k] == "b") else "b"

if (a[0:k].count("a") + t1) % 2 == 0:
    print("!", *[1 if c == "a" else 0 for c in a], flush=True)
else:
    print("!", *[0 if c == "a" else 1 for c in a], flush=True)

本コードでAC。
しかし、偶々この着目点で解ききれる設問だだっただけで、汎用性は無いかも。
けんちょんさんのやりかた（偶奇を含む対称な連立方程式をXORで処理）に慣れておくと今後問題解くときに便利なんじゃないかなと思った。まる。