テク:移動可能区間を遷移していく
AOJ
HUPC
数え上げ問題
操作によって作れるものの集合を考える(判定関数を考える)
操作
操作後の結果の数え上げ
区間
区間ソート
Greedy
DP
テク:移動可能区間を遷移していく
ナップサックDP
座標圧縮
最適化テク:探索候補を絞る
最適化テク:端点のみを考える
DP状態空間を絞る
比較的素直な考察で解ける問題 問題へのリンク 問題概要 umgくんは 1 次元上の座標 0 にいます。今は時刻 0 です。時刻が 1 進むごとに、今いる座標より 1 大きい座標に移動するか、 1 小さい座標に移動するか、その座標にとどまるかという行動ができます。 …
AtCoder
AtCoder400点
AGC-B
テク:スタートを0としてよい
連結性に着目する
区間
条件の言い換え
Yes/No判定問題
数列
テク:移動可能区間を遷移していく
青色diff
考える整数が連続することに着目する
むむむ 問題へのリンク 問題概要 長さ の整数列 であって、 が 以上 以下の整数 となるものが存在するかどうかを判定せよ。 制約 考えたこと とりあえず , としてよい。 さて、 からスタートして、 ターン目にどんなのを作れるかを考察してみる。 1 ターン目…
操作列が文字列で与えられる
AtCoder
AtCoder600点
AGC-B
後ろから解く
二次元グリッド
Greedy:各要素について独立に考えてよい
Yes/No判定問題
連結性に着目する
テク:移動可能区間を遷移していく
ロボット
穴や盤外に落とす問題
水色diff
><
x軸とy軸について独立に考えてよい
嘘貪欲は一瞬脳裏によぎり、それを振り払って問題を解いてた。発想はこれの「後ろから解く」のに似ている。 drken1215.hatenablog.com 問題へのリンク 問題概要 × のグリッドのあるマスにロボットが置かれている。先手と後手はそれぞれ長さ の自分の文字列 …
AtCoder
AtCoder500点
二分探索
操作
操作を逆順に見る
非自明な線形時間
連結性に着目する
区間
単調性に着目する
操作列が文字列で与えられる
後ろから解く
テク:移動可能区間を遷移していく
穴や盤外に落とす問題
ロボット
青色diff
ARC-C
操作後の結果を求める問題
N個の点などを一律に動かす設定の問題
頭の整理が大変！！！ 問題へのリンク 問題概要 左から右に向かって 1 から N の番号がついた N 個のマスがあります。 各マスには文字が書かれており、マス i には文字 si が書かれています。また、各マスにははじめ 1 体のゴーレムがいます。 すぬけ君は Q …
