B - Curiosity Has No Limits

Quiz https://codeforces.com/contest/1031/problem/B AC https://codeforces.com/contest/1031/submission/100148060 解法 editorialではbitごとに決まると書いてあるが、値域が狭いので全探索したらACした 先頭2つを全探索し、条件を満たし続ける限りi=2以…

C. Smallest Word

Quiz https://codeforces.com/contest/1043/problem/C AC https://codeforces.com/contest/1043/submission/100145616 解説 aaaaabbbbbの形にできる aの塊ごとに見て、その後端で1度flipすると、そのaの塊が先頭に来る 次のaの塊の直前にあるbで1度flipする…

A. Music

Quiz https://codeforces.com/contest/569/problem/A AC https://codeforces.com/contest/569/submission/100124130 問題理解 音楽をダウンロード(DL)しようとしている。S秒分の曲をDLしたら、Playを開始する DLが完了するまで、何度も曲を聞く 聞いている…

1080C - Masha and two friends ~白黒タイルを塗る。領域の重なり~

Quiz https://codeforces.com/problemset/problem/1080/C AC https://codeforces.com/contest/1080/submission/100064787 感想 解法はeditorialの通り。https://codeforces.com/blog/entry/63436 二次元累積和に似た考え方をすることで指定領域内のblack, wh…

B. Valuable Paper ~Hopcroft–Karp algorithm~ 条件付き2部マッチングでO(E sqrt(V))

Quiz https://codeforces.com/contest/1423/problem/B AC https://codeforces.com/contest/1423/submission/99738013 解説 editorialの通り、使う辺のコストの最大値を上げるほど最大マッチング=Nにしやすい(単調性)ので二分探索する しかし最大流を使っ…

B. Unmerge ~部分和問題 subset sum~

Quiz https://codeforces.com/problemset/problem/1381/B AC https://codeforces.com/contest/1381/submission/99672317 補足 解説はeditorialの通り 部分和が実現できるか?のDPを関数化しておいた // 部分和問題 subset sum // 部分和でtargetを作ることが…

codingame fall-challenge-2020 参加記 ~最後までダイクストラ編~

contest コンテストTOP https://www.codingame.com/contests/fall-challenge-2020 IDE(自分用) https://www.codingame.com/ide/puzzle/fall-challenge-2020 結果 Gold ビームじゃなくてダイクストラで結構いい位置に行けたが限界を感じ、後半の追い込みは…

C2. Binary Table (Hard Version)

Quiz https://codeforces.com/contest/1440/problem/C2 AC https://codeforces.com/contest/1440/submission/99050710 解法 下の2行以外は0になるようにする 最下段2行のみに1がある状態になったら、1を右に寄せていく 右下の2x2領域にのみ1がある状態になる…

C - Knapsack

Quiz https://codeforces.com/contest/1447/problem/C AC https://codeforces.com/contest/1447/submission/99012325 解説 各荷物1つで条件を満たすかチェックする 満たさなかった場合、荷物の重さは floor(W/2)より小さいか、Wより大きいものしかない floor…

B. Toy Blocks

Quiz https://codeforces.com/contest/1452/problem/B AC https://codeforces.com/contest/1452/submission/98991586 解説 コードにコメントを書きました 感想 sum, max, minで求まる。問題位置や解けた人数的にそれくらいの難易度であるのは予想できたがコ…

D. Powerful Ksenia

Quiz https://codeforces.com/contest/1438/problem/D AC なし 解説 editorialは読んだとする このコード、美しい・・・ https://codeforces.com/contest/1438/submission/98381344 from functools import reduce n = int(input()) a = list(map(int, input(…

C. Space Formula

Quiz https://codeforces.com/contest/1046/problem/C AC https://codeforces.com/contest/1046/submission/98531774 感想 通したんだけどモヤモヤ・・・ "It's guaranteed that given astronaut will have unique number of points before the race."って書…

C. Sonya and Robots

Quiz https://codeforces.com/contest/1004/problem/C AC https://codeforces.com/contest/1004/submission/98520055 解説 左のロボットの居場所と右のロボットの居場所の切れ目をすべて見る 左のロボットの領域を1つずつ拡大していく すでに見た数字を左に…

981C - Useful Decomposition

Quiz https://codeforces.com/contest/981/problem/C AC https://codeforces.com/contest/981/submission/98427495 問題理解 読解に苦労したが、画像を見れば一発だろう(下記) 木をパスに分解する。各パスは互いに接している必要がある 解説 これを考える…

D. Divide by three, multiply by two

Quiz https://codeforces.com/problemset/problem/977/D AC https://codeforces.com/contest/977/submission/98420443 解説 各数字aは1度しか出てこない サンプル1を図示するとDAGになっている トポロジカルソートすればよい int main(){ cin.tie(0); ios::s…

C. Valhalla Siege

Quiz https://codeforces.com/problemset/problem/975/C AC https://codeforces.com/contest/975/submission/98419257 問題理解 Lagerthaが矢を放つ Ivar軍には兵士がいて、矢は前の人から刺さる 兵士が全滅した時のみ、全員復活する 解法 各クエリにて、今…

B. String Typing

Quiz https://codeforces.com/problemset/problem/954/B AC https://codeforces.com/contest/954/submission/98365821 感想 N<=100なので雑に実装しても間に合う 1文字タイプするごとに、今コピーした場合の最終コストを求めればいい N<=105の場合はローリン…

B. Our Tanya is Crying Out Loud

Quiz https://codeforces.com/problemset/problem/940/B AC https://codeforces.com/contest/940/submission/98362694 解説 k>1とする 2つ選択肢があるように見えて、大抵は片方しか選べない kで割る場合、何回連続で割るか考えそうになるが、1ステップのみ…

連結判定 bfs

やるだけbfsはコピペで済ませよう 今回の設定では、地図が ##. #.. ... のようにドットが空地、#が壁として、空地が連結かを判定する ll H,W; int dx[4] = {-1, 0, 1, 0}; int dy[4] = { 0, 1, 0, -1}; bool in_range(ll i, ll j){ if(0<=i && i

C. Uncle Bogdan and Country Happiness

Quiz https://codeforces.com/problemset/problem/1388/C AC https://codeforces.com/contest/1388/submission/97891528 感想 分かったつもりでスキップしていたが、実際に解いてみるとハマって何時間もかかった 結局editorialを見てAC 確実に求められる値(…

PAST E - 順列

Quiz https://atcoder.jp/contests/past202004-open/tasks/past202004_e AC https://atcoder.jp/contests/past202004-open/submissions/17899410 解説 制約が緩いのでシミュレーションしてもいいけれど、連結成分のサイズでも求められる #include <atcoder/dsu> using nam</atcoder/dsu>…

D. Extreme Subtraction 単調増加と単調減少に分離

Quiz https://codeforces.com/contest/1443/problem/D AC https://codeforces.com/contest/1443/submission/97668720 解説 配列Vを単調減少なA, 単調増加なBに分離できるかという問題になる editorialのように式変形すれば貪欲に前から決めていける その他 …

1436B - Prime Square

900

Quiz https://codeforces.com/contest/1436/problem/B AC https://codeforces.com/contest/1436/submission/96922880 My editorial it is different from official editorial, so I wrote. My solution is shown in the image below void solve(){ ll N; cin…

B - Putting Bricks in the Wall ~入口と出口なら管理しやすい~

Quiz https://codeforces.com/contest/1421/problem/B AC https://codeforces.com/contest/1421/submission/96783516 解説 左上を00で囲む、右下を11で囲むなどできれば到達不可能にできる 左上を0,1のどちらで囲むか、右下を0,1のどちらで囲むかは初期状態…

C. Link Cut Centroids ~木の重心は木DPするだけ~

Quiz https://codeforces.com/contest/1406/problem/C AC https://codeforces.com/contest/1406/submission/95506541 木の重心を求める関数を使いました記念 // 木の重心(最大2つ) // https://codeforces.com/blog/entry/57593 VI Centroid(const VV &g) {…

codeforces __int128_t __int128 使えます

使った例 https://codeforces.com/contest/1409/submission/95368617 GNU C++17 (64) 2020/03頃に使えるようになった様子

1426C - Increase and Copy ~三分探索の嘘解法でAC~

Quiz https://codeforces.com/contest/1426/problem/C AC https://codeforces.com/contest/1426/submission/94974030 解説 +1する操作を先にするが、何回必要かを三分探索した +1の操作回数をx軸、N以上とするために必要な合計回数をy軸とすると下に凸の関数…

D - Teleporter ~ダブリングで再AC~

Quiz https://atcoder.jp/contests/abc167/tasks/abc167_d AC https://atcoder.jp/contests/abc167/submissions/17244023 その他 コンテスト中は周期を使って解いたが、こういうワープ系はダブリングで捉えるとより一般的 ということで解き直したらかなり簡…

(コスト付き)木の直径

yosupo judgeでAC https://judge.yosupo.jp/submission/25877 直径のパスも求められる // 木の直径(コストあり) struct TreeDiameter{ vector<vector<PII>> G; // (to, cost) ll N; ll start,end; VI path; ll d; VI TO; // 初期化のみ TreeDiameter(ll n){ N=n; G.res</vector<pii>…

マンハッタン距離は45度回転させて考える(図示)X=x-y; Y=x+y

(√2の倍率は無視します) 45度回転させる式は、X=x-y; Y=x+y これで反時計回りに45度回転し、XY座標で2次元累積和を使うと解ける問題があったりする 例:ABC018 C – 菱型カウント https://atcoder.jp/contests/abc018/tasks/abc018_3 図示した