2020-01-01から1年間の記事一覧
Quiz https://codeforces.com/contest/1005/problem/D AC https://codeforces.com/contest/1005/submission/100175976 解説 各文字をmod3しておく 文字列を後ろから見て、今まで見た数値の部分集合で3の倍数が作れるなら+1して、見た集合を空にする int main…
Quiz https://codeforces.com/contest/1031/problem/B AC https://codeforces.com/contest/1031/submission/100148060 解法 editorialではbitごとに決まると書いてあるが、値域が狭いので全探索したらACした 先頭2つを全探索し、条件を満たし続ける限りi=2以…
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する…
Quiz https://codeforces.com/contest/569/problem/A AC https://codeforces.com/contest/569/submission/100124130 問題理解 音楽をダウンロード（DL）しようとしている。S秒分の曲をDLしたら、Playを開始する DLが完了するまで、何度も曲を聞く 聞いている…
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…
Quiz https://codeforces.com/contest/1423/problem/B AC https://codeforces.com/contest/1423/submission/99738013 解説 editorialの通り、使う辺のコストの最大値を上げるほど最大マッチング＝Nにしやすい（単調性）ので二分探索する しかし最大流を使っ…
Quiz https://codeforces.com/problemset/problem/1381/B AC https://codeforces.com/contest/1381/submission/99672317 補足 解説はeditorialの通り 部分和が実現できるか？のDPを関数化しておいた 計算量注意 O(N2) // 部分和問題 subset sum // 部分和でt…
contest コンテストTOP https://www.codingame.com/contests/fall-challenge-2020 IDE（自分用） https://www.codingame.com/ide/puzzle/fall-challenge-2020 結果 Gold ビームじゃなくてダイクストラで結構いい位置に行けたが限界を感じ、後半の追い込みは…
Quiz https://codeforces.com/contest/1440/problem/C2 AC https://codeforces.com/contest/1440/submission/99050710 解法 下の2行以外は0になるようにする 最下段2行のみに1がある状態になったら、1を右に寄せていく 右下の2x2領域にのみ1がある状態になる…
Quiz https://codeforces.com/contest/1447/problem/C AC https://codeforces.com/contest/1447/submission/99012325 解説 各荷物1つで条件を満たすかチェックする 満たさなかった場合、荷物の重さは floor(W/2)より小さいか、Wより大きいものしかない floor…
Quiz https://codeforces.com/contest/1452/problem/B AC https://codeforces.com/contest/1452/submission/98991586 解説 コードにコメントを書きました 感想 sum, max, minで求まる。問題位置や解けた人数的にそれくらいの難易度であるのは予想できたがコ…
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(…
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."って書…
Quiz https://codeforces.com/contest/1004/problem/C AC https://codeforces.com/contest/1004/submission/98520055 解説 左のロボットの居場所と右のロボットの居場所の切れ目をすべて見る 左のロボットの領域を1つずつ拡大していく すでに見た数字を左に…
Quiz https://codeforces.com/contest/981/problem/C AC https://codeforces.com/contest/981/submission/98427495 問題理解 読解に苦労したが、画像を見れば一発だろう（下記） 木をパスに分解する。各パスは互いに接している必要がある 解説 これを考える…
Quiz https://codeforces.com/problemset/problem/977/D x2か÷3をして作れる列を復元せよ AC https://codeforces.com/contest/977/submission/98420443 解説 制約には書いていないが、操作を考えると各数字aは1度しか出てこないことが分かる サンプル1を図示…
Quiz https://codeforces.com/problemset/problem/975/C AC https://codeforces.com/contest/975/submission/98419257 問題理解 Lagerthaが矢を放つ Ivar軍には兵士がいて、矢は前の人から刺さる 兵士が全滅した時のみ、全員復活する 解法 各クエリにて、今…
Quiz https://codeforces.com/problemset/problem/954/B AC https://codeforces.com/contest/954/submission/98365821 感想 N<=100なので雑に実装しても間に合う 1文字タイプするごとに、今コピーした場合の最終コストを求めればいい N<=105の場合はローリン…
Quiz https://codeforces.com/problemset/problem/940/B AC https://codeforces.com/contest/940/submission/98362694 解説 k>1とする 2つ選択肢があるように見えて、大抵は片方しか選べない kで割る場合、何回連続で割るか考えそうになるが、1ステップのみ…
やるだけ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
Quiz https://codeforces.com/problemset/problem/1388/C AC https://codeforces.com/contest/1388/submission/97891528 感想 分かったつもりでスキップしていたが、実際に解いてみるとハマって何時間もかかった 結局editorialを見てAC 確実に求められる値（…
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>…
Quiz https://codeforces.com/contest/1443/problem/D AC https://codeforces.com/contest/1443/submission/97668720 解説 配列Vを単調減少なA, 単調増加なBに分離できるかという問題になる editorialのように式変形すれば貪欲に前から決めていける その他 …
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…
Quiz https://codeforces.com/contest/1421/problem/B AC https://codeforces.com/contest/1421/submission/96783516 解説 左上を00で囲む、右下を11で囲むなどできれば到達不可能にできる 左上を0,1のどちらで囲むか、右下を0,1のどちらで囲むかは初期状態…
問題説明 重心が1つのみの木を作りたい。辺を1つ削除し、辺を1つ追加して新たな木としてよい時、それは可能。その操作（辺の追加・削除）を構築せよ Quiz https://codeforces.com/contest/1406/problem/C AC https://codeforces.com/contest/1406/submission…
使った例 https://codeforces.com/contest/1409/submission/95368617 GNU C++17 (64) 2020/03頃に使えるようになった様子 verified (1500)D2. Magic Powder - 2 AC https://codeforces.com/contest/670/submission/100988928 私はこうしています using LL = …
Quiz https://codeforces.com/contest/1426/problem/C AC https://codeforces.com/contest/1426/submission/94974030 解説 +1する操作を先にするが、何回必要かを三分探索した +1の操作回数をx軸、N以上とするために必要な合計回数をy軸とすると下に凸の関数…
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>…
