[PPC] About half [PPC] Compound Word [Crypto] Substitution [Web] Typing game [Shell] netcat [PPC] Balanced Choice [PPC] CPC To F [Web] Let's buy some array [Crypto] RSA Trial [Web] Read Novels [Shell] veeeeeeery long text [PPC] Power! or +…

https://atcoder.jp/contests/abc264/tasks/abc264_c 前提知識 bit全探索 解法 パっと見た感じ難しい問題に見えると思う。 この問題で注目すべき部分は制約である。 盤面のサイズがとても小さく、最大でも10。 制約が小さいということは、少し無茶な解法でも…

https://atcoder.jp/contests/abc259/tasks/abc259_c あるといい知識 （自分の解法では）ランレングス圧縮 解説 https://atcoder.jp/contests/abc259/submissions/33113322 ランレングス圧縮というものを知っていると少し解きやすかったかもしれない。 性質…

https://atcoder.jp/contests/abc259/tasks/abc259_d 前提知識 幾何：円上に点があるかの判別、2円の交差判定 到達可能性判定 解説 https://atcoder.jp/contests/abc259/submissions/33122718 今回の問題は前提として、幾何の以下の判定方法を知っている必要…

https://atcoder.jp/contests/abc257/tasks/abc257_e 前提知識 （構築テクに似たようなものがある。ここのテク2） 解説 https://atcoder.jp/contests/abc257/submissions/32754197 この問題は貪欲法で解く。 アドホックな解法ではあるが、方針としてはテクと…

https://atcoder.jp/contests/abc257/tasks/abc257_d 前提知識 二分探索 BFS （BFSを使わなくても良いやり方もある） 解説 https://atcoder.jp/contests/abc257/submissions/32753407 何から考え始めるか いつものように全探索解法がないか探してみる。 全探…

https://atcoder.jp/contests/abc257/tasks/abc257_c 前提知識 SegTree （だが、使わない解法もあると思う） 解説 https://atcoder.jp/contests/abc257/submissions/32751195 全探索解法に向けて まずは全探索解法がないかを模索してみる。 Xが実数全体を動…

https://atcoder.jp/contests/abc249/tasks/abc249_d 前提知識 約数列挙 解説 https://atcoder.jp/contests/abc249/submissions/31211388 とある数xの約数列挙をO(sqrt(x))で行う方法がある。 もし分からない場合は「約数列挙」あたりで検索して、勉強してく…

https://atcoder.jp/contests/abc249/tasks/abc249_c 前提知識 bit全列挙 解説 https://atcoder.jp/contests/abc249/submissions/31208645 この問題ではbit全列挙が分かっているとスムーズに解くことができる。 bit全列挙については、他に詳しい解説があるの…

https://atcoder.jp/contests/abc248/tasks/abc248_f 前提知識 （連結DP） 解説 https://atcoder.jp/contests/abc248/submissions/31047647 全くメジャーな言い回しではないが、連結DPをする。 ただ単に連結性を状態として持つDP。 一般にこの手のDPでは行列…

https://atcoder.jp/contests/abc248/tasks/abc248_e 解説 https://atcoder.jp/contests/abc248/submissions/31046558 幾何問題。 以下解法、非常に面倒なので、別の解法があるかも… （解法に移る前に） 以下のケースでちょっとはまったので、WAではまってる…

https://atcoder.jp/contests/abc248/tasks/abc248_d 前提知識 二分探索 解説 https://atcoder.jp/contests/abc248/submissions/31044881 色々な解法が見える問題。 実際WaveletMatrixというデータ構造を使えば、一瞬で答えが出るのだが、二分探索解法で説明…

https://atcoder.jp/contests/abc248/tasks/abc248_c 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc248/submissions/31043632 この問題では動的計画法を用いて、答えを作成していく。 動的計画法の入門の次の一手くらいの問題なので、全く分か…

https://atcoder.jp/contests/abc246/tasks/abc246_e 前提知識 拡張ダイクストラ 解説 https://atcoder.jp/contests/abc246/submissions/30681205 問題文とはxとyの解釈を逆にして説明している。 好みの問題ではあるのだが、つまり、チェス盤の上からy行目、…

https://atcoder.jp/contests/abc246/tasks/abc246_d 前提知識 二分探索 解説 https://atcoder.jp/contests/abc246/submissions/30680524 なかなか難しいというか、競プロ的なアプローチを含んだ問題。 二分探索が分かっていない場合はそちらを先に学習して…

https://atcoder.jp/contests/abc245/tasks/abc245_c 解説 https://atcoder.jp/contests/abc245/submissions/30483611 やや丁寧めに説明ぞ書いていく。 何から始めていけばいい？ 問題への取り組み方として、全列挙してみたり、実験してみたり、色々やってみ…

https://atcoder.jp/contests/abc244/tasks/abc244_g 解説 https://atcoder.jp/contests/abc244/submissions/30323833 何から始めればいいか困る問題。 構築問題で重要なのはなるべくシンプルなルールで構築を考えていくことである。 今回は特に最適なパス長…

https://atcoder.jp/contests/abc244/tasks/abc244_f 前提知識 BFS 解説 https://atcoder.jp/contests/abc244/submissions/30322530 今回の問題はbitmaskを状態として利用したbfsで解くことができる。 状態の持ち方としてbitmaskを利用するという方法はbit全…

https://atcoder.jp/contests/abc244/tasks/abc244_e 前提知識 動的計画法 解説 https://atcoder.jp/contests/abc244/submissions/30321733 まず前提としてDPが分かっていないとこの問題を解くことは難しい。 DPが未履修であれば、先に学習してこよう。 DPの…

https://atcoder.jp/contests/abc239/tasks/abc239_e 前提知識 オイラーツアー セグメントツリー 解説 https://atcoder.jp/contests/abc239/submissions/29488895 データ構造でゴリ押して解けそうな感じもするし、Kの値が小さいことを利用して、楽に解くこと…

https://atcoder.jp/contests/abc239/tasks/abc239_e 前提知識 オイラーツアー セグメントツリー 解説 https://atcoder.jp/contests/abc239/submissions/29488895 データ構造でゴリ押して解けそうな感じもするし、Kの値が小さいことを利用して、楽に解くこと…

この記事は競技プログラミングを始めたばかりの人に伝えたいことのカレンダー | Advent Calendar 2021の10日目の記事です。 カレンダーを見るとネタ被りをしていたのでテーマを変更しました。 競技プログラミングには色々な要素があり、初めて競プロを始めた…

この記事は競プロ Advent Calendar 2021の10日目の記事です。 長年、競技プログラミングをやってきた。 気が付けば、最初に競技プログラミングを初めてから既に6年が過ぎていた。 別にこの記事を何らかの区切りにしようとか、そういった意図はないのだが、振…

https://atcoder.jp/contests/past202109-open/tasks/past202109_k 前提知識 最小費用流 (もしくは重み付き二部グラフ上での最大マッチング) 解説 https://atcoder.jp/contests/past202109-open/submissions/26707534 慣れていると、この問題がかなりフロー…

https://atcoder.jp/contests/past202109-open/tasks/past202109_j 前提知識 遅延評価セグメントツリー 解説 https://atcoder.jp/contests/past202109-open/submissions/26703507 遅延評価セグメントツリー以外にも沢山実装方法があるように見える。 今回、…

https://atcoder.jp/contests/past202109-open/tasks/past202109_i 解説 https://atcoder.jp/contests/past202109-open/submissions/26690153 難しい問題。色々方針が思い浮かぶかもしれないが、思いつかないと中々厄介だろうと思う。 本質を見抜く 実は、今…

https://atcoder.jp/contests/past202109-open/tasks/past202109_h 前提知識 LCA 解説 https://atcoder.jp/contests/past202109-open/submissions/26687334 今回の問題は制約が割と緩いので、基本的な典型アルゴリズムを理解していると解ける。 愚直に考えて…

https://atcoder.jp/contests/past202109-open/tasks/past202109_g 前提知識 二分探索 解説 https://atcoder.jp/contests/past202109-open/submissions/26603092 この問題は正直典型問題として知っていないと解くのは難しいように思う。 二分探索を利用する…

https://atcoder.jp/contests/past202109-open/tasks/past202109_f 構築 解説 https://atcoder.jp/contests/past202109-open/submissions/26602840 構築問題。 構築問題の基本は、シンプルな構築ルールである。 なるべく簡単に簡単に条件を満たせるルールを…

https://atcoder.jp/contests/past202109-open/tasks/past202109_e 解説 https://atcoder.jp/contests/past202109-open/submissions/26602632 貪欲法で解いていく。 かかる値段を最小化したいと考えた場合、簡単な方針として、安いものから選択するという方…