中国剰余定理 (CRT) 使いました記念

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

python3で整数どうしの割り算に注意。片方が負のときの挙動がC++と違う

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

点Pから円に引いた2本の接線が求まるが、その2つの接点を求めよ (polar) "Tangent to a Circle" AOJ

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>…

点と線分の距離 ~long double VER~

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 解説 点と直線の距離ではないので注意 点を線分に射影した後、射影された点が線分内にいるかもチェックした そ…

2つの線分の交点の位置 ~ax + by = cと逆行列~

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で表す 交差するなら逆行列が存在するので求ま…

スライド最小値 Sliding Window Minimum Algorithm

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…

AOJ 2251 - Merry Christmas ~DAG上の最小パス被覆 minimum path cover~

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に遷移できるなら辺をはる。これはDAGになる そのDAG上の最小パス…

D: mod rally ~ACL sccを用いて強連結成分分解~

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して最大距離を求める …

A - Reachable Towns

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

E - Sequence Sum ~サイクル検出(位置と長さ)~

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

B: P進XOR

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 を再現したようなコードになっ…

ACPC2020Day1, Day2, Day3

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…

Range Update Query (by ACL) 範囲更新

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

F - Convolution 畳み込み

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

C - Floor Sum ~直線以下の格子点の数え上げ~

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

最小点被覆 minimum vertex cover 2部グラフなら最大マッチングで解ける

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 解説 ワーシャルフロイドで最短距離を求め、アルファベット…

HUPC2020Day1, Day2, Day3

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…

D. Maximum Distance

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

WUPC2020

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

D. Petya and Array ~座標圧縮してBITで数える~

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

L. Lexicography

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

B. Beingawesomeism

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

オイラーのトーシェント関数 (φ, ファイ, phi)

verified Same GCDs https://codeforces.com/contest/1295/problem/D AC https://codeforces.com/contest/1295/submission/92113264 AC(AOJ) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4869035#1 // 借り物 // https://ei1333.github.io/luzhil…

D. Shortest and Longest LIS

Quiz https://codeforces.com/problemset/problem/1304/D 解説 editorialの補足として、イメージ画像のみ置いておきます increasing or decreasingなブロックで分割して、数字を割り振る

難易度は低いけれど「やるだけ」ではない興味深い問題集

On setting D2A and D2B problems - Codeforces https://codeforces.com/blog/entry/75163 ここで「Div2-A,Bはやるだけ問題を置いておけばいい」「違う、興味深い(思考が必要な)問題も置けるはずだ」という議論がある その中で良問として20問ほど挙げられ…

Bad Ugly Numbers

Quiz https://codeforces.com/contest/1326/problem/A AC https://codeforces.com/contest/1326/submission/91974618 解説 23333333333333 その他 AAAAABの形は考えたが、ABBBBBB の形は考えなかった・・・ その両方を考えつつ、A,Bに2~9を機械的に入れてチ…

E. Count The Blocks ~ダブルカウントにより本数を数える~

Quiz https://codeforces.com/contest/1327/problem/E AC https://codeforces.com/contest/1327/submission/91918902 解説 editorialの通り、長さlenが何本あるかを数えるときに、はじっこと中間に場合分けして数える ここで私がひっかかったのは「ダブルカ…

D. Maximum Distributed Tree 木DP, tree DP

Quiz https://codeforces.com/contest/1401/problem/D\ AC https://codeforces.com/contest/1401/submission/91696004 解法 辺の両端のノード数の積が大きい辺に、大きい値を割り振るといい 木DPで根からの深さと、部分木のサイズを求めておけばいい 「割り…