2019-06-10から1日間の記事一覧
AtCoder
AtCoder600点
ABC-F
特殊なmod
行列
行列累乗
総和を求める
多項式・FPS(形式的冪級数)
各桁ごとに見る
級数和を求める
整数値のconcatを考える問題
主客転倒
個別の要素の動きに注目する
橙色diff
数学(代数)
ダブリング
重たい。。。 でも例えば行列 に対して の計算を行列累乗に帰着させるテクニックは、蟻本中級編の行列累乗のところに載っていたりする。それを膨らませると みたいな計算も、行列累乗でできそうという気持ちには確かになるよね。。。(なったけど昨日間に合わ…
AtCoder
AtCoder500点
ABC-E
XOR
条件の言い換え
数え上げ問題
各桁ごとに見る
DP状態:smaller(桁DP)
DP
0と1の問題
水色diff
どの場所で初めてsmallerになるかを考える
DP状態:どの桁まで見たか(広義の桁DP)
制約条件:ある値<=K
まさにこの考え方で解ける問題 drken1215.hatenablog.com 今回の問題も桁 DP でもよいのだが、実は桁 DP しなくても解ける。 問題へのリンク 問題概要 正整数 が二進数表記で与えられます。 以下の条件を満たす非負整数 の組がいくつ存在するか求めてくださ…
AtCoder
AtCoder400点
ABC-D
二次元グリッド
前処理
壁にぶつかるまで動く
累積max
緑色diff
「次の要素」へのポインタを求める
競プロ典型90問とその類題
縦方向と横方向の情報を整理する
典型要素を詰め合わせた教育的問題
累積和の亜種
累積和
壁マス
for文:各マスに対して「次のイベントマス」を求める
これも実はよくある典型問題だったりはする。 問題へのリンク 問題概要 下のような の二次元グリッドが与えられる。 #..#.. .....# ....#. #.#... このグリッドで '#' は壁を表している。ここで '.' マスを 1 つ選んで、そこに光源を置きたい。光源が照らす…
いわゆる本当に最初の入門という感じの DP だね。 問題へのリンク 問題概要 段の階段があって、現在は 0 段目にいる。 高橋君は一歩で 1 段か 2 段上がることができる。ただし 段目は壊れていて、そこに足を踏み入れることはできない。 高橋君が 0 段目から …