Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_B AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4878657#1 解法 オイラー閉路にしたい（頂点の次数が全て偶数） これの「中国人郵便配達問題」を参考にした https://www.…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4878456#1 解説 bit DP chokudai https://www.slideshare.net/chokudai/wap-atcoder4 その他 最初は再帰関数＆メモ化で書…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_G&lang=ja AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4877011#1 解説 tsutajさんのBlogを読んだ 各品物を1, 2, 4, 8個... に分解して、採用・非採用で分岐していけばm…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_F AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4876929#1 解説 蟻本にある 普通のナップサックはO(NW)でdpテーブルを「個数」「容量」で持つが、今回はWが大きいので別…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_4_B&lang=ja AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4875613#1 解法 半分全列挙 N=40なので20, 20に分割すればそれぞれの列挙は220=106程度 片側を全列挙、片側を二…

Quiz Bipartite Matching http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4875362#1 解法 2部マッチングは最大フローで解ける その他 最大フローにはatcoder libraryを用いた …

Quiz https://atcoder.jp/contests/acl1/tasks/acl1_b AC https://atcoder.jp/contests/acl1/submissions/17010040 解説ではなく、自分用の記録 drkenさんライブラリにより、「aで割ってb, cで割ってdになるようなxは？」という質問に答えられるようになった…

>>> -1/3 -0.3333333333333333 >>> -1//3 -1 >>> 1//3 0 スラッシュ1つだと小数点になることがある。これは基本 スラッシュ2つだと整数の割り算で答えも整数になるが、-1//3が-1になっており、これはC++だと0が返ってくる。挙動の違いに注意 除算値を超えな…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_F AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4868997#1 解説 画像の通り せっかく複素数で点(x,y)を表しているのだから、複素数の回転(polar)のお世話になった typede…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_B&lang=ja AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4868983#1 解説 隣り合った2辺についてベクトルを考えて外積が負ならダメ typedef complex<ld> C; // 外積 ld cross(</ld>…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_A AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4868979#1 解説 https://imagingsolution.net/math/calc_n_point_area/ typedef complex<ld> C; // 外積 ld cross(C a, C b){</ld>…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_D AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4868959#1 解説 点と直線の距離ではないので注意 点を線分に射影した後、射影された点が線分内にいるかもチェックした そ…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_C AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4868625#1 解説 交差することは保証されている 線分を直線の式 ax + by = cで表す 交差するなら逆行列が存在するので求ま…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4867025#1 解説 蟻本p301にある 最初はmultisetを使ってO(NlogN)で解いたが、スライド最小値を使うとO(N)となる (N=10000…

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2251 できるだけ少ないサンタでプレゼントを配る問題 AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4866924#1 解説 L個の条件について、条件iを実行後、条件jに遷移できるなら…

Quiz https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2020Day3/problems/D AC https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2020Day3/4862555 解説 強連結成分分解する 始点の強連結グループからトポロジカル順にDPして最大距離を求める …

Quiz https://atcoder.jp/contests/acl1/tasks/acl1_a AC https://atcoder.jp/contests/acl1/submissions/16925269 解説 (x,y)の昇順にソートする 順に見ていって、必要ならunion findでmergeする 愚直にやるとTLEするが、連結成分ごとにyの最小値を持ってお…

Quiz https://atcoder.jp/contests/abc179/tasks/abc179_e AC https://atcoder.jp/contests/abc179/submissions/16895230 解説 Mが小さいので十分な長さの数列を作ればサイクルに入る Nが大きいが、サイクル分はまとめて処理できるのでO(M)となる ライブラリ…

Quiz https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2020Day1/problems/B AC https://onlinejudge.u-aizu.ac.jp/services/review.html#ACPC2020Day1/4854845 解説 editorial https://hackmd.io/@qLethon/rk2qAIrQD を再現したようなコードになっ…

Day 1 (農工大Set) contest https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2020Day1/info editorial https://hackmd.io/@olphe/HyCg84MSw Day2 (Aizu Set) contest https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2020Day2 editorial htt…

AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4852717 区間加算ではなく、区間更新 範囲取得 ACLを使用。モノイド分からないので https://atcoder.github.io/ac-library/document_ja/lazysegtree.html こちらの問題Kを少し書き換えた（係数０）

Quiz https://atcoder.jp/contests/practice2/tasks/practice2_f Document https://atcoder.github.io/ac-library/document_ja/convolution.html

Quiz https://atcoder.jp/contests/practice2/tasks/practice2_c Document https://atcoder.github.io/ac-library/document_ja/math.html 図示のみです

Quiz E: えびちゃんを捕獲せよ https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2020Day1/problems/E AC https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2020Day1/4841280 解説 ワーシャルフロイドで最短距離を求め、アルファベット…

Day1 (Hokkaido Set) https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2020Day1/info editorial https://drive.google.com/drive/folders/169f9B1J33Z1HPFUw-2DizK3bYyhyAOzF 結果 A,B,Cの3完 復習 Eまでupsolveしましょう Day2 (Aizu Set) contes…

Quiz https://codeforces.com/problemset/problem/1081/D AC https://codeforces.com/contest/1081/submission/92692968 問題理解 最初、max, min, cost, distanceで混乱した costについては「経路上の1番高いコストの切符を買えば、他は無料」と考える spec…

問題集 https://onlinejudge.u-aizu.ac.jp/beta/room.html#WUPC2020/info 解説 https://drive.google.com/drive/folders/16n_1q3evzq2sUJtAdjBT7OnxNW-UpQx4 その他 解いておきたい

Quiz https://codeforces.com/contest/1042/problem/D AC https://codeforces.com/contest/1042/submission/92543146 解法 editorialの通り、式変形して、leftを固定して条件を満たすrightを数える BITを用いて数え上げるために座標圧縮を使う（累積和を座標…

Quiz https://codeforces.com/problemset/problem/1267/L AC https://codeforces.com/contest/1267/submission/92214492 問題理解 部分文字列で切り取るわけではなく、与えられる文字列sの文字を好きな順番で使っていいことに注意 なのですべての文字列は辞…

Quiz https://codeforces.com/contest/1281/problem/D AC https://codeforces.com/contest/1280/submission/92201582 解説 editorialの通り、ひたすら場合分け。考察難易度は低い 学び より小さい答えになるものをコードの前方に書く 長くなりがちだし、提出…