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

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…