📝

AtCoder Regular Contest 151 レポート

2022/10/17に公開

AtCoder

Python 3

tech

摘要

Aのみ1完，レーティングを少し下げて緑に下がりました．

ARC151

コンテスト名: AtCoder Regular Contest 151
順位: 1301st / 3817
パフォーマンス: 1150
レーティング: 1200 → 1195 (-5)
コンテスト参加回数: 60

A - Equal Hamming Distances

A - 問題

長さ $N$ の $01$ 列 $S, T$ とハミング距離^[1]で等距離にあるような長さ $N$ の $01$ 列 $U$ のうち辞書順最小のものを求めよ．

A - 解法

まず，ハミング距離について，

$S, T$ のハミング距離が偶数 $\iff$ $U$ が存在
特に $01$ 列においては「各桁の総和の差abs(sum(S) - sum(T))」とハミング距離の偶奇が一致しそう

ということがわかる．
また，その時の最良な $U$ については，

sum(U) == (sum(S) + sum(T))//2となるように
基本的には $U_i = 0$ ，cnt = abs(sum(S) - sum(T)) // 2の回数だけ $U_i=1$ とする
右から順に $cnt$ 回だけ，sum()の大きい方が $1$ ，小さい方が $0$ となっているところを $U_i=1$ とする

というように貪欲法より求められると考えた．

A - ACコード

def main():
    global N, S, T
    N = int(input())
    S, T = input(), input()

    sm_s, sm_t = sum(int(si) for si in S), sum(int(ti) for ti in T)
    if (sm_s - sm_t)%2: ans = -1
    elif sm_s == sm_t: ans = '0'*N
    elif sm_s > sm_t:
        arr = ['0']*N
        cnt = (sm_s - sm_t)//2
        for i in range(N-1, -1, -1):
            if S[i] == '1' and T[i] == '0':
                arr[i] = '1'
                cnt -= 1
            if cnt == 0: break
        ans = ''.join(arr)
    else:
        arr = ['0']*N
        cnt = (sm_t - sm_s)//2
        for i in range(N-1, -1, -1):
            if S[i] == '0' and T[i] == '1':
                arr[i] = '1'
                cnt -= 1
            if cnt == 0: break
        ans = ''.join(arr)

    print(ans)


if __name__ == '__main__': main()

B - A < AP

B - 問題

$(1, 2, \dots, N)$ の順列 $P$ に対して，各要素が $1 \leq A_i \leq M$ であり， $A < (A_{P_1}, A_{P_2}, A_{P_N})$ を満たすような $A$ の個数を求めよ．

B - 検討

しっかり時間の余裕を持って臨んだものの全くわからず．
転倒数とか関係あるかな？と思ってフェニック木を用いた計算を調べ実装してみたくらい（全く関係なかった）．

C - 01 Game

C - 問題

長さ $N$ の一列に並んだマス目について， $0, 1$ を書き込んでいく．ただし，そのうち $M$ 個のマス目には初めから数字が書き込んである．
同じ数字が隣り合わないように，2人のプレイヤーで順にマス目に数字を書き込んでいき，互いに最適な戦略をとる場合の勝者を求めよ．

C - 検討

パッと見解けそう．
「コインの山を取っていくやつ^[2]とか，テーブルにコインを置いていくやつみたい」
などと考えていた．

連続区間のそれぞれについて，

両端とも数字と接していない場合
片端だけ数字と接している場合
両端が同じ数字と接している場合
両端が異なる数字と接している場合

に分けて先手必勝・後手必勝が判定できるところまでは見つけたもののそこから先のアプローチが思いつかず時間切れ．

C - 解法

解説によれば，連続区間のそれぞれについてゲームのGrundy数を求め，その排他的論理和をとることで勝者が求まるとのこと．
組み合わせゲーム理論，二人零和有限確定完全情報ゲーム，不偏ゲームあたりのキーワードに辿り着けるまでググっていればよかった．

Grundy数の算出は，連続区間の長さ $n$ について，

両端とも数字と接していない場合: n % 2
片端だけ数字と接している場合: n
両端が同じ数字と接している場合: 1
両端が異なる数字と接している場合: 0

となるらしい．
両端とも数字と接していない場合は $n$ の偶奇で決まり，また両端が異なる数字と接している場合は後手必勝となり，他のケースでは先手必勝となることまでは検討できていたので悔しい．

C - ACコード（追試）

from bisect import insort


def main():
    N, M = map(int, input().split())
    arr = [[0, -1], [N+1, -1]]
    for _ in range(M): insort(arr, list(map(int, input().split())))

    xor = 0
    for i in range(M+1):
        if arr[i][1] == arr[i+1][1] == -1: xor ^= N%2
        elif min(arr[i][1], arr[i+1][1]) == -1: xor ^= arr[i+1][0] - arr[i][0] - 1
        elif arr[i][1] == arr[i+1][1]: xor ^= 1
        else: xor ^= 0

    print('Takahashi' if xor else 'Aoki')


if __name__ == '__main__': main()

感想

B問題は正直時間をかけても解けなさそうでした．一方でC問題はコンテスト時間中も終了後解説を見てもやはり自力で解け切れそうな感覚があったので，ここが取れれば大きく変わっていたと思います．
「調べれば出てきそう」という感覚を絶対に見逃さずキッチリと検索をかけることがめちゃくちゃ大事ですね．

脚注

レーベンシュタイン距離に似ていると思いました．Wikipedia: ハミング距離 ↩︎
Nimと呼ばれるそうです． ↩︎