2019-02-10から1日間の記事一覧
累積和
前処理
3つのものの真ん中に着目する
AOJ
JOI本選
JOI
JOI難易度5
0と1と2の問題
典型要素を詰め合わせた教育的問題
解空間:O(N^2)通りの選択肢
二次元グリッド
ある量を固定して考える
【問題集】累積和
累積和テク:条件を満たすものの個数を累積和で表す
縦方向と横方向の情報を整理する
累積和テク:累積和や累積結果を前処理しておく
とりあえず 1 問目やってみた!累積和の典型題 問題へのリンク 問題概要 以下のような J, O, I で構成される N × M の盤面があたえられる。以下の条件を満たすような 3 マスの組が何個あるか求めよ。 3 マスはそれぞれ J, O, I である J の右側 (行は一緒) …
DP
数え上げ問題
操作
操作後の結果の数え上げ
条件の言い換え
必要条件を列挙したら十分条件になる
AtCoder
AtCoder900点
順列の数え上げ
二項係数
ナップサックDP
黄色diff
ARC-like
ARC-F
21:01 発の磐越西線 (会津若松 -> 郡山) に乗りながらのコンテスト参戦だった。 元々コンテスト出ないで問題だけ読んで考察だけ楽しむつもりが、この F がスラッと解けたので思わず提出してしまった。この段階ではまだ電波状態が大丈夫だった...のと、やはり…
行列
Gauss-Jordanの掃き出し法
0と1の問題
パリティ
条件の言い換え
AtCoder
AtCoder800点
数え上げ問題
「選ぶ」と「選ばない」の一対一対応
二項係数
橙色diff
ARC-like
すごく面白そうだし、これ考えたかった 問題へのリンク 問題概要 × の binary 行列 が与えられる。 行集合の部分集合 通り 列集合の部分集合 通り の組であって、 の各要素のうち、行と列がともに該当する部分集合に含まれるようなものの総和が奇数となって…
区間
DP
ナップサックDP
パリティ
AtCoder
AtCoder600点
条件の言い換え
操作
最小回数・最小個数を求める
最小コスト
DP状態:フェーズ(耳DP)
操作の流れを単純化する
ARC-like
青色diff
最適化問題
郡山駅のベンチで寒さに震えながらやる問題ではなかった...必要以上に複雑にしてしまった。。。 問題へのリンク 問題概要 すぬけさんが、座標 0 と との間を行ったり来たりする。行って方向転換できる場所は整数座標のみである。 このとき、各区間 [ ] () に…