📝

AtCoder Regular Contest 151 レポート

2022/10/17に公開約3,700字

摘要

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

ARC151

https://atcoder.jp/contests/arc151

コンテスト情報

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

A - Equal Hamming Distances

問題 / 解説

A - 問題

長さN01S, Tとハミング距離[1]で等距離にあるような長さN01Uのうち辞書順最小のものを求めよ.

A - 解法

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

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

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

  • sum(U) == (sum(S) + sum(T))//2となるように
  • 基本的にはU_i = 0cnt = 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()

https://atcoder.jp/contests/arc151/submissions/35724588

B - A < AP

問題 / 解説

B - 問題

(1, 2, …, 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]とか,テーブルにコインを置いていくやつみたい」
などと考えていた.

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

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

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

C - 解法

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

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

  1. 両端とも数字と接していない場合: n % 2
  2. 片端だけ数字と接している場合: n
  3. 両端が同じ数字と接している場合: 1
  4. 両端が異なる数字と接している場合: 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()

https://atcoder.jp/contests/arc151/submissions/35747618

感想

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

脚注
  1. レーベンシュタイン距離に似ていると思いました.Wikipedia: ハミング距離 ↩︎

  2. Nimと呼ばれるそうです. ↩︎

Discussion

ログインするとコメントできます