arc105

NISHIO Hirokazu [Translate]
ARC105
AとBを解いてレートは微増。残りの時間は全部の問題を読んで考察することにした。
帰着する力をどうすれば鍛えられるのかについて、難しい問題に対して自分が考えるプロセスを言語化し、それを公式解説とか強い人の解説記事と照らし合わせて食い違いを見つけるって戦略でやってみようと考えている。

ところで僕は956位、パフォーマンス1357なのだけど、同じ点数で最も速い人は599位で1657なので、実は灰色難易度問題の回答速度を上げるのが短期的には有効なのかも知れないなあ。

A - Fourtune Cookies
考えたこと
4つなので総当たりしても余裕
pythondef solve(XS):
    S = sum(XS)
    if S % 2 == 1:
        return False
    goal = S // 2
    for i in range(16):
        s = 0
        for j in range(4):
            if i & 1:
                s += XS[j]
            i >>= 1
        if s == goal:
            return True
    return False


def main():
    # parse input
    XS = list(map(int, input().split()))
    if solve(XS):
        print("Yes")
    else:
        print("No")
ビットで部分集合全体を探索してる
公式解説
ソートしても一般性を失わない
ソートされてる場合に等号条件を満たすパターンは2つしかない
DとC、DとBが同じグループに入るとダメだから
D + C > B + A (D > B, C > A)
D + B > C + A (D > C, B > A)

B - MAX-=min
考えたこと
N=2で考える
XをX-xにした後に起こることは３パターン
まだ大きい時→さらに-x
要するにmod x
イコールの時→終了
小さい時→入れ替える
これユークリッドの互除法だな
pythondef solve(XS):
    from math import gcd
    from functools import reduce
    return reduce(gcd, XS)

C - Camels and Bridge
考えたこと
Nが8なので全部の順番に対して調べても大丈夫
8!=40320なので
橋が1個の場合
v以下のグループに分けてl間隔にすれば良い
vより重いラクダがいる時のみ実現不能
複数の場合はどうすれば良いのか？
例えば同じ長さで耐荷重が大きい橋は無視して良い
同じ対耐荷重で短い橋も無視して良い
条件の強さに全順序が成立する？
しなそう
公式解説
よくわからない
>全てのラクダの部分集合に対しその右端と左端の距離の最小値を前計算した後全順列をDPで探索
https://twitter.com/googol_s0/status/1315308927156846593?s=21
なるほど、すべての部分列に対して「その重量の和」が耐荷重viを超えてたら「両端はli以上離れてる」ということか、超えてなければ0でいいのね
部分列の重量の和は累積和で定数オーダー
M=100000個の橋から、与えられた重さwより耐荷重が小さくて、最も長いものを見つける必要がある
これを素朴にO(M)でやると間に合わなさそう
耐荷重でソートしておいて二分探索
Range max…セグメント木か？
Rangeの片端が固定だからあらかじめ累積max取っておけば良い
これで対数オーダー
その後どうする？
最長経路探索をDPするらしい
ライブラリを使い回すなら、負の費用で最小費用流でもいいのかな

D - Let's Play Nim
考えたこと
Nimなので行動後xorが0なら勝ち
これを踏まえてコインの配置を競うゲーム
途中のxorが十分大きければ逆転できない？
No, たとえば4と3でxorが7の時、+1で0になりうる
可能な分配方法はすごく多いのでなんらかの圧縮が効くのだろうけど思いつかないなぁ
公式解説
Nの偶奇でゲームが変わる
偶奇で場合わけすべきだったな
>先手は「最も多くのコインが乗った皿と最も多くのコインが入った袋を選ぶ」という手を繰り返す
この戦略にどうすれば気付けただろうか
>試しに、3つの数が 10以下のときに全探索解法を実装した結果、先手は全く勝てない
https://maspypy.com/atcoder-参加感想-2020-10-12arc105
なるほど小さい問題を力づくで解いて観察か
>山が多いと判定が大変で困る
> 山が多いと困るということは、逆側はなるべく一箇所に固めたくなるはずで、こういうときは過半数かどうかが大事なことが多い
https://beet-aizu.hatenablog.com/entry/2020/10/12/140532
なるほど

E - Keep Graph Disconnected
考えたこと
全域木の辺の本数は決まってるからゲームにならないのでは？
ああ、そうか、木とは限らないのか
自分の番で1とNを繋いでしまうことを避け続けると、最終的に2つの完全グラフになる
開始局面で1にもNにも繋がってない頂点をどっちに繋ぐかで最終的な完全グラフの頂点数が変わる
これを競い合うゲーム
「頂点」ではなく「連結成分」か
完全グラフの辺の偶奇
頂点数を4で割った余りが1,2の時に奇数
ここから先がわからない
公式解説
どういう時に先手が勝つのか
元のグラフの頂点数の偶奇で場合わけ
関連
Tutte の定理と構造が似てるらしい

F - Lights Out on Connected Graph
考えたこと
頂点を選んで、つながってる辺の色の反転をする
辺の色が青にできる
どういう時にできるのか？
試しに書く
二部グラフ？
Yes
反転だから同じ頂点を何度も選んでも意味がない
選んだ頂点と選んでない頂点にわける
選んだ頂点同士、選んでない頂点同士を結ぶ辺は存在しない(赤になってしまう)
これは二部グラフ
連結であることも条件
二部グラフであるかどうかの判定はDFSで塗り分けて矛盾が起きなければOK 二部グラフ判定
頂点数は17だからDFSしてもそんなに遅くない
2^17のグラフを全部試す？13万個くらいだからアリ(間違い)
2の肩は辺の数なので2^136、ダメです
DP的に探索空間を圧縮できる？
辺を1本足し引きしてなんとかならないか
二部グラフから辺を取ったものも二部グラフ
連結なグラフに辺を足したものも連結
両方なのでどうしたものやら
公式解説
連結二部グラフと考えたとこまでは良い
公式解説見てもさっぱりわからない