selpo's diary

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

問題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とも表せる)
です。これがヒントになっています。

続きを読む

問題B『DDPC特別ビュッフェⅡ』 : DDPC(DISCO presents ディスカバリーチャンネル プログラミングコンテスト)2016 本選

冷静に考えればそこまで難しくはないのですが、
朝だと頭が働かず、本番中には解けませんでした。

問題文 : DDPC特別ビュッフェⅡ

概要

N種類の料理があり、i番目の料理は時刻T_iまでしか食べられない。
また、それぞれの料理にはスコアA_iが決まっており、一度食べたらなくなる。
それぞれの時刻(t\geq 1)ではt\leq T_iの料理をひとつ選んで食べることができる。

うまく食べる料理を選ぶとき、スコアの合計をX以上にするのに必要な時間の最小値を出力せよ。
どうやってもX以上のスコアにできなければ、-1を出力せよ。

制約

1\leq N\leq 10^5
1\leq T_i\leq 10^5
1\leq A_i\leq 10^5
1\leq X\leq 10^9

解説

美味しい料理から食べていけばよさそうだが、制限時間の緩い(T_iの大きい)料理は後回しにしたい。
どれくらい後回しにできるか、とか考えるといろいろと面倒(←何回もバグりました)。

続きを読む