最小点被覆 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で根からの深さと、部分木のサイズを求めておけばいい 「割り…

D. Mysterious Crime

Quiz https://codeforces.com/problemset/problem/1043/D 補足 editorialがよくわからなかったので解説コードを紐解いてみた 1人目の証言をrenumber(番号振り直し)する。permutationだからやってよい あとは各iについて、i, i+1, i+2, ...がどこまで伸ばせ…

C. Colored Rooks

Quiz https://codeforces.com/contest/1068/problem/C 感想 readforces! まず斜めに置くことはひらめいたとする あとはharmonyな色の接続だが、対角に置くと意図せぬ色もharmonyになってしまうケースがある そこでn x nの領域を飛び越えて、外側から接続すれ…

D. Cow and Snacks

Quiz https://codeforces.com/problemset/problem/1209/D AC https://codeforces.com/contest/1209/submission/91176952 解説 連結成分ごとに見たとき、「連結成分内のノード数-1」が幸せになる客の数、逆に言えばそれ以外の客は sad になる その他 「入次数…

A. Marcin and Training Camp ~bitで見た時のsubset~ is_subset

is_subset /* b is subset of a a = 11001010 b = 01001000 => true */ bool is_subset(ll a, ll b){ ll c = (~b | a); if(c==~0LL){ // 11111111 return true; }else{ return false; } } A. Marcin and Training Camp Quiz https://codeforces.com/contest/…

D. Ticket Game

Quiz https://codeforces.com/contest/1215/problem/D AC https://codeforces.com/contest/1215/submission/91168942 解説 editorialと違う解法 左の数字の和==右の数字の和の時は自明とし、以降は数字の和に差があるものとする 左の?が多いとする(違う…

C. Periodic integer number ~コーナーケースは端っこを攻めろ!~

Quiz https://codeforces.com/contest/1219/problem/C AC https://codeforces.com/contest/1219/submission/91093006 解説 ...はeditorialの通りなので書きません 解法は簡単に思いつきますが、コーナーケースがあります。与えられる文字列sの長さをNとして…

C. Platforms Jumping O(N)

Quiz https://codeforces.com/contest/1256/problem/C AC https://codeforces.com/contest/1256/submission/91006703 解法 最大ジャンプを繰り返した場合、その長さの川まで渡れるかは求められる。それが足りないならNO 足りている場合、platformの間隔を詰…

C. Infinite Fence

Quiz https://codeforces.com/contest/1260/problem/C AC https://codeforces.com/contest/1260/submission/91003892 解説 r==gの時はOBEY それ以外のとき、空白を除去するためにgcdで割る r>gとする rとrの間に、gを最大に詰め込んだ場合に何個入るかを考え…

B. Infinite Prefixes

Quiz https://codeforces.com/contest/1295/problem/B AC https://codeforces.com/contest/1295/submission/90787038 解説 editrorialとは別の解法 波船が上下しながらxという上にあるバーに迫っていくイメージだが、逆にxのバーが下に下がってくると考える …

A. Recommendations

Quiz https://codeforces.com/problemset/problem/1310/A AC https://codeforces.com/contest/1310/submission/90780105 解説 editorialではmultisetを使っていたが、私はpriority_queueを使った サンプル1を見れば分かるように、Aの小さい方から見ていって…

C. Annoying Present

Quiz https://codeforces.com/contest/1009/problem/C AC https://codeforces.com/contest/1009/submission/90329549 解説 xは位置に関係なく均一に足されるのでまとめて考えられる dが正の時は i をはじっこに、 dが負の時は i を真ん中に置けばいい その他…

B. Diagonal Walking v.2

Quiz https://codeforces.com/contest/1036/problem/B AC https://codeforces.com/contest/1036/submission/89997834 解説 できるだけ斜め移動しようとしたとき、X回目にいれる座標には制限がある。逆にその座標なら全て斜めで行ける 目的地までの大抵の移動…

I. Palindrome Pairs

Quiz https://codeforces.com/problemset/problem/1045/I AC https://codeforces.com/contest/1045/submission/89811807 解説 たとえばaabとbは同一視できる 各文字の偶奇のみに意味があり、各文字列は26文字をフラグとした整数値として表せる 回文を作れる…

B. Divide Candies

Quiz https://codeforces.com/problemset/problem/1056/B AC https://codeforces.com/contest/1056/submission/89797233 解説 mが小さく、m x mの範囲なら全探索できる。その中で条件を満たす座標を見つけた時、それに対応する座標がm x mより向こうの範囲に…

D. Decorate Apple Tree

Quiz https://codeforces.com/contest/1056/problem/D 解説 色を塗るのは葉だけ 辺の与え方が見慣れない形式 解法は、各頂点以下の葉の個数を調べ、それをソートする sample 2

D1. Optimal Subsequences (Easy Version)

Quiz https://codeforces.com/problemset/problem/1227/D1 AC https://codeforces.com/contest/1227/submission/89546017 解説 降順ソートして上位k個を取るのは分かる その中の最小値をxとして、xを何個取ればいいかも分かる xより大きい値は全部取る あと…

long doubleで小数を読み込むならEPS足しとけ

具体的にはこの問題 A - Integer Product https://atcoder.jp/contests/agc047/tasks/agc047_a 本番では文字列で読み込んで1e9倍することで誤差を完全に消してACしたが、EPSで誤差を解消できればもっと速く解けた 具体的にはここ using ld = long double; #d…