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