問題C『+/- Rectangle』 : AtCoder Grand Contest 016
問題文 : +/- Rectangle
概要
の盤面に整数を書き込んで、次の条件を満たすようにできるか?できるなら具体的に作れ。
- の大きさの部分長方形を任意に取ってくると、その中での総和は必ず負
- 盤面全体の総和は正
制約
問題C『N!÷K番目の単語』 : ARC(AtCoder Regular Contest) 047
問題文 : N!÷K番目の単語
概要
の並び替え( 個ある)を辞書順に並べたとき、
1-indexedで番目にくる並び替えは何か。
制約
解説
並び替えといえば階乗進数。
0-indexedで番目の数に対応する階乗進数表記が求まればよい。
階乗進数と順列の対応付け - 猫尾製作所
とりあえず、階乗進数と並び替えの関係について説明する。
DDPC 2016 本選 問題Cの補足
計算量がよくわからないとか言ってましたが、実はらしいです。
というのも、長さの括弧列に対する計算量をとすると、
(1)
(2)
となるはずです(は正の定数)。
仮にとしてみましょう。
(1)
となるためには、であればよいです。
(2)
となるためには、であればよいです。
よって、のときが成立します。
逆に、のような入力では明らかになので、
となります。
前回、(2)のほうが計算量的に重たいとか言ってましたが、
実は(1)も(2)も(長さの増え方を考えると)同じくらいの計算量なんですね。
ちなみに、僕の解法はいわゆる木DPと同等らしく、
一見だけど実は、というのは有名な話らしいです。
参考 : 二乗の木 DP - (iwi) { 反省します - TopCoder部
問題C『特別講演「括弧列と塗り分け」』 : DDPC(DISCO presents ディスカバリーチャンネル プログラミングコンテスト)2016 本選
問題文 : 特別講演「括弧列と塗り分け」
概要
きちんと対応の取れている、括弧のみからなる文字列がある。
非負整数が与えられたとき、以下の場合の数(をで割った余り)を求めよ。
のそれぞれにを割り当てる方法のうち、以下の条件を満たすものの個数。
(条件) 任意のについて、'('と')'が対応するならば、が成立する。
制約
解説
問題文に「括弧の対応に矛盾がない文字列」の定義があります。
BNFで書くと、
T ::= | (T) | TT
(あるいは空文字列を除けば T ::= () | (T) | TTとも表せる)
です。これがヒントになっています。