ARC105

AとBを解いてレートは微増。残りの時間は全部の問題を読んで考察することにした。

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

https://gyazo.com/965ded9d0465682f4ac72c2cd98a84b0

考えたこと

4つなので総当たりしても余裕

code:python

def 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:

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)

https://gyazo.com/7d51225e7e98ca2a831dfb93e0d14dfa

考えたこと

N=2で考える

XをX-xにした後に起こることは３パターン

まだ大きい時→さらに-x

要するにmod x

イコールの時→終了

小さい時→入れ替える

code:python

def solve(XS):

from math import gcd

from functools import reduce

return reduce(gcd, XS)

https://gyazo.com/869d181ba8e1c413aad6abdaae58d06b

考えたこと

Nが8なので全部の順番に対して調べても大丈夫

8!=40320なので

橋が1個の場合

v以下のグループに分けてl間隔にすれば良い

vより重いラクダがいる時のみ実現不能

複数の場合はどうすれば良いのか？

例えば同じ長さで耐荷重が大きい橋は無視して良い

同じ対耐荷重で短い橋も無視して良い

条件の強さに全順序が成立する？

しなそう

公式解説

よくわからない

全てのラクダの部分集合に対しその右端と左端の距離の最小値を前計算した後全順列をDPで探索

なるほど、すべての部分列に対して「その重量の和」が耐荷重viを超えてたら「両端はli以上離れてる」ということか、超えてなければ0でいいのね

部分列の重量の和は累積和で定数オーダー

M=100000個の橋から、与えられた重さwより耐荷重が小さくて、最も長いものを見つける必要がある

これを素朴にO(M)でやると間に合わなさそう

耐荷重でソートしておいて二分探索

Range max…セグメント木か？

Rangeの片端が固定だからあらかじめ累積max取っておけば良い

これで対数オーダー

その後どうする？

https://gyazo.com/0c7dfdbf04c7708f8ea734260f888b1c

考えたこと

Nimなので行動後xorが0なら勝ち

これを踏まえてコインの配置を競うゲーム

途中のxorが十分大きければ逆転できない？

No, たとえば4と3でxorが7の時、+1で0になりうる

可能な分配方法はすごく多いのでなんらかの圧縮が効くのだろうけど思いつかないなぁ

公式解説

Nの偶奇でゲームが変わる

先手は「最も多くのコインが乗った皿と最も多くのコインが入った袋を選ぶ」という手を繰り返す

この戦略にどうすれば気付けただろうか

試しに、3つの数が 10以下のときに全探索解法を実装した結果、先手は全く勝てない

山が多いと判定が大変で困る

山が多いと困るということは、逆側はなるべく一箇所に固めたくなるはずで、こういうときは過半数かどうかが大事なことが多い

なるほど

https://gyazo.com/b574e16286d6e80922242bcf36153666

考えたこと

全域木の辺の本数は決まってるからゲームにならないのでは？

ああ、そうか、木とは限らないのか

自分の番で1とNを繋いでしまうことを避け続けると、最終的に2つの完全グラフになる

開始局面で1にもNにも繋がってない頂点をどっちに繋ぐかで最終的な完全グラフの頂点数が変わる

これを競い合うゲーム

「頂点」ではなく「連結成分」か

完全グラフの辺の偶奇

頂点数を4で割った余りが1,2の時に奇数

ここから先がわからない

公式解説

どういう時に先手が勝つのか

関連

https://gyazo.com/7e2b618d0324a5fd22cea014ba400fc2

考えたこと

頂点を選んで、つながってる辺の色の反転をする

辺の色が青にできる

どういう時にできるのか？

試しに書く

二部グラフ？

Yes

反転だから同じ頂点を何度も選んでも意味がない

選んだ頂点と選んでない頂点にわける

選んだ頂点同士、選んでない頂点同士を結ぶ辺は存在しない(赤になってしまう)

これは二部グラフ

連結であることも条件

頂点数は17だからDFSしてもそんなに遅くない

2^17のグラフを全部試す？13万個くらいだからアリ(間違い)

2の肩は辺の数なので2^136、ダメです

DP的に探索空間を圧縮できる？

辺を1本足し引きしてなんとかならないか

二部グラフから辺を取ったものも二部グラフ

連結なグラフに辺を足したものも連結

両方なのでどうしたものやら

公式解説

連結二部グラフと考えたとこまでは良い

公式解説見てもさっぱりわからない