撹乱順列とは {1,2,3,...n}の順列で，どの要素も元の位置にないような順列を撹乱順列(またの名を完全順列)といいます．例えばn=3の撹乱順列として{2,3,1},{3,2,1},{3,1,2}とかが挙げられます．{2,1,3}とかは撹乱順列ではありません．3番目の要素が元の位置に…

jag2016-domestic.contest.atcoder.jp 誤って書いた記事を消してしまったので再投稿です． 問題文 省略 解法(反転して表示) LL(1)による再帰構文解析を知っていると特に思考をせず木構造に直すことができる． 木に落としたらマージをするが，これは再帰でや…

jag2016-domestic.contest.atcoder.jp 本番バグらせて解けなかった悲しいね． 問題文 省略 解法(反転して表示) 基本的な方針はDPと場合分け．累積和とかである区間の値の総和がO(1)で求めれるように前処理しとく． マスは全て非負なので，空き空間は特に作っ…

jag2016-domestic.contest.atcoder.jp 問題文 省略 解法(反転して表示) オーソドックスな幾何． 列挙して意味のある候補点を列挙する．この候補点に意味のない点が含まれていてもいいので雑に． 候補点を列挙するために，有権者から各多角形の頂点への直線を…

jag2016-domestic.contest.atcoder.jp 問題文 省略 解法(反転して表示) よくあるゲーム木のmin-max探索，後手は差を最小化，先手は差を最大化するように実装する． 状態数がどれくらいになるのかを見積もるのが本質． 実際山札の残り枚数と，どの区間(※)がス…

jag2016-domestic.contest.atcoder.jp 問題文 省略 解法(反転して表示) 時刻 a に宅配便が届くと，[a-M,a+M)の範囲に書斎には居られない． なので，[0,T)の範囲で区間に含まれていない時刻を列挙すれば良い． 境界に気をつけつつ，愚直にシミュレーションす…

jag2016-domestic.contest.atcoder.jp 問題文 省略 解法(反転して表示) 本質的には括弧列が与えられるのでvalidな括弧列ですかという問題に言い換えれば見通し良く解ける． カウンタを定義する．「A」が来たらカウンタをインクリメント，「Un」が来たらデク…

なんか面倒くさかったので，困っている人のためにメモ そもそもWindowsはscipyのインストールが面倒くさい．↓を参考にしてお手軽にインストールした． Windows で VirtualEnv の Python2.7 に pip と wheel を使って コンパイルエラーが発生するパッケージ(…