DP状態:パリティ
AtCoder
AtCoder900点
ARC-E
NoviSteps3D
橙色diff
DP
シーケンシャルDP
DP状態:state
DP状態空間を絞る
パリティ
DP状態:パリティ
最適化の考察:緩和して解く
単純化:操作の流れを単純化して考える
最適化問題
最大スコア
コーナーケース
ずっと、「2 個分開いているかっこについて、1 個閉じてから、また 1 個開く」というパターンを見落として、WA 12 個がとれなかった!! 問題へのリンク 問題概要 1 - 20 - 13 + 14 - 5 のような、 個の正の整数を「+」「-」で連結した計算式が与えられる。…
AtCoder
AtCoder800点
ARC-D
赤色diff
DP
ゲーム
ゲームDP
数列
数学(整数問題)
操作:整数をreplaceしていく
最大公約数
考察:パリティに着目する
DP状態:パリティ
DP状態削減テク:全部分集合でなく個数のみ持つ
各kに対して
制約:数値が10^6以下
約数系包除
包除原理
数量が小さいことの活用:約数の個数
単調性に着目する
モノグサ社内で同僚と一緒に解いた! 問題へのリンク 問題概要 要素からなる数列 が与えられる。各 に対して次の問に答えよ。 先手と後手が交互にプレイする。整数 を管理する。最初 である。 先手は初手は を選び、 と に更新し、数列からその整数は削除す…
二次元グリッド
数え上げ問題
包除原理
DP
包除原理:DP
AtCoder
除原理
考察:パリティに着目する
DP状態:あまり
EDPCとTDPC
DP状態:パリティ
壁マス
DP状態削減テク:個数でなくパリティのみ持つ
座圧に見えてしまった 問題へのリンク 問題概要 のグリッドがあります。グリッドのうち マスに壁があって壁の位置は で与えられます。壁のあるマスには行けません。 マス からマス へと至る最短経路が何通りあるか、 で割ったあまりを求めよ。 制約 考えたこ…