https://atcoder.jp/contests/past201912-open/tasks/past201912_j 前提知識 ダイクストラ 解説 https://atcoder.jp/contests/past201912-open/submissions/9257724 難しい問題。 左下を点X, 右下を点Y, 右上を点Zとしておこう。 簡単にX->Yの最短距離+Y->Z…

https://atcoder.jp/contests/past201912-open/tasks/past201912_i 前提知識 bitDP 解説 https://atcoder.jp/contests/past201912-open/submissions/9257465 bitDPを知らないと解くのは難しい。 もしわからない場合は、bitdpでググって概要を理解してきて欲…

https://atcoder.jp/contests/past201912-open/tasks/past201912_h 解説 https://atcoder.jp/contests/past201912-open/submissions/9257326 さて、色々な操作があるが、愚直に操作していくと、O(QN)となって間に合わない。 セット販売と全種類販売について…

https://atcoder.jp/contests/past201912-open/tasks/past201912_g 解説 https://atcoder.jp/contests/past201912-open/submissions/9253193 競技プログラミング的なやりかたで解決する。 3つ以下のグループに分けるので、全てのやり方を試してもO(3N)である…

https://atcoder.jp/contests/past201912-open/tasks/past201912_f 解説 https://atcoder.jp/contests/past201912-open/submissions/9253007 単語は大文字2つで挟まれているので、大文字が2つ現れた時点で文字列を分裂していく。 単語分割が問題の最も難しい…

https://atcoder.jp/contests/past201912-open/tasks/past201912_e 解説 https://atcoder.jp/contests/past201912-open/submissions/9252782 実装が厳しくなってくる。 N≦100なので、計算量は雑にやっても問題ない。 follow[i][j] := iがjをフォローしている…

https://atcoder.jp/contests/past201912-open/tasks/past201912_d 解説 https://atcoder.jp/contests/past201912-open/submissions/9252399 サンプル1の説明を見ると、個数が重要そうである。 書き換えが発生していなかった場合は、全て1個であるパターンで…

https://atcoder.jp/contests/past201912-open/tasks/past201912_c 解説 https://atcoder.jp/contests/past201912-open/submissions/9252314 A～Fを降順ソートして3番目を答えればよい。 ソートするために配列に入れるので、入力を受け付けるときもA,B,...と…

https://atcoder.jp/contests/past201912-open/tasks/past201912_b 解説 https://atcoder.jp/contests/past201912-open/submissions/9252279 隣り合う2要素について、実装をしていく問題。 実装を頑張る問題であり、特に注意点も無いが、vectorのsizeメソッ…

https://atcoder.jp/contests/past201912-open/tasks/past201912_a 解説 https://atcoder.jp/contests/past201912-open/submissions/9252220 入力はエラーとなる場合があるので、整数ではなく、文字列で読み込もう。 IntParse的なやつを使って、例外が出たら…

https://codeforces.com/contest/1270/problem/E 解説 https://codeforces.com/contest/1270/submission/67941885 順位表を見ると、みんな爆速で通しているので、なにか特殊なルールで分けるのだろうというのは分かる。 ヤバい状況を考えるというのが抜けて…

https://codeforces.com/contest/1270/problem/D 解説 https://codeforces.com/contest/1270/submission/67932061 リアクティブといえば二分探索であるが、二分探索が適用できそうな感じは無い。 制約も二分探索を示唆していないので、なにか別の方針で行く…

https://codeforces.com/contest/1270/problem/C 解説 https://codeforces.com/contest/1270/submission/67931185 難しい問題に見える。 和は別に大丈夫だが、xor和を2倍するという操作はいかにもヤバそうに見える。 加えて問題の方にも操作は最小化する必要…

https://codeforces.com/contest/1270/problem/B 解説 https://codeforces.com/contest/1270/submission/67930787 条件を満たすものがあるならば、隣り合う2つで満たすものがある。 上手く説明するのが難しいが、条件が満たされるのは、123...のような連続に…

https://codeforces.com/contest/1270/problem/A 解説 https://codeforces.com/contest/1270/submission/67930164 このゲームは最大のカードを持っている方が勝つ。 これは、最大のカードを持っている方が、最大のカードを出し続けることで連勝できるためで…

https://codeforces.com/contest/1283/problem/E 解説 https://codeforces.com/contest/1283/submission/67851492 最小と最大別々に考えよう。 DPでうまいことやる？ 最小のときは、同じ値は特に考える必要はないので、1つにまとめておく。 これで「dp[i] :=…

https://codeforces.com/contest/1283/problem/D 解説 https://codeforces.com/contest/1283/submission/67849985 人を適切に配置する問題であるが、最適解を考えると、木の周りに順番に人を配置していくのがいいだろう。 木を始点にしてBFSをしていくのがい…

https://atcoder.jp/contests/agc041/tasks/agc041_e 前提知識 bitset高速化 解説 https://atcoder.jp/contests/agc041/submissions/9195266 2つの問題が入っているが、全く別のアプローチで解く。 T=1では、bitset高速化で解く。 dp[i][j] := 平衡器iから平…

https://atcoder.jp/contests/agc041/tasks/agc041_c 関連 構築 解説 https://atcoder.jp/contests/agc041/submissions/9194564 DPとかできないか色々考える。 何も出てこない。 これは、あれか、なんか性質を仮定して解くやつか。 クオリティはそんなに大き…

https://atcoder.jp/contests/agc041/tasks/agc041_b 前提知識 二分探索 解説 https://atcoder.jp/contests/agc041/submissions/9194374 Aをソートしておくと、実は採用されるかどうかは単調性を持つ。 A[i]が採用されるのであれば、A[i+1]も採用されること…

https://atcoder.jp/contests/agc041/tasks/agc041_a 解説 https://atcoder.jp/contests/agc041/submissions/9192722 まず、2人の友達は同時に動くため、互いに近づいて行っても、交わることができる場合とできない場合がある。 B-Aが偶数なら交わることがで…

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_e 前提知識 二次元累積和 BFS 解説 https://atcoder.jp/contests/pakencamp-2019-day3/submissions/9144974 クエリ問題では、まず1クエリだとどう解くかを考えるのが定石。 操作…

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_d 解説 https://atcoder.jp/contests/pakencamp-2019-day3/submissions/9144334 ここから競技プログラミングになれていないと、満点解答を狙うには難しいかもしれない。 さて、…

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c 解説 https://atcoder.jp/contests/pakencamp-2019-day3/submissions/9144292 難しい問題に直面したときは、まずは全探索ができないか考えてみよう。 何を全探索するかである…

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_b 解説 https://atcoder.jp/contests/pakencamp-2019-day3/submissions/9144087 白の人数と黒の人数を数えて多い方が答えになる。 C++なら==で比較すれば判定できる。 int N; //…

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_a 解説 https://atcoder.jp/contests/pakencamp-2019-day3/submissions/9144056 よーくみるとB-A+1日が答え。 int A, B; //--------------------------------------------------…

https://atcoder.jp/contests/abc148/tasks/abc148_f 解説 https://atcoder.jp/contests/abc148/submissions/9103846 色々考えることができそう。 以下解法は全探索しているが、色々なことを要求しているので、木へのライブラリを余り持ってない場合は、 ち…

https://atcoder.jp/contests/abc148/tasks/abc148_e 解説 https://atcoder.jp/contests/abc148/submissions/9103493 大学受験を済ませている人は、この問題を見たらピンと来るかもしれない。 ある数の末尾に続く0の個数はある数を素因数分解したときのmin(2…

https://atcoder.jp/contests/abc148/tasks/abc148_d 解説 https://atcoder.jp/contests/abc148/submissions/9103243 400点問題にしては、なかなか難しそうな問題に見える。 何か特殊な操作をするのだろうか。 壊すレンガを最小化するのではなく、残すレンガ…

https://atcoder.jp/contests/abc148/tasks/abc148_c 前提知識 最小公倍数の効率的な求め方 解説 https://atcoder.jp/contests/abc148/submissions/9103143 今回の問題はAとBの最小公倍数が答えとなる。 ライブラリとして、最小公倍数を高速に求めるものをも…