問題リンク 解説 prefixのxorの累積は制約からせいぜい1024通りしかありません。 よってA - Zero-Sum Rangesと同様の方法で、各値について何通りあるかを求めることができます。 計算量はです(定数？に1024がつきます) C++なら余裕を持って間に合います 提出…

問題リンク 解説 0が1つもない場合は逆元が存在するのでやるだけです。 0がある場合はもし塗りつぶしたので0が全て消えたのなら、0以外の全ての積から0以外の塗りつぶしたのを割りましょう。 全部きえてなければ0です。 以上で求めることができました。 提出…

問題リンク 解説 制約に森と書いています。ということでトポロジカル順にみていきましょう。 現在持っている値が正なら後に足していった方が得なのでつなげます。 負ならこれを足すと損なので、後回しにします。 復元はこの順番の管理をみればいいのでトポロ…

問題リンク 解説 葉から見ていきましょう。そうするとgood moodの人とbad moodの人の人数がそれぞれ一意に定まります。 上に登っていってる間はbad→goodにすることのみができ、このときgood - badは2増加します。 それをgood mood の人とbad moodの人が0以上…

問題リンク 落ちたので参考にしないでください(落としていただいた方ありがとうございます) 解説 明らかに線形計画法です。 Pythonのscipyにはシンプレックス法があるのでそれを貼ります。 これだけです。 落とすの頑張る人是非頑張ってみてください 提出コ…

問題リンク ごめんなさい！！のところ全く読んでなかったです。修正しました。 解説 DPで解きます。dpの定義を dp[i][j] := i番目まで見た時、j個分けている としましょう。こうしたとき、愚直にDPを遷移させると以下のようなコードになると思います。 もち…

問題リンク 解説 現状Fastestですのでその解説。 実はでこの問題を解くことができます。 詳しくはこの記事で jupiro.hatenablog.com 提出コード yukicoder.me

問題リンク 解説 いろいろ解き方があると思います。 ある程度1で埋めてしまいましょう。1を個置いたとき、のペアが素数になります。 次に2と6を1つずつおきます。2と6は1とペアを組むと素数になるので、ペアが増えます。 最後に、5を1つ置くと2個ペアが増え…

問題リンク 解説 遅延セグ木のノードに(総和、偶数の個数、奇数の個数)を持ちます。 更新クエリは(クエリ1パターン、加算)という風にします。 クエリ1パターンは3通りあって、 クエリ1パターンがない (実装の0) クエリ1パターンがある(偶奇はそのまま) (実装…

問題リンク 解説 前処理として、各要素の左にあるものかつその要素より大きいもので、最も近いものをメモしておきましょう。 これはstd::setなどで簡単にできます。 次にクエリを先に読んでが小さいものから見ていきます。 現状条件をみたしてるものをBITに…

問題リンク 解説 変更クエリなしで解くことから考えてみましょう。 dp[i] := i番目までみたときのとの組み合わせ とすると、との各桁の和はせいぜいであることから、2桁のみ考えたらいいことがわかります。 よって、s[i]となる組み合わせを、s[i-1]s[i]の2桁…

問題リンク 解説 いろいろやり方はあるらしいですが、マージテクを用いる方法を解説します。 この問題の解はとを辺で結んだときのになります。 ということでまず最初にこれを愚直に求めてしまいましょう。 その後はクエリ毎にマージをしていきます。 マージ…

問題リンク 解説 次数が10以下であるので、11個の異なる値が分かればラグランジュ補間を使うと次数をとして、で係数が分かります。 係数が分かれば、のはであるので全探索をしても十分間に合います。 提出コード codeforces.com

問題リンク 解説 が列目にいくときの、座標の最小値をとする。 ここで、明らかなこととして、以上のポーンの個数が個あれば、必ずであることが必要である。 で実はこれが十分であることも示せるらしい(Editorial曰くHallの定理を使うといいらしい) 上を実現…

問題リンク 解説 先手が必ず勝ちます。 常に変化するものが最大値になるように意識しましょう。 そうすると、 とすると、 であるとき、であるので、を投げると先手が勝ちます あとはこうなるようにするだけです。 提出コード codeforces.com

問題リンク テスターでした。 解説 として、根から木DPすると解けます。 子供から親にいくときに、距離が1ずつ増えることに注意しましょう。 提出コード yukicoder.me