AとBを解いてレートは微増。残りの時間は全部の問題を読んで考察することにした。 帰着する力をどうすれば鍛えられるのかについて、難しい問題に対して自分が考えるプロセスを言語化し、それを公式解説とか強い人の解説記事と照らし合わせて食い違いを見つけるって戦略でやってみようと考えている。
ところで僕は956位、パフォーマンス1357なのだけど、同じ点数で最も速い人は599位で1657なので、実は灰色難易度問題の回答速度を上げるのが短期的には有効なのかも知れないなあ。
- 考えたこと
- 4つなので総当たりしても余裕 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:
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)
- 考えたこと
- N=2で考える
- XをX-xにした後に起こることは３パターン
- まだ大きい時→さらに-x
- 要するにmod x
- イコールの時→終了
- 小さい時→入れ替える
- これユークリッドの互除法だな python
- まだ大きい時→さらに-x
def solve(XS):
from math import gcd
from functools import reduce
return reduce(gcd, XS)
- 考えたこと
- Nが8なので全部の順番に対して調べても大丈夫
- 8!=40320なので
- 橋が1個の場合
- v以下のグループに分けてl間隔にすれば良い
- vより重いラクダがいる時のみ実現不能
- 複数の場合はどうすれば良いのか？
- 例えば同じ長さで耐荷重が大きい橋は無視して良い
- 同じ対耐荷重で短い橋も無視して良い
- 条件の強さに全順序が成立する？
- しなそう
- Nが8なので全部の順番に対して調べても大丈夫
- 公式解説
- よくわからない
-
全てのラクダの部分集合に対しその右端と左端の距離の最小値を前計算した後全順列をDPで探索
- なるほど、すべての部分列に対して「その重量の和」が耐荷重viを超えてたら「両端はli以上離れてる」ということか、超えてなければ0でいいのね
- 部分列の重量の和は累積和で定数オーダー
- M=100000個の橋から、与えられた重さwより耐荷重が小さくて、最も長いものを見つける必要がある
- これを素朴にO(M)でやると間に合わなさそう
- 耐荷重でソートしておいて二分探索
- Range max…セグメント木か？
- Rangeの片端が固定だからあらかじめ累積max取っておけば良い
- これで対数オーダー
- その後どうする？
- 考えたこと
- Nimなので行動後xorが0なら勝ち
- これを踏まえてコインの配置を競うゲーム
- 途中のxorが十分大きければ逆転できない？
- No, たとえば4と3でxorが7の時、+1で0になりうる
- 可能な分配方法はすごく多いのでなんらかの圧縮が効くのだろうけど思いつかないなぁ
- 公式解説
- Nの偶奇でゲームが変わる
- 偶奇で場合わけすべきだったな
-
先手は「最も多くのコインが乗った皿と最も多くのコインが入った袋を選ぶ」という手を繰り返す
- この戦略にどうすれば気付けただろうか
-
試しに、3つの数が 10以下のときに全探索解法を実装した結果、先手は全く勝てない
-
山が多いと判定が大変で困る
-
山が多いと困るということは、逆側はなるべく一箇所に固めたくなるはずで、こういうときは過半数かどうかが大事なことが多い
- Nの偶奇でゲームが変わる
- 考えたこと
- 全域木の辺の本数は決まってるからゲームにならないのでは？
- ああ、そうか、木とは限らないのか
- 自分の番で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本足し引きしてなんとかならないか
- 二部グラフから辺を取ったものも二部グラフ
- 連結なグラフに辺を足したものも連結
- 両方なのでどうしたものやら
- 公式解説
- 連結二部グラフと考えたとこまでは良い
- 公式解説見てもさっぱりわからない
