問題ページ 解法 サンプル2について考える． 4 ADD 1 ADD 2 ADD 3 ACCEPT 2 ACCEPTが正常に行われるには2がBUYの最善かSELLの最善である必要がある．したがって2未満はBUY，2より大きいものはSELL以外にすることが不可能でどちらにすべきか確定する． このsa…

問題ページ 解法 まず区間 を一つ固定して，この区間が条件を満たせるかの判定を考える． ビットが立っている数が同じであれば作れる数字の集合は同じなため の値は本質ではなくビットが立っている数が大事． のビットが立っている数とする． とできる方法が…

問題ページ 解法 2以外の偶数は素数にならないことからa[i]とa[j]の偶奇が一致するときa[i]+a[j]は素数にならない a[i]+a[j]が素数であれば頂点iと頂点jを結んだグラフは二部グラフになる 二部グラフから各頂点の次数が2になるように辺集合を選ぶ問題に帰着…

問題ページ 解法 どのような状態が勝ち/負けなのか考える。n=6で試してみる。0が4個以上の場合操作できないのでその時点で負けである。0が3個以下の場合、0が4個以上になるように操作して相手に渡せばよいので勝ちになる。1が4個以上の場合、どう操作しても0…

問題ページ 解法 木において最大マッチングを考える場合、葉が隣接する辺から貪欲に取っていけばよい。葉が隣接する辺を取らなかったことでマッチングに追加できる辺の本数は高々1本なので取らないことで得をすることはないからである。よってTrie木で根から…

問題ページ 解法 パスの端点を一つも含まないような範囲 範囲に入った後出ることを繰り返すので返ってくる値は必ず偶数 パスの端点を両方含むような範囲 範囲から出た後入るを繰り返すので返ってくる値は必ず偶数 パスの端点を片方だけ含む範囲 範囲内と範囲…

問題ページ 考えたこと 完全グラフだと辺の本数が多すぎてつらそう 木の任意の頂点間を移動できると思った方がよさそう 任意の順番で木上を移動するとき最長となる経路長を答える問題になった よくわからないので実験する ある頂点からはじめて最も遠い頂点…

全部解いたので略解と感想メモ Session1 A: 算数 B: 各文字の出現回数を数える C: binom(32, 6) の全探索 D: 8*5n-1 E: 各数は高々1回しか消されないのでsetとかで愚直に書いてもok F: 最小値の最大化と言われたので二分探索を考える 満足度を決めると各果物…