2020-09-23から1日間の記事一覧
AtCoder
AtCoder600点
ARC-like
二次元グリッド
パズル
フロー
グラフ
マッチング
二部マッチング
最小費用流問題
操作
ロボット
多点を扱う問題
前処理
最短路問題
BFS
下駄を履かせて負辺除去
グラフの辺数を削減する
青色diff
【問題集】フローの入門
割当問題
駒(コマ)や石やコインを扱う問題
穴や盤外に落とす問題
典型要素を詰め合わせた教育的問題
グラフの辺数削減テク:うまく並べて隣接する部分のみに辺を張る
壁マス
フローって確かに天才パズルな問題はすごく天才的なんだけど、典型的な問題もたくさんある! 問題へのリンク 問題概要 下図のような の盤面が与えられる。盤面は通路 ('.') と壁 ('#') がある。いくつかの通路にはコマ ('o') が配置されている。 コマは下方…
AtCoder
AtCoder600点
数学(整数問題)
入力が定数個
テク:約数の個数は少ない
素因数分解
全探索:ビット全探索
全探索
拡張Euclidの互除法
中国剰余定理
枝刈り
互いに素
オーバーフロー
ある量を固定して考える
青色diff
【問題集】整数変数の式で表された条件を扱う探索
中国剰余定理使う問題楽しいよね! 問題へのリンク 問題概要 正の整数 が与えられる。以下の条件を満たす最小の正の整数 を求めよ。 が の倍数である 制約 考えたこと まず、 なので、問題の条件は次と同値になる。 が の倍数である ここで改めて を で置き…
AtCoder
AtCoder300点
Union-Find
平面走査
setの上手な使い方
ならし計算量解析
連結成分
順列を題材とした問題
二次元平面上のN点の問題
各kに対して
二値パラメータ問題
探索順序を工夫して解く
復元
Greedy:どちらも可なら厳しい方
データ構造
stack
連結性に着目する
数学的帰納法に基づく考察
ARC-like
水色diff
可視化テク:二次元平面上に可視化する
操作をstackを用いて高速化する
えーーー、300 点!? 問題へのリンク 問題概要 二次元平面上に 点が与えられる。これらの点の x 座標、y 座標を抽出すると、それらは の順列となっている。 各 に対して、点 から 自分よりも x 座標と y 座標がともに大きな点 自分よりも x 座標と y 座標が…