Quiz https://atcoder.jp/contests/arc056/tasks/arc056_b Submit https://atcoder.jp/contests/arc056/submissions/4410100 Note 通れる部分が減っていく。i番目の車を入れたらiからのびる辺が消えてグラフが分断されていく union findの逆でグループ分けを…

Quiz https://atcoder.jp/contests/abc025/tasks/abc025_c Submit https://atcoder.jp/contests/abc025/submissions/4408334 Note 片方がスコアを最大にしようと動き、もう片方がスコアを最小にしようと動くとき、ミニマックス法で先読みする Wikipedia参照 …

Quiz https://atcoder.jp/contests/abc016/tasks/abc016_4 板が何枚に切られるかという問題 AC https://atcoder.jp/contests/abc016/submissions/4405573 交差判定関数あり 図示 交差数が分割数に影響する (交差数 / 2) + 1 2次元の点は複素数で扱うと楽 和…

何故書いている 精進記録 他の人の解く助けになれば 主に図での理解 検索に表示されない Blogタイトル＝問題タイトルで書くことが多い コードはコンテストサイトにUPされているのでコピペすることもなかろうということでURL これが良くなさそう Google Searc…

Quiz https://atcoder.jp/contests/abc119/tasks/abc119_c Submit https://atcoder.jp/contests/abc119/submissions/4377522 Note N=8と小さい 伸ばしてから合成と、合成してから伸ばすのは同じ 各竹をA, B, C, D(使わない)に割り当てるのを全パターン試せば…

Quiz https://atcoder.jp/contests/abc119/tasks/abc119_d Submit https://atcoder.jp/contests/abc119/submissions/4374869 Note xの位置から見て、一番近い右にある寺・神社 xの位置から見て、一番近い左にある寺・神社 をそれぞれ求める 右の神社に行って…

Contest https://leetcode.com/contest/weekly-contest-125 Submit Q1 https://leetcode.com/contest/weekly-contest-125/submissions/detail/210152464/ Q2 https://leetcode.com/contest/weekly-contest-125/submissions/detail/210165453/ Q3 Q4 感想 サ…

Quiz https://atcoder.jp/contests/abc003/tasks/abc003_4 Submit https://atcoder.jp/contests/abc003/submissions/4361326 Note editorialの通りに包除原理 サンプルが全部通ればほぼ通る 101点の条件ではもっと小さいテストケースを作るといい 包除原理 …

グローバルに書く const int N_MAX = 100010; ll Per[N_MAX] = {}; // n! ll Per_inv[N_MAX] = {}; //(n!)^-1 ll nCr(ll n, ll r){ if(n

Quiz https://codeforces.com/contest/1131/problem/F Submit https://codeforces.com/contest/1131/submission/50398023 Note 問題文の図の通り、union find木などで結合していく グループ毎にメンバー一覧を持っておく 結合した時、グループAとグループBの…

Quiz https://yukicoder.me/problems/no/793 Submit https://yukicoder.me/submissions/318975 Note 10N (N=1018) ここに高速累乗を使う。log(N) 3で割ったもののmodなのでフェルマーの小定理を使う

Submit Div 2 問題 https://community.topcoder.com/stat?c=round_overview&rd=17400 レーティング レーティング 0の白コーダー Easy, Midを解けたがHardは解けず 結果、0->1152 で緑に。1200を越えると青になるようで、AtCoderの青よりも難易度が低いことが…

Quiz https://atcoder.jp/contests/abc087/tasks/arc090_b Submit https://atcoder.jp/contests/abc087/submissions/4342479 Note 解説YouTubeの通り https://youtu.be/br3ze-KC6WA?t=1852 もう少し詳しく M個のエッジ情報を登録する visited配列 距離配列 …

Quiz https://csacademy.com/contest/fii-code-2019-round-1/task/Sugarel-in-Love/statement/ Submit なし 問題 disjointなパスの和の最大値 サンプル１ 問題の読み間違い バスに乗って長い時間一緒にいたいから、乗り換えはせずにパスは1本だと思い込んで…

Quiz https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_d Submit https://atcoder.jp/contests/nikkei2019-final/submissions/4334442 解法 editorialの通り https://img.atcoder.jp/nikkei2019-final/editorial.pdf 注意点 setから消…

Quiz https://codeforces.com/contest/1118/problem/C Submit https://codeforces.com/contest/1118/submission/50243260 解法 Nが偶数のとき 各値のカウントが4の倍数なら解ける。対称に置くだけ Nが奇数の時 4個以上ある値を4隅に割り当てる 残りから十字(…

Quiz https://codeforces.com/contest/1118/problem/D1 https://codeforces.com/contest/1118/problem/D2 Submit https://codeforces.com/contest/1118/submission/50237247 解法 d日で解けるかを二分探索 カフェイン列は大きい順にソートしておき、各日の早…

Quiz https://atcoder.jp/contests/abc014/tasks/abc014_4 Submit https://atcoder.jp/contests/abc014/submissions/4325911 根が0決め打ちなので注意 解法 どこかをrootにしてdfsでdepthを測っておく LCA (Lowest Common Ancestor)が高速に求まれば、depth…

Quiz https://codeforces.com/contest/1117/problem/C Submit https://codeforces.com/contest/1117/submission/50138888 解法 二分探索 日数を固定(daysとする)したとき、まず流され、そのあと移動する 流された後の位置とゴールのマンハッタン距離 <= days…

Quiz https://codeforces.com/contest/1107/problem/A Submit https://codeforces.com/contest/1107/submission/50076744 Note cfはテストケース全部見せてくれるっぽい コンテストが終了しているからだろう 感想 正しく英語が読めているかどうか、という壁…

Quiz https://atcoder.jp/contests/abc104/tasks/abc104_d Submit https://atcoder.jp/contests/abc104/submissions/4308261 Note この解説が素晴らしい https://betrue12.hateblo.jp/entry/2018/08/05/230358

Quiz https://atcoder.jp/contests/abc113/tasks/abc113_d Submit https://atcoder.jp/contests/abc113/submissions/4307703 線の引き方はフィボナッチで求まる 例えば4本の場合、線の引き方はfib(5) = 5通りある N本の場合、fib(N+1)通り 例えば左に折れる…

Quiz https://atcoder.jp/contests/abc095/tasks/arc096_b Submit https://atcoder.jp/contests/abc095/submissions/4307178 Note 解説AC B側に進んで折り返してAまで行く場合をO(N)で解くコードを書く A側で折り返す場合の方は、データを反転させて対応 合…

Quiz https://atcoder.jp/contests/abc118/tasks/abc118_c Submit https://atcoder.jp/contests/abc118/submissions/4285563 Note できるだけ小さいモンスターを作るゲーム 1番小さいモンスターのサイズで各モンスターのサイズはmodを取って良い 同じサイズ…

使いたいときは、コンパイルオプションが必要 g++ -std=c++11 answer_abc004_4.cpp

アルゴリズム http://www.prefield.com/algorithm/graph/primal_dual.html ポテンシャルについては下記 最小費用流 http://dopal.cs.uec.ac.jp/okamotoy/lect/2013/opt/handout13.pdf 図がステップ毎に丁寧に書かれているので理解できた 書けそうと思える 実…

Quiz https://atcoder.jp/contests/abc054/tasks/abc054_d Submit https://atcoder.jp/contests/abc054/submissions/4261224 Note 3次元DPとはいえ恐れるなかれ テストケース テストケース1, 2は間違ったコードでも通りやすい そこでテストケース1に追記した…

ll dp[41][401][401]; この配列をint main()内で宣言したらローカルでREになった グローバル変数にしたら解決した 40x400x400 = 640万 = 6.4 x 106 これくらいの大きさの配列を宣言するときは気をつけよう 関連問題 https://atcoder.jp/contests/abc054/task…

Quiz https://atcoder.jp/contests/abc110/tasks/abc110_d Submit https://atcoder.jp/contests/abc110/submissions/4246912 解法 editorialや、けんちょんさんの記事と同じ 素因数分解 過去の提出から再利用 因数に1が含まれないように微修正した vector<ll> fa</ll>…

Quiz https://atcoder.jp/contests/rco-contest-2019-qual/tasks/rco_contest_2019_qual_a 雰囲気を知るということで軽く参加 テストケースジェネレータをjavacで生成したりした 星のように点がある場合をイメージして、一番遠くに行く戦略を試してみた 得点…