AHC011でやったことの解説

この記事を書いた背景

こんにちは。競技プログラミングのコンテストに参加しているyunix (https://atcoder.jp/users/yunix )です。 最近行われたAtCoderAHC011に参加して33位でした。 マラソン初心者なりに色々やってみて学びが多かったので、それについて備忘録として記事を書きました。

また、長期のマラソンマッチに時間をかけて参加するのは初めてだったのですが(と思ったけれどHTTFは割とちゃんとやってたな...)、コンテスト中に色々な方法を試して挙動がどう変わるかを調べたり、処理速度を改善したり試行錯誤することが本当に面白かったです。 試行錯誤してプログラムを書くことが面白かったということを伝えたい、AHCのようなマラソンマッチのコンテストに興味をもつ人が増えてほしいという気持ちで記事を書きました。

この記事の内容

  • AHC011の概要
  • 解法の解説
  • 学びを得たこと
続きを読む

CADDi 2018 D Harlequinの解説

CADDi 2018 D Harlequinの解説

D - Harlequin

問題概要

N色のリンゴがあり、各色のリンゴはそれぞれa_i個ある。
先手と後手が以下の行動を交互に行うようなゲームを考える。

  • 一個以上のリンゴを選んで食べる。ただし、同じ色のリンゴを2個以上食べてはいけない。

このとき、最後のリンゴを食べたほうが勝ちになるとする。
先手と後手が双方最善を尽くした時、どちらが勝つか?

考え方の方針

この手のゲームの問題は、"先手必勝の局面"の特徴は何か、ということを考えるとうまく行くことがあります。
もっと簡単な例でいうと、子供のころにやった遊びで、

  • 先手と後手が交互に数字を1から昇順に数える
  • それぞれの手番では1つ以上3つ以下まで数を数えることができる
  • 最後に30を言ったほうが勝ち

というものがあると思います。

このゲームは

  • 30を言ったほうが勝ち
  • 26を言える状況ならば26を言った後に相手に手番を譲る。そうすると相手は27~29のいずれかまでしか数えることができず、どの場合でも自分のターンで30を言うことができる。したがって26を言えたら勝ち。
  • 同様の理屈で22を言ったら勝ち
  • 同様の理屈で2を言ったら勝ち

というわけで、正しくやれば先手が必ず勝ちます。
最初のターンで2までをカウントして、次に相手が3~5のどの数値までを数えたとしても、次に6を言って手番を譲り... ということを繰り返せば最終的に30を言うことができます。

この手のゲーム(いわゆる石取りゲーム)では、"相手が何を言っても最終的には勝てる"というような状態(必勝状態*1 )を決して手放さないような手順を考えることが大事になることが多いです。
この30を言うゲームでの必勝状態は"自分の手番で2+4nの数値までを言った"という状態です(n>=0)。
相手がその次にどのような手を指したとしても、自分のターンでまたこの状態に持ってくる、ということを繰り返すと最終的に勝つことになります。

NimやNimKなどで出てくるGrundy数の解析によって問題を解くのもこの考え方の延長で、"最善を尽くせば後手が必ず勝てるような局面"はGrundy数が0になっていて、局面のGrundy数を数えることで先手と後手のどちらが勝つかがわかります*2

というわけで、このゲームでもそのような"先手か後手のどちらかが必ず勝てる状態"がないかを探してみましょう。

どういうときに必勝の局面が現れるか?

まず簡単のため、一色しかリンゴがない場合を考えましょう。
リンゴの数が

  • 1個の時: これは先手が1個食べておしまいなので、先手勝ち
  • 2個の時: 先手は1個しか食べることができず、一個残った状態で後手の手番にわたる。したがって後手勝ち
  • 3個の時: 同じ理屈で先手の勝ち
  • 以下省略

というわけで、リンゴの数が奇数: 先手勝ち、偶数:後手勝ち、という結果になります。

このことから、どうも各色のリンゴの数の偶奇が大事そうな雰囲気がしてきます*3
最後のリンゴを食べたほうが勝ちなので、リンゴの数が偶数個の時に手番を譲られたほうが不利のような気がしてきます。
そこで、このゲームをプレイするときの戦略として、

  • 各色のリンゴについて、リンゴの数が奇数ならばリンゴを食べる、偶数ならば食べない

という方針でやったら勝てそうです(今は全部偶数の場合は考えないことにします)。

この方針で実際にゲームに勝つことができて、

  • 相手に手番がわたるときには必ず各色のリンゴの数はすべて偶数になっています(0も偶数です)。
  • 相手がどのような手を指してきても、相手が食べた色のリンゴを次のターンで食べることで、その次もすべての色のリンゴが偶数の状態で相手に手番を渡すことができます。
  • 最終的に勝てる人は手番で残っている色のリンゴの数が1個だけになっているような人である(つまり奇数)。したがって、偶数の状態で手番が回ってくる人は必ず負けてしまいます。

というわけで、このゲームにおいて、手番が回ってきたときに"すべての色のリンゴの数が偶数"の時は必ず負ける、逆に"どれか一つでもリンゴの数が奇数の色があるとき"には必勝になります。
最初の局面のリンゴの数、すなわち各a_iの偶奇を判定すればよく、コード自体は以下のようにとてもシンプルになります。

提出コード

Submission #25883195 - CADDi 2018

def main():
    N = int(input())
    a = [int(input()) for _ in range(N)]
    odd_count = sum([(val%2) for val in a]) # aの中の奇数の数の個数を数える
    if odd_count==0: # 奇数の数が0の時、すなわちすべて偶数の時には先手負け
        print("second")
    else:
        print("first")
    
if __name__ == "__main__":
    main()

*1:すいません、これは勝手に名前を付けただけです。この記事の外では使われていないので気を付けてください。

*2:ここではGrundy数については解説しません。たくさんの人が良い記事を書いてくれているので、そちらを探してみてください。AtCoderではABCの水色~青くらいの問題でGrundy数の解析が前提になる問題が出ることがあると思います。Grundy数を知っておくと、与えられた問題をどうやってGrundy数を数えるか、という問題に言い換えることができ、解答への糸口を得られることが多いです

*3:ここから先はあんまり論理的な展開ではないので語尾を濁しています。上のように簡単な例を使って考えると結果的に正しい方針を思いつけることが多いと思います。方針を思いつくまではエスパーでも、それが正しいことが説明できればOKだと思います。

ABC209

ABC 209 D - Collisionの解説

問題概要

 N個の町がN-1本の道路でつながっており、街には1からNの番号が付いている。道路を通ってどの町からどの町へも移動できる。また道路はすべて同じ長さである。

 Q個のクエリが与えられて、各クエリでは町の番号c, dが与えられる。cとdを同時に二人の人が出発し、二人とも同じ速さで最短経路を通ってもう一方の町に向かう。この時、二人の人が出会うのは町で出会うか道路上で出会うか判定せよ。

制約

2 ≦ N ≦ 10^5

1 ≦ Q ≦ 10^5

問題の解法

最初に考えるポイントは二つあります。

  • N個の町がN-1本の道路でどの町からどの町へも移動できるということは、町と道が木構造のグラフになっている。したがって2つの町の間の最短経路は一意に定まる。
  • 町c, d間の距離が偶数ならば二人は町で出会う。奇数ならば道路上で出会う。

このことによって、町と道からなる木構造のグラフ上で、任意の2頂点間の距離の偶奇がわかればよいことになります。

もちろんクエリのたびに距離をBFSなどで求めていては計算量がO(NQ)になってしまい、間に合いません。どのようにすれば効率化できるでしょうか? 以下のように絵を描きながら考えてみると、ノードの深さを利用すればうまく行くことがわかります。

 

下の図のような構造の木を例にとって考えてみましょう。

町Aと町Bの間の距離は、二つの町が根を介して反対側にあるので、根からの深さの和と等しくなり、5になることがわかると思います。このことから、ノードの深さが役に立ちそうということが示唆されます。

f:id:yunix_kyopro:20210711012229p:plain

 
次に、下のように町Aと町Cの場合について考えてみましょう。町Aと町Cは町Dを経由して最短距離は3になります。この場合はAとCの深さの和5は最短距離とは等しくなりません。

しかし町A → 町D → 町Cという最短経路と、町A→根→町Cという経路(この場合の距離はA, Cの深さの和)で違う点は、下図の赤い矢印の部分だけになります。この赤い矢印の部分はDと根の間を往復しているので、どのような場合でも赤い矢印の距離の合計は偶数になります。

したがって、(AからCへの最短距離)と(AとCの深さの和)の違いは必ず偶数になり、この二つ数の偶奇は一致します。


この性質は一般的な木構造のグラフの任意の2頂点間で成立し、いわゆるLCAをこの図でいうDとして考察をすれば同じ結果になります。もちろん、A, Cの深さだけがわかれば偶奇の判定ができるので、LCAを陽に求める必要はありません。*1

f:id:yunix_kyopro:20210711012916p:plain

 

以上の考察から、元の問題は二つの頂点の深さの和を計算して、偶数ならば町、奇数ならば道となることになります。*2
したがって、適当な頂点を根とした木を作って、各ノードの深さを先に計算しておけば、各クエリに対してO(1)で回答をすることができます。

 

提出コード

Submission #24149505 - AtCoder Beginner Contest 209

from collections import deque


def main():
    [N, Q] = [int(x) for x in input().split()]

    # グラフの初期化
    graph = [[] for _ in range(N+1)]
    for _ in range(N-1):
        [a, b] = [int(x) for x in input().split()]
        graph[a].append(b)
        graph[b].append(a)

    # 深さを記録するリスト
    depth_vec = [-1 for _ in range(N+1)]

    # 1を根とする根付き木を作り、各頂点の深さを記録する
    queue = deque()
    queue.append((1, 0))
    while len(queue) > 0:
        (node, depth) = queue.pop()
        depth_vec[node] = depth
        for child in graph[node]:
            if depth_vec[child] >= 0:
                continue
            queue.append((child, depth+1))

    # クエリに解答する
    for query in range(Q):
        [c, d] = [int(x) for x in input().split()]
        if (depth_vec[c] + depth_vec[d]) % 2 == 0:
            print("Town")
        else:
            print("Road")


if __name__ == "__main__":
    main()

 

*1:doublingを使えばLCAをO(logN)で求めることができるので、LCAを求めても一応通りますが、実装が複雑になるだけでかなり無駄が多いです。まあそれをやった人はLCAをライブラリ化して木上の2点間の距離を簡単に求められるようにしていた人が多いと思うので、情状酌量の余地はあると思います(私のことです。反省しています。)。

*2:まあ、ノードの深さの偶奇というのは二部グラフの色分けと全く同じなので、公式解説と結局は同じことをやっていることになりますね。