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進数で扱うとわかりやすい 後…

https://atcoder.jp/contests/cf16-final-open/tasks/codefestival_2016_final_d 解法 modを取って対応する二つの集合のマッチングを考える ここで、仮に元の数が同じもの達のペアを作った時、使われなかったものを優先的にマッチングに使う（ここで全て使い…

https://atcoder.jp/contests/cf16-tournament-round2-open/tasks/asaporo_e 解法 距離が1の時以外は右に移動したほうがいい En = p * (En-2) + (1-p) * (En) + 1 En = En-2 + 1 / p よって E(2n+1) = E1 + (1/p)*n E(2n+2) = E2 + (1/p)*n また、E1,E2は1/p…

https://atcoder.jp/contests/cf16-tournament-round1-open/tasks/asaporo_c 解法 最小全域木で使わない辺は使わないため、候補を4000本まで減らせる（300点） ここで問題はstがコスト0で繋がっているとみなせるため、最小全域木のst間の最も重い辺を削除で…

C - Min Cost Cycle 解法 n個を並べて、辺のコストをaかbとしていい この時iについてabの選び方は以下の4通りある これらを輪にできるようなabの取り方は実現できる 全てa,全てbのような取り方は出来ることがわかる abを取り入れるとどうなるだろうか あるa…

C - +/- Rectangle 解法 H % h || W % wの時にできそう サンプル1のように、基本1で区間に一つだけ-を入れて合計が-1になるようにしたい よくよく考えると基本の数が大きいほど有利（構築でありがち） Submission #4640917 - AtCoder Grand Contest 016 void…

C - Interval Game Submission #4640210 - AtCoder Grand Contest 025 解法 Aさんの動きは「一番近い区間の端まで移動する」と言い換えられる すると、左右の振れ幅が大きくなるようにすれば答えは最大に出来る 左が大きい順と、右が小さい順の二つのソート…

C - Nuske vs Phantom Thnook 解法 木の数は頂点-辺の数らしい ので、二つを二次元累積和で持てばいい しかし、辺の数を二次元累積和で計算すると赤と緑の分答えが大きくなってしまうので、「dh[i][h] := 列i-1とiの間がhまでで繋がっている量」のようにして…

C - Differ by 1 Bit Submission #4602092 - AtCoder Grand Contest 031 snukeさんのコードを参考にしました。 方針は解説生放送と同じです。 解法 まず遷移は奇数回なので、aとbの立っているbitの数が偶数差ならNO。 それ以外の場合はYES。（証明できないが…

B - Reversi 解法 まず、操作に選ばれた区間は交わらないと考えていい。 ここで、選ばれなかった石を長さ一の区間とみなすと、この問題はN個の石をいくつかの区間に分割する問題となる。 区間が交わらないことから、dp[i] := iまでを分割する方法としてまと…

No.798 コレクション - yukicoder 思考 無料で手に入るというのを無視して 買うもの選ぶという風に問題を読み替えたい 集めた個数は日数から分かるので dp[i][j] := i日目にj番目を選ぶ組み合わせ のようにしたくなった しかし、最適解は左から順番に選ぶと…

https://atcoder.jp/contests/agc022/tasks/agc022_c 思考 ・2のべき乗なので、なるべく小さいkを使いたい ・同じkを複数回使う事はない kを50から順に見ていき何かしたい。が、よく分からない とりあえずaiから作れる数を考えてみる ai bi 1 : 0 2 : 0 3 : …

C - Ants on a Circle 解法 蟻なのでぶつかる際にすれ違う事にして、番号を交換すればよさそう 最終的な位置集合は分かり、かつ 1< 2 <3 ...なので、一匹でも答えがわかれば解ける 位置は1< 2 <3で常に一定なので、 交換する番号は自分-1である よって最終的…

B - Splatter Painting 解法 後ろから見れば、頂点が塗られる回数は高々10^5なのでよさそう dp[v][d] := vから周囲d以内が塗られている とし、dp[v][d] からdp[t][d-1],dp[v][d-1]と伝播することで解ける https://atcoder.jp/contests/agc012/submissions/45…

D - Choose Your Characters 都合のため、iはiに対して不利とする 解法 rok[l] := lに対して、選べる最小のr 上が出来れば解ける 例えばi に対して不利なキャラが 2 3 5 6 7の時、 rok[7] = max(rok[7],8 ) rok[6] = max(rok[6],8 ) rok[5] = max(rok[5],8 )…

C - Permutation City 木の方が扱いやすそうなので、全域木に変換して0を根とする dfs(i,親)で以下を繰り返す iと子のうち、他の頂点に選ばれていない物の集合Vを考える Vの要素数が1以下ならreturn 2つ以上あればv[0] -> v[1] ......v[last] -> v[0]の様に(…

No.409 ダイエット - yukicoderすぐに見えて成長を感じた 解法 断食日数がはっきりしないと面倒なのでdp[i] := i日目に食べる際の最適とする こうするとdp[j]から遷移する際に断食日数が定まるためやりやすい これは一見O(n^2)だが、これはconvex hull trick…

Y - Grid 2 解法壁へ行ける事にする。dp[i] := iへの行き方のうち、他の壁を通らないような場合の数とする。ここで、ゴール地点gを壁としてやると、dp[g]が答えである。 遷移方法は、iの左上にある任意の壁jでdp[i] = iへの行き方 - sum(dp[j]からiへ行く方…

W - Intervals dp[i] := iまで見ていて、iが1の時の最大値としたいすると、あるi未満のjで、dp[i] := max(dp[j]) + iが含まれる区間のコスト という風にしたくなるmax(dp[j])はセグ木を使えば管理できる しかし、このままではi,j共に含まれる区間が、重複し…

https://atcoder.jp/contests/arc102/tasks/arc102_cあるiについて考えると合計がiとなるようなペアがp種類存在する この時、ペアの片方は自由に選べ、選ぶ物の数をq種類とする するとiが奇数の時に res += pCq * 2^q * k-2p+q H n-q となる 全てのqについて…