2022-04-03から1日間の記事一覧
包除原理を学べる問題! 問題へのリンク 問題概要 個の文字列 が与えられます。次の手順によって作れる長さ の文字列の個数を 998244353 で割ったあまりを求めてください。 のいずれかを選ぶ 文字列 に含まれる文字のみを使って、長さ の文字列を作る 制約 …
AtCoder
AtCoder500点
ABC-E
水色diff
迷路
二次元グリッド
BFS
0-1BFS
最小回数・最小個数を求める
最短路問題
壁にぶつかるまで動く
グラフの頂点を倍加する
グラフの辺数を削減する
枝刈りBFS
【問題集】DFS・BFSのステップアップ
【問題集】最短路問題
DP状態:向き
グラフの辺数削減テク:頂点に向き情報を付加する
DP状態:直前の場所
グラフの辺数削減テク:うまく並べて隣接する部分のみに辺を張る
壁マス
最適化問題
迷路の最短路問題なので BFS でやりたくなるが、まともにやると で TLE してしまう!! 頂点の持ち方を工夫して 0-1 BFS で解く! 別解として枝刈り BFS も。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられます。各マスは通路 (文…
AtCoder
AtCoder400点
ABC-D
緑色diff
式変形
ある量を固定して考える
二分探索
二分探索:lower_bound
多項式・FPS(形式的冪級数)
方程式
見積り大事
数学(整数問題)
しゃくとり法
単調性に着目する
【問題集】整数変数の式で表された条件を扱う探索
前回の ABC に続いて、D 問題が数学っぽい。でも実際には今回は探索問題ですね。 問題へのリンク 問題概要 非負整数 を用いて と表せる整数 を「特別数」と呼ぶことにします。 非負整数 が与えられますので、 以上である最小の「特別数」を求めてください。 …
AtCoder
AtCoder300点
ABC-C
灰色diff
ソート
Greedy
探索順序を工夫して解く
小さいところで帳尻を合わせる
コーナーケース
priority_queue
Greedy:交換しても悪化しない
数列
価格に関する問題
操作をちょうどK回行う
制約条件:ちょうどK個
ソート:条件を満たすまで大きい順に取っていく
【問題集】ソート
ソートが必要になるところが少し難しいかもしれない。 問題へのリンク 問題概要 個の商品があって、それぞれ 円である。 またクーポンが 枚あって、1 枚のクーポンを使って次のことができる。 商品を 1 つ選ぶ その商品の価格を 円減少させる ただしもとの価…