2021-07-24から1日間の記事一覧
https://atcoder.jp/contests/abc211/tasks/abc211_e 前提知識 BFS 解説 https://atcoder.jp/contests/abc211/submissions/24516205 入力例3を見ると答えの最大数はあまり大きくないので、正しい候補を列挙すればよさそうに見える。 全探索だろうという方針…
https://atcoder.jp/contests/past202107-open/tasks/past202107_i 前提知識 幾何問題 解説 https://atcoder.jp/contests/past202107-open/submissions/24478121 幾何問題である。複素数を使って座標を保持しながら、幾何的な操作を行っていくのがいい。 幾…
https://atcoder.jp/contests/past202107-open/tasks/past202107_o 前提知識 動的計画法 累積和 priority_queue, multiset 解説 https://atcoder.jp/contests/past202107-open/submissions/24477460 最初の考察方針というのはだいぶパフォーマンスに影響する…
https://atcoder.jp/contests/past202107-open/tasks/past202107_n 前提知識 平面走査 座標圧縮 遅延評価セグメントツリー 解説 https://atcoder.jp/contests/past202107-open/submissions/24475768 今回の問題は最低限遅延評価セグメントツリーを理解してい…
https://atcoder.jp/contests/past202107-open/tasks/past202107_m 前提知識 最小費用流 解説 https://atcoder.jp/contests/past202107-open/submissions/24472779 今回の問題は最小費用流が分かっていないと解けないので、どこかで学習してきてほしい。 最…
https://atcoder.jp/contests/past202107-open/tasks/past202107_l 前提知識 セグメントツリー 解説 https://atcoder.jp/contests/past202107-open/submissions/24471772 解法を思いつくのも難しいが、ならし計算量(償却計算量)も意識する必要があり、そこ…
https://atcoder.jp/contests/past202107-open/tasks/past202107_k 前提知識 ダイクストラ 解説 今回の問題は無向グラフが与えられて頂点1から頂点Nへの最短距離で、かつ、満足度が最高のものを選択することが目的。 特に前半の「無向グラフが与えられて頂点…
https://atcoder.jp/contests/past202107-open/tasks/past202107_j 前提知識 DAG判定、トポロジカルソート 解説 https://atcoder.jp/contests/past202107-open/submissions/24466589 問題を簡単化しよう 都市を頂点、道路を有向辺と捉えると、全体が有向グラ…
https://atcoder.jp/contests/past202107-open/tasks/past202107_h 前提知識 動的計画法 解説 https://atcoder.jp/contests/past202107-open/submissions/24466156 多次元のDPをくみ上げていく。 問題設定的にはいかにもDPっぽいという感じではあるが、慣れ…
https://atcoder.jp/contests/past202107-open/tasks/past202107_g 解説 https://atcoder.jp/contests/past202107-open/submissions/24465845 何から始めるか このような構築問題は、慣れないうちは何から始めていいか分からないと思う。 とりあえずいくつか…
https://atcoder.jp/contests/past202107-open/tasks/past202107_f 解説 https://atcoder.jp/contests/past202107-open/submissions/24465658 判定を効率化する問題。 大変そうに見えるが、特に大きなひねりはなく、愚直に実装すれば間に合う。 慣れている人…
https://atcoder.jp/contests/past202107-open/tasks/past202107_e 解説 https://atcoder.jp/contests/past202107-open/submissions/24461067 この問題は勘がいい人だと3進数を利用したような問題だなと感じるかもしれない。 それが見えてれば比較的見通しの…
https://atcoder.jp/contests/past202107-open/tasks/past202107_d 解説 https://atcoder.jp/contests/past202107-open/submissions/24466988 ちょっと考察、ちょっと実装の問題。 操作回数が最大となる操作 ここがまず1つ考察が必要な部分である。 今回は実…
https://atcoder.jp/contests/past202107-open/tasks/past202107_c 解説 https://atcoder.jp/contests/past202107-open/submissions/24460011 要求されている判定を行う実装問題。 自分の実装では色々な工夫をすることで、なるべく実装を減らしている。 まず…
https://atcoder.jp/contests/past202107-open/tasks/past202107_b 解説 https://atcoder.jp/contests/past202107-open/submissions/24459788 シミュレーション問題。 計算一本でも求めることができるが、言われているシミュレーションを動かすことでも求め…
https://atcoder.jp/contests/past202107-open/tasks/past202107_a 解説 https://atcoder.jp/contests/past202107-open/submissions/24459496 シミュレーション問題。 問題で要求されていることを実装しよう。 まず、自分の実装ではコードを文字列で取り込ん…