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

https://codeforces.com/contest/1633/problem/E 問題 N頂点M辺の連結無向グラフが与えられ、各辺にはwiの重みがある。 f(x) := sigma(wi - x)が最小になるように取った全域木のコスト とした時に、10^7個のxが与えられる。 全てのxについてf(x)を計算し、そ…

https://codeforces.com/contest/1593/problem/D2 問題 N要素の整数列Aと以下の操作が与えられる ・あるiについてA[i]-=Kする あるKについて上の操作を任意の回数行った後に 同じ数字が過半数を占めました 考える最大のKを求めよ Kには単調性が無いので二分…

O - Computer どういう思考で解いたかを書き下します indexは断わりが無ければ0-indexedです まず当然ですがコンピュータの性能は買うたびに良くなると考えていいです。 そして、この問題は使うコンピュータの性能ごとに、区間を分割する問題として考える事…

atcoder.jp 解説をみてピンと来なかったところを補足する形の自分用のメモです。 まず、K個を足して平均に置き換えるという操作は分かりにくいので 上のように操作をK分木で表す事にする そして、1の頂点の深さをa1....am 0の頂点の深さをb1.....bnとする す…

atcoder.jp 主客転倒 問題 左右対称な区間が与えられ、それぞれの区間には得点がある 得点は中心に近いほど高い。 D以上の間隔で点をN個まで置く時、得点の合計を最大化せよ 問題を言い換えていきます。 まず隣り合う点の距離はDだとして良いです なぜなら点…

atcoder.jp 解法 割り振り方において、Mで割った余りが異なる物同士は互いに影響を及ぼさないので、 割った余り毎にどう割り振るか組み合わせで考える。 また、K個ちょうどで考えると難しいので、K個のグループに分けるが0人のグループがあってもいいという…

D - Unique Subsequence 考えたこと dp[i] := iを先頭に使ったときの答えとして iを後ろから更新する時にどう遷移するかを考える 以降A[i]の後ろにA[j]から始まる部分列を付け加えられる事を iにjを加えられると呼ぶことにする 上の図を見るとA[i]==A[j]かつi

C - Maximize GCD 考えたこと 今回は関係ないが、よくある最大公約数の性質として gcd(A1, A2, ... , An) | sum(A1, A2, ... , An)となる 似た問題で何回かi, jを選びA[i]++, A[j]--としたうえでの最大公約数を最大化するものがあったが、それにはこの性質が…

問題文 https://atcoder.jp/contests/abc173/tasks/abc173_e 解法 (editorialとは違う方法です) まず、答えの正負で場合分けします。 負の数を偶数個選べる場合は正、選べない場合答えは負となります。(ここでAに0があれば答えを0に出来る事に注意) この上で…

https://drken1215.hatenablog.com/entry/2020/03/08/202600 { in(N); na(A, N); int res = 0; rep(k, 30) { vi B = A; rep(i, N) { B[i] %= bit(k + 1); } sort(B); //kbit目が立つような相手を数える int cou = 0; rep(i, N) { auto cou_range = [&](int l…

https://atcoder.jp/contests/arc067/tasks/arc067_c hotmanさんの https://blog.misw.jp/entry/2019/12/18/000000 の記事でGrouping がfpsで解けるとあったので解いてみました 解説 「i人含まれるグループの数は0かc~d人」というのが扱いづらいので、一つの…

https://atcoder.jp/contests/keyence2020/tasks/keyence2020_d 最終的にひっくり返るカードを決め打つと、最終的な数列が定まります ひっくり返るカードは奇数個移動し、その他のカードは偶数個移動することを考えると それぞれの移動後のパリティが決まり…

AGC2完 2100パフォで微妙だった あと1問解ける事が重要だと思った

デバッグ能力の不足 コードを見ずに、とりあえず一行ずつ実行することが多い.空中で考える ミスが起こりにくいように 一つ一つの意味を明確にして実装するべき

Problem - E1 - Codeforces 解法mを昇順にpを降順にソートして、後ろから考える。ここでiを買う必要が無いのは、自分の前にいるi人とi以降で買ったj人でi+j >= m[i]となる場合であるこの時、i-1までを埋めることが出来ればiまで埋まる事が分かるi+j< m[i]な…

http://codeforces.com/contest/1153/problem/F 問題 区間[0,L]で、N個のランダムな区間が作られる。 K個以上の区間で覆われる区間の長さの期待値を求めろ。 解法 区間のうち、左端の点をl,右端の点をrと呼ぶ ここでl,rをN個ずつ決めた時、どのl,rを結んでも…

理解するのに時間がかかったので書いてみます 問題文 https://atcoder.jp/contests/agc039/tasks/agc039_c まず、文中の操作は下のように、一番右のビットを反転して左へ移動する操作と言い換えられます N回の操作で全ビットが反転し、2N回の操作で元に戻り…

https://yukicoder.me/problems/no/832 解法 まず与えられた14枚があがりの形であるか判定する方法を考えます これが難しいのは、ABCやBBB等の二つの揃え方があるためです ここで、AAAは一つしか作れない（Aは4枚しかない）事に気付くと、同じ3つ組を作る数…

https://atcoder.jp/contests/ddcc2016-final/tasks/ddcc_2016_final_c 解法 ランレングス圧縮する 最初に追加した区間がtのどの位置か決めると組み立て方が一意に定まる 累積和 https://atcoder.jp/contests/ddcc2016-final/submissions/5008563 void solve…

https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_d 解法 sをソートして、s[i]を最初に使った場合の合計を考えていく。 ここでx%s[i] はs[i] より小さくなるため、今後s[i]より右でmodを取っても答えは変わらない。 よってこの答えは s[0~i…

https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_e 解法 ほとんどの状態でi番目に黒を引く確率は1/2となる 例外はi番目に「黒が残っていない場合」と「白が残っていない場合」である i番目に黒が残っていない確率をpiとすると pi = p(i-1)…

https://atcoder.jp/contests/code-festival-2018-qualb/tasks/code_festival_2018_qualb_d てんぷらさんのツイートとコードを参考にしました https://twitter.com/tempura_cpp/status/1051475771221401600 https://atcoder.jp/contests/code-festival-2018-…

https://atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_g 解法 それぞれの籠に大きさを決める aiをいれた際、全体の合計はai*籠の大きさ となるためaiが大きいものほど小さい籠に入れたいと分かる よって籠の大きさを…

https://atcoder.jp/contests/code-festival-2017-qualc/tasks/code_festival_2017_qualc_d 思考 回文の条件は奇数個のアルファベットが高々1つ アルファベットはbitで持てる いくつかの区間に分割するdpか、左から貪欲に取ればよさそう 貪欲は駄目だった だ…

https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_d 解法 11110111のように0の左右に1が並んでいるとき、左か右の個数回だけ操作でき、逆側の1の個数を1減らす 上のように左右に1を持つ0について、左か右の1をいくつか…

https://atcoder.jp/contests/cf17-final-open/tasks/cf17_final_d 教育的典型 思考 参加者の順番が決まったらdpでできそう。 というかそうでもないと解ける気がしない。 順番を決める時の典型テクで「隣り合う二項間の優先順位が決まればソート出来る」とい…

https://atcoder.jp/contests/cf17-tournament-round2-open/tasks/asaporo2_a 解法 難しいので、全頂点が無色の時を考える。 短い辺を貪欲にk-1個選んで1 - 2 , 2 - 3 のように繋げそう しかし、閉路に含まれる辺をすべて選ぶ事はできないので、最小全域木に…

https://atcoder.jp/contests/cf17-tournament-round1-open/tasks/asaporo2_c 解法 対応の取れた括弧列で、二点の括弧を入れ替えることを考える。 すると、端以外の括弧を入れ替えた場合、操作後も対応が取れている事が言える。 よって、端を除く2n-2個でa,b…

https://atcoder.jp/contests/abc122/tasks/abc122_d 解法 dp[i][m] := 長さがiで後ろ3文字がmとなる個数として、後ろに足した文字によって dp[i+1][t] += dp[i][m] と遷移したい 3文字の状態はACGT をそれぞれ1234とみなして10進数で扱うとわかりやすい 後…