G - Minimum Permutation メモ Li(v) := vが現れるインデックスの内最も左 Ri(v) := vが現れるインデックスの内最も右 とする 辞書順最小なので、次の数にできる物の内最小のものを貪欲に決めていきたい。 値vを先頭にできるかの判定を考える。 l = Li(v)と…

セグ木で差分を更新する方法が勉強になった。 F - Insertion Sort ---------------------------------------------------- 問題 長さNの順列Pが与えられる。 左からi番目の値はPiである。 以下の操作を使ってPiを昇順に並べたい。 ・i(1<=1<=N)を選ぶ。コス…

atcoder.jp 問題 順列P, Qが与えられるときに、連続するとは限らない部分列P', Q'を長さKで取る 任意のiについて、Q'i がP'iの倍数になっているとするとあり得る最大のKは何か 解答 全てのiについて、Piに対して同時に選べるQjの組の合計の合計は調和級数よ…

C: 茶碗と豆 - AtCoder Regular Contest 038 | AtCoder豆一つをnimの山として考えられる。 よって、全ての茶碗についてgrundy数を求め、A[i]回xorを取った物たちをxorすればいい。難しいのはgrundy数を求める方法。 区間 [ i - c[i] , i ) に含まれない最小…

G - Perm Query問題文より、全ては周期40以下の巡回群である。 あるli~riが揃うまでにはそれらの周期の最小公倍数回だけ操作が必要である。 区間の最小公倍数はセグ木で持てる。 また、操作の和も調べられるので持てる。Submission #3879423 - Japan Alumni …

D: タコヤキオイシクナール - AtCoder Regular Contest 008 | AtCoder 問題概略 N個の箱が一列に繋がって並んでおり、それらは実数(a,b)を持つ。 箱に数字を渡すとその数字は a * 渡された数 + bに変化して次の箱に渡される。 (a,b)は(1,0)で初期化されてい…

B: Sprinkler - ウクーニャたんお誕生日コンテスト | AtCoder お誕生日おめでとうございます（こっそり） 問題概略 N個の数が並んでいる。連続した数を選択して、1減らす作業がM回できる。 ただし、0は選択できない 減らした数の合計最大値を求めよう 制約 1…