問題ページ Problem - C - Codeforces 考えたこと 0と1の数からつくる01列の数特定できない？みたいになるけどできない 色々試してると前から貪欲に取ればいい気持ちになる 前から貪欲するのになぜかO(n^2)の方法しか思いつかない 括弧列みたいに+1/-1で累積…

問題ページ Problem - D - Codeforces 本番中は誤読で時間溶かして終了 解法 操作を逆順にして考える n=5のとき以下のようになる 15243 1 2435 1 2 354 1 2 3 45 1 2 3 4 5 もし最終状態で存在する位置から初期状態の位置を復元できれば答えが求められる 移…

考えたこと 0,1につながってない頂点はどう選ぼうが全く影響しなさそうなので2^(この頂点数)を掛けるとよさそう 実際は無向辺だけど有向辺として考えた方がよさそう サイクルの部分はどう選択しようが必ず連結性が保たれているっぽい 0と1が連結かどうかで場…

考えたこと 互い違いにおいていくのが一色を多く置く方法っぽい 一色でn個より多くあるのを条件を満たすようには置けない 逆に全部n個以下なら適当に互い違いにおいていくだけで構成できる 割とすぐ思いつけた ソースコード #include <bits/stdc++.h> using namespace std; </bits/stdc++.h>…

考えたこと 文字列長が1000なのに操作回数10回の制限でよくわからない とりあえず実験するけどよくわからない 括弧列を+1/-1に置き換えるやつをしてみる +1/-1の累積和で-1になったところがあったらそこを1回は操作しないとだめ 操作しないといけない場所が…

考えたこと ナップザックDPの復元とか考えつつ問題文を読むと制約的に論外 上から貪欲にとっていくやつを考える 7とかが3+4でつくれるけど先に6を取っちゃうとだめ 漸化式の性質を何かうまく使う…？ とりあえず漸化式の要素を順番に書いていってみるけどよく…

考えたこと 開括弧を選んでそれに対応する閉じ括弧のパターンが何通りあるか数えるみたいなので考える 正しい括弧列ならば開括弧の数は(括弧列の長さ/2)になるはず 与えられる括弧列の長さが最大40なのでその半分なら開括弧の選び方を全列挙できる もし開括…

考えたこと ある数字iを削除できるのは(j$k) == iとなるj,kが存在しない事みたいな気持ちになる 削除する対象の数字を探索するのにO(n)、削除判定O(n^2)で繰り返すのにO(n)で間に合いそうという気持ちになる 数字が削除できるならするを繰り返すコードを書く…

問題ページ Problem - D - Codeforces 考えたこと 頂点iに住んでいる人が2往復以上したほうがいいことはない 日付について区間[l,l+k]で議論をすると考える lより前の最も安いチケットで頂点0へ行き、l+kよりもあとの最も安いチケットで頂点0から出発する 各…

問題ページ Problem - C - Codeforces 考えたこと 順列を全部試すのが無理なのはそれはそう 制約がだいぶでかいのでdpはつらそう 隣同士をswapするとコストがどう変化するかを考える i,i+1をswapするとコストが +c[i]-c[i+1] 変化する sortするような感じで…

問題ページ Problem - D - Codeforces sparseTableのverifyとして解いた。 解法 区間の左端lを固定して考えてみる 区間[l,r]についてmax(a) - min(b)を考えると単調に増えていく max(a) - min(b) の数列は [-2, -1, -1, 0, 0, 0, 0, 1, 2, 3] みたいな単調増…

問題ページ Problem - D - Codeforces 考えたこと 部分列を全列挙とかそういう方向は不可能そうなので各要素が含まれる部分列の回数とかそういう方向で考える gcdがiとなるような部分列について考える (部分列の長さの和)*i がこんな部分列のスコアになる m…

問題ページ Problem - C - Codeforces 考えたこと s8pcで見た D - Driving on a Tree 1頂点から求めればいいだけなのでもっと簡単 頂点1を根とした木について考える 止まる頂点は葉以外ありえない 葉までの距離とその葉にたどりつく確率を求めれば期待値が求…

問題ページ Problem - B - Codeforces 考えたこと 二人席が2n個、四人席がn個あると考えればよさそう ぴったり座れるときに座らない方がいいことはなさそう 二人席と四人席のどちらを先に埋めるべきか 四人席*1より二人席*2の方があとあとぴったり埋められる…

考えたこと つくる数を決め打ったときにそれを実現できるかについて単調性がありそうなのでにぶたんができそう 二分探索部分でO(log(nm)) 判定部分をどうすればいいか 区間と言われたので終端でソートする 終端が遅いものをできるだけ残しておくと後半にも使…

問題ページ C: 高橋君と国家 - AtCoder Regular Contest 029 | AtCoder 考えたこと 最小全域木を求めたくなる 最小全域木で使わない辺はいらなさそう 根をcが最も小さい頂点とした根付き木を考えればよさそう 辺を使わないことにして別の頂点を使うみたいな…

問題ページ C - 高橋王国の分割統治 考えたこと 明らかに†全方位木DP†をしろという雰囲気をしている d[i] = (頂点iの部分木の頂点数) とする d_par は n-(進む頂点の部分木の頂点数) を渡せばよさそう テンプレに当てはめて書くと通った #include <bits/stdc++.h> using nam</bits/stdc++.h>…

問題ページ C - 高橋君、24歳 考えたこと 正しく手紙をいれた人のパターンはC(N,K)でO(K)で求まるので問題ない 問題は誤ったK人の方が何パターンあるか 組み合わせを頑張ってO(1)とか考えるけど思い浮かばない 樹形図を書いて小さいケースについて実験する k…

考えたこと 題意がよくわからないのでサンプルを試していると[1,upTo[i]]の要素がquantity[i]個存在するということらしい 区間でソートしておくとよさそう dp[i][j] = (i個目のhintまでの区間で偶数をj個使うのが可能か) みたいなDPを考える 状態数O(nq)、偶…