selpo's diary

主に競プロの解説をします。C#erです。

問題E『数式とクエリ』: codeFlyer 本選

問題文 : 数式とクエリ

概要

以下のBNF表記の<expr>で表される数式Sと、S中の左からi番目の変数aの初期値a_iが与えられる。(b_q,x_q)からなるQ個のクエリに答えよ。

  • S中の左からb_q番目以外の変数は初期値のままで、b_q番目の変数にx_qを代入したときの数式の値を10^9+7で割ったあまりを出力する。
<expr> ::= <term> | <expr> '+' <term> | <expr> '-' <term>
<term> ::= <value> | <term> '*' <value>
<value> ::= 'a' | '(' <expr> ')' 

制約

  • |S|\leq200000

  • Q\leq100000

続きを読む

問題C『+/- Rectangle』 : AtCoder Grand Contest 016

問題文 : +/- Rectangle

概要

H\times Wの盤面に整数を書き込んで、次の条件を満たすようにできるか?できるなら具体的に作れ。

  • h\times wの大きさの部分長方形を任意に取ってくると、その中での総和は必ず負
  • 盤面全体の総和は正
制約

1\leq h\leq H\leq 500
1\leq w\leq W\leq 500

続きを読む

問題B『チョコレート』 : AtCoder Regular Contest 025

O(H^2W^2)解法しか見当たらなかったので。

問題文 : チョコレート

概要

H\times Wの盤面上に整数C[x,y]が書かれており、市松模様の色(白、黒)が塗られている。
盤面上に含まれる長方形領域のうち、その中に書かれた白と黒の総和が一致するようなものの面積の最大値を求めよ。

制約

1\leq H,W\leq 100
0\leq C_{x,y}\leq 1000

解説

累積和をとって長方形を全列挙すれば一応O(H^2W^2/4)で、/4のおかげでギリギリセーフだが…。

続きを読む

問題E『六角形』 : MUJIN プログラミングチャレンジ

ほとんど数学の問題でした。

問題文 : 六角形

概要

z=0上の凸六角形(頂点(x_i,y_i)は反時計回り)が与えられる。
この六角形を断面として持つ直方体は存在するか。
存在しなければ-1を答え、存在すればそのような直方体の体積の最小値を答えよ。

制約

0\leq x_i,y_i\leq 1000
座標はいずれも整数。

解説

実は、存在するときは直方体は一意に定まる。
f:id:selpoG:20160229235610p:plain:w500
直方体の断面が六角形になるのは、図のような場合。

続きを読む

問題C『N!÷K番目の単語』 : ARC(AtCoder Regular Contest) 047

問題文 : N!÷K番目の単語

概要

1,2,\ldots,Nの並び替え(N! 個ある)を辞書順に並べたとき、
1-indexedでN!/K番目にくる並び替えは何か。

制約

1\leq K\leq N\leq 10^5

解説

並び替えといえば階乗進数。
0-indexedでN!/K-1番目の数に対応する階乗進数表記が求まればよい。
階乗進数と順列の対応付け - 猫尾製作所
とりあえず、階乗進数と並び替えの関係について説明する。

続きを読む

DDPC 2016 本選 問題Cの補足

計算量がよくわからないとか言ってましたが、実はO(|S|^2)らしいです。

というのも、長さ2xの括弧列に対する計算量をf(x)とすると、
(1)f(x+1)=f(x)+ax
(2)f(x+y)=f(x)+f(y)+bxy
となるはずです(a,bは正の定数)。

仮にf(x)\leq Cx^2としてみましょう。

(1)f(x+1)\leq Cx^2+ax\leq C(x+1)^2
となるためには、2C\geq aであればよいです。
(2)f(x+y)\leq Cx^2+Cy^2+bxy\leq C(x+y)^2
となるためには、2C\geq bであればよいです。

よって、C=\max(a,b)/2のときf(x)\leq Cx^2が成立します。
逆に、(((\cdots)))のような入力では明らかにO(x^2)なので、
f(x)=\Theta(x^2)となります。

前回、(2)のほうが計算量的に重たいとか言ってましたが、
実は(1)も(2)も(長さの増え方を考えると)同じくらいの計算量なんですね。

ちなみに、僕の解法はいわゆる木DPと同等らしく、
一見O(N^3)だけど実はO(N^2)、というのは有名な話らしいです。
参考 : 二乗の木 DP - (iwi) { 反省します - TopCoder部

問題C『特別講演「括弧列と塗り分け」』 : DDPC(DISCO presents ディスカバリーチャンネル プログラミングコンテスト)2016 本選

問題文 : 特別講演「括弧列と塗り分け」

概要

きちんと対応の取れている、括弧のみからなる文字列Sがある。
非負整数Kが与えられたとき、以下の場合の数(をM=10^9+7で割った余り)を求めよ。

0\leq i<|S|のそれぞれにx_i=\pm 1を割り当てる方法xのうち、以下の条件を満たすものの個数。
(条件) 任意のi\lt jについて、S_i='('とS_j=')'が対応するならば、\displaystyle -K\leq \sum_{i\leq k\leq j}x_k\leq Kが成立する。

制約

2\leq |S|\leq 3000
0\leq K\leq 3000

解説

問題文に「括弧の対応に矛盾がない文字列」の定義があります。
BNFで書くと、
T ::= | (T) | TT
(あるいは空文字列を除けば T ::= () | (T) | TTとも表せる)
です。これがヒントになっています。

続きを読む