https://atcoder.jp/contests/abc205/tasks/abc205_c 解説 https://atcoder.jp/contests/abc205/submissions/23456949 発想力が必要となる問題。 真面目に計算するのは精度的に無理なので、logか…？とも思ったがこちらも精度が心配で、300点っぽくない。 大…

https://atcoder.jp/contests/abc205/tasks/abc205_b 解説 https://atcoder.jp/contests/abc205/submissions/23457038 問題を少し変えて考えてみる。 今回の判定問題は、与えられたAを並び替えて、1,2,3,...,Nになるかというのを考えても問題ない。 と考える…

https://atcoder.jp/contests/abc205/tasks/abc205_a 解説 https://atcoder.jp/contests/abc205/submissions/23457255 単位数である1mLを経由することで計算をしていく。 100 mL -> A kcal 1 mL -> A / 100 kcal B mL -> A / 100 * B kcal ということでA/100…

https://atcoder.jp/contests/abc204/tasks/abc204_f 前提知識 bitDP 行列累乗を使ったDP高速化 解説 https://atcoder.jp/contests/abc204/submissions/23263864 今回の問題はとても難しいのだが、典型度は高い。 まず、制約がかなりとがっているので、何を…

https://atcoder.jp/contests/abc204/tasks/abc204_e 前提知識 ダイクストラ 解説 https://atcoder.jp/contests/abc204/submissions/23263588 問題設定が有向グラフの最短経路問題なので、ダイクストラ法が最初に思いつく。 ダイクストラ法をもじって解くこ…

https://atcoder.jp/contests/abc204/tasks/abc204_d 解説 https://atcoder.jp/contests/abc204/submissions/23262989 この問題はDPで解ける。 いかにDPで解くという所に帰着させるかを説明していこう。 まず、制約がとても小さい。 パッと見て貪欲で行けそ…

https://atcoder.jp/contests/abc204/tasks/abc204_c 前提知識 BFS 解説 https://atcoder.jp/contests/abc204/submissions/23261589 この問題では実装方針から正しく計算量を見積もれるかがポイントとなる。 計算量見積もりをして、オーダーで上限を当てはめ…

https://atcoder.jp/contests/abc204/tasks/abc204_b 解説 https://atcoder.jp/contests/abc204/submissions/23260128 シミュレーションする問題。要求されていることを実装しよう。 それぞれの木の実について、 10以下であれば何もしない 10より大きいならA…

https://atcoder.jp/contests/abc204/tasks/abc204_a 解説 https://atcoder.jp/contests/abc204/submissions/23259935 あいこになるのは全部同じか全部違う場合なので、その2つの状況で場合分けして答えることにしよう。 x=yであれば全部同じの場合なので、x…

https://atcoder.jp/contests/abc203/tasks/abc203_f 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc203/submissions/23075597 まずAはソートしておこう。 これはよくあるテクであるが、ソート可能な配列はソートしておく。 何に気付くべきか こ…

https://atcoder.jp/contests/abc203/tasks/abc203_e 解説 https://atcoder.jp/contests/abc203/submissions/23075564 計算を差分だけになるように気を付けながらポーンの場所を残しつつ、シミュレーションしていく問題。 ans := とあるx座標において、白の…

https://atcoder.jp/contests/abc203/tasks/abc203_d 前提知識 二分探索 二次元累積和 解説 https://atcoder.jp/contests/abc203/submissions/23075536 二分探索しよう。 始めてみる・慣れていない場合はピンとこないと思うが、最大値の最小値というのが二分…

https://atcoder.jp/contests/abc203/tasks/abc203_c 解説 https://atcoder.jp/contests/abc203/submissions/23075028 int N, K; vector<pair<ll, ll>> AB; //--------------------------------------------------------------------------------------------------- ll s</pair<ll,>…

https://atcoder.jp/contests/abc203/tasks/abc203_b 解説 https://atcoder.jp/contests/abc203/submissions/23075335 全ての階層、すべての部屋について全探索して間に合うので全探索しよう。 2重ループで2変数を使うのでごちゃごちゃにならないように注意…

https://atcoder.jp/contests/abc203/tasks/abc203_a 解説 https://atcoder.jp/contests/abc203/submissions/23075477 問題に書いてあることをそのまま実装した。 全部違うかどうかはsetを使って実装して、被っているものがあれば、どこが被っているかを比較…

https://atcoder.jp/contests/abc202/tasks/abc202_e 前提知識 オイラーツアー BIT クエリ先読みと平面走査 解説 https://atcoder.jp/contests/abc202/submissions/22837009 最後までの理解は難しいかもしれないが、問題の言い換え部分までは参考になるかも…

https://atcoder.jp/contests/abc202/tasks/abc202_d 解説 https://atcoder.jp/contests/abc202/submissions/22836918 辞書順に並び替えると、 a???????? b???????? の並びになっており、K番目ということを考えると、このどちらのグループに入るかということ…

https://atcoder.jp/contests/abc202/tasks/abc202_c 解説 https://atcoder.jp/contests/abc202/submissions/22836846 ちょっとだけ整理 今回の問題は、解く前にまずは整理することが重要である。 B[C[j]]の部分であるが、別途配列Dを考えて、単純にD[j] = B…

https://atcoder.jp/contests/abc202/tasks/abc202_b 解説 https://atcoder.jp/contests/abc202/submissions/22836805 シミュレーション問題。 問題で要求されていることを実装しよう。 自分の実装例について説明する。 反転する C++であればreverse関数を使…

https://atcoder.jp/contests/abc202/tasks/abc202_a 解説 https://atcoder.jp/contests/abc202/submissions/22836615 abcについて反対側の面を計算（7-aのように）して総和を求めて答えよう。 特に注意点はないですね。 もし、この問題に詰まった場合は AtC…

https://atcoder.jp/contests/past202104-open/tasks/past202104_o 前提知識 木上での最短経路(LCA, ダブリング, HL分解…) 最短経路問題 解説 https://atcoder.jp/contests/past202104-open/submissions/22667026 最終問題。今までなかなか見たことがない難…

https://atcoder.jp/contests/past202104-open/tasks/past202104_n 前提知識 動的計画法 解説 https://atcoder.jp/contests/past202104-open/submissions/22661300 最小費用流とか貪欲法とか微妙に色々見える問題とか制約になってはいるが、考えてみるとオー…

https://atcoder.jp/contests/past202104-open/tasks/past202104_m 解説 https://atcoder.jp/contests/past202104-open/submissions/22660709 最初に書いておくと実装がとてもしんどいのでデバッグ用出力を駆使しながら実装していく必要がある。 さて、頑張…

https://atcoder.jp/contests/past202104-open/tasks/past202104_l 前提知識 最小全域木 （幾何） 解説 https://atcoder.jp/contests/past202104-open/submissions/22659267 ICPCでよく見るような幾何問題。 幾何問題といっても特殊な知識を要求するものでは…

https://atcoder.jp/contests/past202104-open/tasks/past202104_k 前提知識 動的計画法 解説 https://atcoder.jp/contests/past202104-open/submissions/22655816 買う買わないの問題。スコアがあって最大化するし、同じ商品は複数買えない。 いかにもDPな…

https://atcoder.jp/contests/past202104-open/tasks/past202104_j 前提知識 三分探索 解説 https://atcoder.jp/contests/past202104-open/submissions/22655262 数学の知識と「三分探索」というのを知っているかという問題。 三分探索が分からない場合は別…

https://atcoder.jp/contests/past202104-open/tasks/past202104_i 前提知識 動的計画法 解説 https://atcoder.jp/contests/past202104-open/submissions/22654667 DPに慣れていると問題設定と制約を見るとDPかなと一直線で結びついてしまう。 考察過程が何…

https://atcoder.jp/contests/past202104-open/tasks/past202104_h 解説 https://atcoder.jp/contests/past202104-open/submissions/22654243 缶切りが必要なものと必要でないものを分けて考えよう。 すると、それぞれから最適に缶を選択してくることを考え…

https://atcoder.jp/contests/past202104-open/tasks/past202104_g 解説 https://atcoder.jp/contests/past202104-open/submissions/22652811 何から始めようかという感じであるが、愚直なやり方から考えてみる。 愚直に探索できないか 操作を行っていく上で…

https://atcoder.jp/contests/past202104-open/tasks/past202104_f 解説 https://atcoder.jp/contests/past202104-open/submissions/22645973 問題文で要求されている仕様も難しいが、ちゃんと読み解ければ実装はそれほど難しくない。 foreverとなる場合 自…