codeforces

E. Product Oriented Recurrence

Quiz https://codeforces.com/contest/1182/problem/E Note Editorial https://codeforces.com/blog/entry/67614 天才かよ!?と思った点 cxを分解(分配)することでcx fxの形にできる 三項の積になるが、g(x, p)を導入して三項の和にする するとトリボナッ…

E. Cover it!

Quiz https://codeforces.com/contest/1176/problem/E ACコード https://codeforces.com/contest/1176/submission/55399046 解法 グラフを2色に塗る(例えば白と黒とする) 現在見ているノードを白で塗ったなら、隣はできるだけ黒で塗るようにする 塗り終わ…

D. Almost All Divisors

Quiz https://codeforces.com/contest/1165/problem/D Submission https://codeforces.com/contest/1165/submission/54147350 解法 Codeforces Round #560 (Div. 3) お疲れ様でしたA:下x桁を見る y桁目は1 それ以外は0にするB:ソートして昇順に見る 次が使え…

B. Expansion coefficient of the array

Quiz https://codeforces.com/contest/1159/problem/B Submission https://codeforces.com/contest/1159/submission/54048500 実験 サンプル3を見る |i-j| = 3のとき、minは717 k x 3 <= 717 k <= 239 これは答えと一致する 解法 |i-j|を幅と呼ぶことにする …

1163B2 - Cat Party (Hard Edition)

Quiz https://codeforces.com/contest/1163/problem/B2 Submit https://codeforces.com/contest/1163/submission/54007477 問題設定 配列Aの前からx個を見て、その中の1つだけを除外して、他の値の頻度が同じなら、そのxはOK [2,2,1,1,5,4,4]なら5を除外すれ…

C2. Power Transmission (Hard Edition)

Quiz https://codeforces.com/contest/1163/problem/C2 Submit https://codeforces.com/contest/1163/submission/54005559 解法 2点から直線が求まるので、係数a, b, cで表現する この時、係数を定数倍すると一致するものに注意する (a, b, c) = (1, 2, 3), …

E. Thanos Nim

Quiz https://codeforces.com/contest/1162/problem/E Submission https://codeforces.com/contest/1162/submission/53797164 解法 まず、1つでも空にしてしまうと負けである 次のターンに相手がN/2個を空にしてきて、自分はN/2個取れないので負ける 1, 1, 1…

C. Hide and Seek

Quiz https://codeforces.com/contest/1162/problem/C Submission https://codeforces.com/contest/1162/submission/53758184 考察 値 i がguess値と同じ時、1度だけ(i-1, i+1に)「分裂」できるとする すでに分裂済みで、またguess値と当たった時「捕まる」…

F. Graph Without Long Directed Paths

Quiz https://codeforces.com/contest/1144/problem/F 内容 無向グラフが与えられる それを有向グラフにし、各パスの長さを2より小さくせよ できない場合は-1を返す Submit https://codeforces.com/contest/1144/submission/52118977 観察 自分に矢印が向い…

B. Circus (1138B)

Quiz https://codeforces.com/contest/1138/problem/B Submit https://codeforces.com/contest/1138/submission/51062002 英語 最初は問題の意図がよく分からなかった 前半にピエロをX人 後半にアクロバットをX人 にする必要がある。他の人は別のサポート役…

D. Zero Quantity Maximization 〜doubleの精度〜

Quiz https://codeforces.com/contest/1133/problem/D Submit https://codeforces.com/contest/1133/submission/50980508 Note b/aが一致するものの個数の最大値が答え a==0は別対応する 落とし穴 コンテスト中、test 37でWA doubleを使っていたが精度に疑い…

C. Painting the Fence

Quiz https://codeforces.com/contest/1132/problem/C Submit https://codeforces.com/contest/1132/submission/50862056 解法 除去する2人を全パターン試すとO(N3)となってしまう 除去する1人を固定する 残りq-1人で塗る。各箇所が何回塗られたかをカウント…

C. Connect (Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2))

Quiz https://codeforces.com/contest/1130/problem/C Submit https://codeforces.com/contest/1130/submission/50620759 解法 高々1つのみ橋を作れる 始点から幅優先で歩ける領域を確認 終点からも同様 始点領域の全点と、終点領域の全点でトンネルを掘って…

B - Two Cakes (Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2))

Quiz https://codeforces.com/contest/1130/problem/B Submit https://codeforces.com/contest/1130/submission/50619986 反省点 Div 2で多くの人が解けているなら貪欲を疑えばよかった 解法 https://twitter.com/torus711/status/1099724979476676608 B: 2 …

F - Asya And Kittens

Quiz https://codeforces.com/contest/1131/problem/F Submit https://codeforces.com/contest/1131/submission/50398023 Note 問題文の図の通り、union find木などで結合していく グループ毎にメンバー一覧を持っておく 結合した時、グループAとグループBの…

C. Palindromic Matrix

Quiz https://codeforces.com/contest/1118/problem/C Submit https://codeforces.com/contest/1118/submission/50243260 解法 Nが偶数のとき 各値のカウントが4の倍数なら解ける。対称に置くだけ Nが奇数の時 4個以上ある値を4隅に割り当てる 残りから十字(…

Coffee and Coursework D1, D2 ☕

Quiz https://codeforces.com/contest/1118/problem/D1 https://codeforces.com/contest/1118/problem/D2 Submit https://codeforces.com/contest/1118/submission/50237247 解法 d日で解けるかを二分探索 カフェイン列は大きい順にソートしておき、各日の早…

C. Magic Ship (Educational Codeforces Round 60)

Quiz https://codeforces.com/contest/1117/problem/C Submit https://codeforces.com/contest/1117/submission/50138888 解法 二分探索 日数を固定(daysとする)したとき、まず流され、そのあと移動する 流された後の位置とゴールのマンハッタン距離 <= days…

2年ぶりくらいにcodeforcesに練習でトライ。AC

Quiz https://codeforces.com/contest/1107/problem/A Submit https://codeforces.com/contest/1107/submission/50076744 Note cfはテストケース全部見せてくれるっぽい コンテストが終了しているからだろう 感想 正しく英語が読めているかどうか、という壁…