Quiz https://yukicoder.me/problems/no/314 Submit https://yukicoder.me/submissions/330500 他の人の解法 dp[i][j] : i番目まで見たとき、ケンの数が j である場合の数 解法 私は、直前2つの状態を見れば遷移が決まることから、 dp[i][j][k] i 番目まで見…

Quiz https://yukicoder.me/problems/no/3 Submit https://yukicoder.me/submissions/330413 解法 ある地点からの移動先は(2箇所以下に)固定されている よって、ある地点に戻って来たら、それは最短距離ではない 同じ地点を訪れないようにしながら最短距離を…

Quiz https://yukicoder.me/problems/no/4 Submit https://yukicoder.me/submissions/330176 解法 天秤の両方を気にするのは大変 重さの合計 / 2 を片側で作れるかで判定すればいい 各重りを使う・使わないで分岐したらO(2100)となってしまう dp[i][j] : i番…

const int N_MAX = 10010; bool is_prime[N_MAX]; // エラトステネスのふるい void Eratosthenes(){ FOR(i, 0, N_MAX){ is_prime[i] = true; } is_prime[0] = false; is_prime[1] = false; FOR(i, 2, N_MAX){ if(is_prime[i]==1){ int p = i; int step_p = p…

O(√N) Ver // 素因数分解 // その素因数が何個あるかのmapを返す map<ll, ll> factorize(ll n){ map<ll, ll> mp; ll sq = sqrt(n); FOR(i, 2, sq+1){ while(n%i==0){ mp[i]++; n/=i; } } // 残り if(n!=1){ mp[n]++; } return mp; } // 約数の種類数 // 6 => 1, 2, 3, 6なの</ll,></ll,>…

Quiz https://yukicoder.me/problems/no/786 Submit https://yukicoder.me/submissions/329556 解法 dp[i] : i段登るときのパターン数とする dp[i]は、 dp[i-2]から2段UP dp[i-1]から1段UP という遷移から来ることができるので、 dp[i] = dp[i-2] + dp[i-1] …

Quiz https://atcoder.jp/contests/code-thanks-festival-2017-open/tasks/code_thanks_festival_2017_e Submit https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/4723793 解法 1回のクエリで5袋の審議判定をする それぞれ1, 10, 10…

Quiz https://atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_e Submit https://atcoder.jp/contests/code-thanks-festival-2018-open/submissions/4722141 解法 dp[i][j] 整数 i まで見て、iがj個余る場合の数 例 dp…

Quiz https://yukicoder.me/problems/no/806 Submit https://yukicoder.me/submissions/328743 解法 公式解説の通り、Σmax(Deg(i)-2, 0) ポイント グラフを次数で見る 最終形の性質を観察する そして現状と比較して、その差が、すべき操作

Quiz https://atcoder.jp/contests/agc032/tasks/agc032_b Submit https://atcoder.jp/contests/agc032/submissions/4705411 発想 最初は上の図のように「どう線を引くか？」考えた しかしSが不明なので手がかりがない 下の図のように一度すべての辺を張って…

Quiz https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e01/00000000000698d6 Google Kick Start? GCJほどではなくAtCoder ABCのような気軽に参加できるコンペティションのようだ 月イチで予定されている 最初の問題 "Training" を…

Quiz https://atcoder.jp/contests/abc122/tasks/abc122_d Submit (コンテスト後に解説放送を見てからAC) https://atcoder.jp/contests/abc122/submissions/4704750 解法 解説放送とeditorialで十分なので省略 コンテスト中 DP感 直前の3文字だけを見ればい…

Quiz https://atcoder.jp/contests/agc032/tasks/agc032_a Submit https://atcoder.jp/contests/agc032/submissions/4676797 解法 テストケース３を見ると、最終状態から過去に1手づつ遡るのがよさそう 最後に行える操作は、j番目にjを挿入 A[j] == j の箇所…

Quiz https://yukicoder.me/problems/no/790 AC https://yukicoder.me/submissions/328008 概要 対応の取れた括弧は何パターンあるか ()()() ((())) など 解法 各位置にどちらの括弧を置くか全パターン生成してからチェックする またはカタラン数 青チャート…

Quiz https://atcoder.jp/contests/bitflyer2018-qual/tasks/bitflyer2018_qual_c Submit https://atcoder.jp/contests/bitflyer2018-qual/submissions/4634379 Note 解法はアルメリアさんのが詳しい https://betrue12.hateblo.jp/entry/2018/06/03/131350 …

Quiz https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_d Submit https://atcoder.jp/contests/mujin-pc-2018/submissions/4629326 解法 (x, y)をノードとして考えて、高々1000x1000個のノードからなるグラフを考える 変換後、(x0, y0) -> (x…

Quiz https://atcoder.jp/contests/dwacon5th-final-open/tasks/dwacon5th_final_a Submit https://atcoder.jp/contests/dwacon5th-final-open/submissions/4625049 Kが奇数の場合 最後の一手を打てる太郎有利 始点の隣にBがある→太郎勝ち 始点の隣にRしかな…

Quiz https://yukicoder.me/problems/no/800 Submit https://yukicoder.me/submissions/324836 Note 4変数で半分を全探索 これは蟻本「おみくじ」で見たやつだ！ x, yは全探索, z, wから作れるパターンは事前に作っておく 二分探索 解いてみる https://yukic…

Quiz https://atcoder.jp/contests/agc005/tasks/agc005_b Submit https://atcoder.jp/contests/agc005/submissions/4611400 Note 解説放送の通り「値aを最小値とする区間をいくつ作れるか」と捉え直す ここの解説も詳しい https://misteer.hatenablog.com/e…

Quiz https://atcoder.jp/contests/abc076/tasks/abc076_c Submit https://atcoder.jp/contests/abc076/submissions/4567256 解法 s上をtを滑らせていき、tが嵌まるところでtをsにコピーする 残った?はaとする 落とし穴 こんなテストケースを考えてみよう ??…

Quiz https://atcoder.jp/contests/nikkei2019-ex/tasks/nikkei2019ex_e Submit https://atcoder.jp/contests/nikkei2019-ex/submissions/4565168 解法・逆関数 学び サンプルテストケースの値が解法の拠り所となることがある その他 このページ、リンクと画…

Quiz https://atcoder.jp/contests/wupc2019/tasks/wupc2019_b Submit https://atcoder.jp/contests/wupc2019/submissions/4549977 解法 まず明らかな解をつぶす 最初から全部0ならクリア 5が存在しないなら無理 後は5を1つ残して他全部を連結して変換する …

Quiz https://atcoder.jp/contests/abc121/tasks/abc121_d AC https://atcoder.jp/contests/abc121/submissions/4532962 解説ブログ アルメリアさん https://betrue12.hateblo.jp/entry/2019/03/09/224330 けんちょんさん http://drken1215.hatenablog.com/e…

Quiz https://atcoder.jp/contests/cf16-final-open/tasks/codefestival_2016_final_b Submit https://atcoder.jp/contests/cf16-final-open/submissions/4513717 Note 難しい問題ではないけれど、editorialに二分探索が書かれていないのと、解説記事Blogも…

Quiz https://codeforces.com/contest/1138/problem/B Submit https://codeforces.com/contest/1138/submission/51062002 英語 最初は問題の意図がよく分からなかった 前半にピエロをX人 後半にアクロバットをX人 にする必要がある。他の人は別のサポート役…

Quiz https://codeforces.com/contest/1133/problem/D Submit https://codeforces.com/contest/1133/submission/50980508 Note b/aが一致するものの個数の最大値が答え a==0は別対応する 落とし穴 コンテスト中、test 37でWA doubleを使っていたが精度に疑い…

Quiz https://atcoder.jp/contests/colopl2018-final-open/tasks/colopl2018_final_c Submit https://atcoder.jp/contests/colopl2018-final-open/submissions/4493568 ステップ１ O(N2) まずはO(N2)でいいから解いてみよう その場合の提出はこちら https://…

Quiz https://atcoder.jp/contests/agc026/tasks/agc026_b Submit https://atcoder.jp/contests/agc026/submissions/4482224 基礎 A<BだとNo D<BだとNo よって、以降はA>=B, B>=D 分析 テストケース1の最初のを見てみると、6になった後にNo これは、CとBの間であり、この区間に入ると補充できず</bだとno>…

Quiz https://codeforces.com/contest/1132/problem/C Submit https://codeforces.com/contest/1132/submission/50862056 解法 除去する2人を全パターン試すとO(N3)となってしまう 除去する1人を固定する 残りq-1人で塗る。各箇所が何回塗られたかをカウント…

Quiz https://atcoder.jp/contests/agc028/tasks/agc028_b Nが小さい場合 解説放送の通り期待値を考える。最初はdoubleを使って確率を定義通りに求めてみる サンプルテストケースは全て通る。提出すると当然TLE https://atcoder.jp/contests/agc028/submissi…