D - 水ようかん (Mizuyokan)

D - 水ようかん (Mizuyokan)


時間制限 : 2sec / メモリ制限 : 256MB

配点 : 100 点

問題文

水ようかんとは,おもに小豆からなる餡を型に流し込んで寒天で固めることにより作られる和菓子である.いま,JOI 君の手元には,横長の直方体の形をした水ようかんがひとつある.JOI 君は,今日のおやつとしてこの水ようかんを食べる予定である.

この水ようかんには,縦方向の切れ目が全部で N−1 箇所に入っている.水ようかんの長さは L1+L2+…+LN であり,i 番目 (1≦iN−1) の切れ目は,左から L1+L2+…+Li の位置にある.

この水ようかんは丸ごと食べるには大きすぎるので,JOI 君は,水ようかんに入っている切れ目から 1 箇所以上を選び,選んだ切れ目に沿って水ようかんを切って,複数のピースに切り分けることにした.ただし,ピースの大きさが不揃いでは見栄えが悪いので,長さ最大のピースと最小のピースの長さの差ができるだけ小さくなるように切ることにした.

長さ最大のピースと最小のピースの長さの差の最小値を求めよ.

制約

  • 2≦N≦50
  • 1≦Li≦1000(1≦iN)

入力

入力は以下の形式で標準入力から与えられる.

N
L1
L2
:
LN

出力

長さ最大のピースと最小のピースの長さの差の最小値を 1 行で出力せよ.

小課題 1 [10点]

  • N≦15

小課題 2 [27点]

  • Li≦10(1≦iN)

小課題 3 [63点]

  • 追加の制限はない.

入力例 1

Copy
11
2
3
8
4
7
6
6
5
1
7
5

出力例 1

Copy
2

この例では,4 番目および 7 番目の切れ目に沿って切り分けることで,長さ 17,19,18 の 3 つのピースに切り分けることができる. このとき,いちばん長いピースは長さ 19 で,いちばん短いピースは長さ 17 であるので,長さの差は 2 となる. これが最小値なので,2 を出力する.


入力例 2

Copy
2
1
10

出力例 2

Copy
9

どんなに大きさが不揃いであっても,必ず 1 箇所以上を切る必要がある.


入力例 3

Copy
5
5
5
5
5
5

出力例 3

Copy
0

この例では水ようかんをちょうど同じ大きさの 5 つのピースに分割できる.

F - L番目のK番目の数 (LthKthNumber)

F - L番目のK番目の数 (LthKthNumber)


時間制限 : 2sec / メモリ制限 : 256MB

配点: 100 点

問題文

横一列に並べられた N 枚のカードがある.左から i 枚目(1≦iN)のカードには,整数 ai が書かれている.

JOI 君は,これらのカードを用いて次のようなゲームを行う.連続する K 枚以上のカードの列を選び,次の操作を行う.

  • 選んだカードを,書かれている整数が小さい順に左から並べる.
  • 並べたカードのうち,左から K 番目のカードに書かれた整数を紙に書き出す.
  • 選んだカードを,すべて元の位置に戻す.

この操作を,連続する K 枚以上のカードの列すべてに対して行う.すなわち,1≦lrN かつ Krl+1 を満たすすべての (l,r) について,al,al+1,…,ar のうち K 番目に小さな整数を書き出す.

こうして書き出された整数を,左から小さい順に並べる.並べた整数のうち,左から L 番目のものがこのゲームにおける JOI 君の得点である.JOI 君の得点を求めよ.

制約

  • 1≦N≦200000
  • 1≦KN
  • 1≦aiN
  • 1≦L
  • JOI 君が書き出す整数は L 個以上である.

入力

入力は以下の形式で標準入力から与えられる.

N K L
a1 a2  aN

出力

JOI 君の得点を 1 行で出力せよ.

小課題 1 [6点]

  • N≦100

小課題 2 [33点]

  • N≦4000

小課題 3 [61点]

  • 追加の制限はない.

入力例 1

Copy
4 3 2
4 3 1 2

出力例 1

Copy
3

1≦lrN(=4) かつ K(=3)≦rl+1 を満たす (l,r) は,(1,3),(1,4),(2,4) の 3 通りある.

これらの (l,r) に対し,al,al+1,…,ar で 3 番目に小さな整数は,それぞれ 4,3,3 である.

このうち L(=2) 番目に小さい整数は 3 なので,JOI 君の得点は 3 である.同じ整数が複数あるときも,重複して数えることに注意せよ.


入力例 2

Copy
5 3 3
1 5 2 2 4

出力例 2

Copy
4

JOI 君が書き出す整数は,

  • (l,r)=(1,3) に対し 5
  • (l,r)=(1,4) に対し 2
  • (l,r)=(1,5) に対し 2
  • (l,r)=(2,4) に対し 5
  • (l,r)=(2,5) に対し 4
  • (l,r)=(3,5) に対し 4

である.このうち L(=3) 番目に小さい整数は 4 である.


入力例 3

Copy
6 2 9
1 5 3 4 2 4

出力例 3

Copy
4

入力例 4

Copy
6 2 8
1 5 3 4 2 4

出力例 4

Copy
3

JOI2017-2018 予選 E - 森林伐採(Deforestation)

E - 森林伐採(Deforestation)


時間制限 : 2sec / メモリ制限 : 256MB

配点 : 100 点

問題文

JOI 王国には広大な森林がある.森林は長方形の形をしており,南北に H マス,東西に W マスのマス目状に分けられている.北から i マス目,西から j マス目(1≦iH,1≦jW)の領域には Ai,j 本の木が生えている.ただし,北西の端の領域には木材加工工場があり,木が生えていない.すなわち,A1,1=0 である.

木が生えていない領域には人が立ち入ることが出来る.また人は東西南北に隣接する領域に,その領域に木が生えていなければ,移動することができる.森林の外に出ることはできない.JOI 君は JOI 王国の公共事業として,木を伐採し,北西の端の領域と南東の端の領域を,相互に行き来可能にしたい.

木の伐採は以下のようにして行う.はじめ,JOI 君は木材加工工場のある北西の端の領域にいる.JOI 君は,現在いる領域と東西南北に隣接する木の生えていない領域に 1 分で移動することができる.また,東西南北に隣接する木の生えている領域から,1 分で木を 1 本伐採することができる.ただし,木を 1 本伐採したら,そのたびに北西の端の領域にある木材加工工場まで伐採した木を運ばなければならない.木を運んでいる間も,JOI 君の移動速度は変わらない.木を運んでいる間は,他の木を伐採することはできない.

条件を満たすように木を伐採するのにかかる時間の最小値を求めよ.ただし,伐採にかかる時間とは,最後に伐採した木を,木材加工工場に運ぶまでの時間とする.

制約

  • 1≦H≦30
  • 1≦W≦30
  • (H,W)≠(1,1)
  • 0≦Ai,j≦10000 (1≦iH,1≦jW)
  • A1,1=0

入力

入力は以下の形式で標準入力から与えられる.

H W
A1,1  A1,W
:
AH,1  AH,W

出力

条件を満たすように木を伐採するのにかかる時間の最小値を 1 行で出力せよ.

小課題 1 [15点]

  • 1≦H≦5
  • 1≦W≦5

小課題 2 [28点]

  • Ai,jAi,j+1 (1≦iH,1≦jW−1)
  • Ai,jAi+1,j (1≦iH−1,1≦jW)

小課題 3 [57点]

  • 追加の制限はない.

入力例 1

Copy
2 3
0 1 2
3 4 5

出力例 1

Copy
32

北から i マス目,西から j マス目の領域を (i,j) で表す.

まず (1,2) の木を伐採する.これには 1 分かかる.

次に (1,3) の木をすべて伐採する.1 本伐採するのに,(1,1) から東に 1 マス進み,(1,3) の木を伐採し,西に 1 マス進んで (1,1) に戻ればいいので,3 分かかる.よってこれには 2×3=6 分かかる.

次に (2,3) の木をすべて伐採する.1 本伐採するのに,(1,1) から東に 2 マス進み,(2,3) の木を伐採し,西に 2 マス進んで (1,1) に戻ればいいので, 5 分かかる.よってこれには 5×5=25 分かかる.

全部で 1+6+25=32 分かかる.これより少ない時間で,条件を満たすように木を伐採することはできないので,32 を出力する.


入力例 2

Copy
2 5
0 5 0 0 0
0 0 0 9 1

出力例 2

Copy
13

(2,5) の木のみを伐採すればよい.


入力例 3

Copy
2 5
0 2 0 0 0
0 0 0 9 1

出力例 3

Copy
11

まず,(1,2) の木を伐採して,次に (2,5) の木を伐採すればよい.

2buttonsのeiya解

https://hoj.hamako-ths.ed.jp/onlinejudge/contest/121/problems/5
提出しても見られないみたいなのではるだけはっておきます。

ところで通常問題の方のURLをはりたかったのですが、なんかidがずれるみたいなのではりません。
現時点(2017/12/2)ではidは869です。

部分点(20点)

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;

int32_t H,W;
int32_t ah,aw,bh,bw;
int32_t map[1000][1000];
int32_t distA(int32_t h, int32_t w) { return std::abs(h - ah) + std::abs(w - aw); }
int32_t distB(int32_t h, int32_t w) { return std::abs(h - bh) + std::abs(w - bw); }

int64_t func(int32_t i, int32_t j, bool myturn)//Aがtrue、先行がtrue
{
	bool finish = true;
	for (int32_t h = 0; h < H; h++)
		for (int32_t w = 0; w < W; w++)
	{
		if (distA(h, w) >= i && distB(h, w) >= j) {
			finish = false;
		}
	}
	if (finish) {
		return 0;
	}

	auto pattA = func(i + 1, j, !myturn);
	if(myturn)
		for (int32_t h = 0; h < H; h++)
			for (int32_t w = 0; w < W; w++)
	{
		if (distA(h, w) == i && distB(h, w) >= j) {
			pattA += map[h][w];
		}
	}

	auto pattB = func(i, j + 1, !myturn);
	if (myturn)
		for (int32_t h = 0; h < H; h++)
			for (int32_t w = 0; w < W; w++)
	{
		if (distA(h, w) >= i && distB(h, w) == j) {
			pattB += map[h][w];
		}
	}

	if (myturn == (pattA>pattB)) {
		return pattA;
	}
	else {
		return pattB;
	}
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> H>>W;
	in >> ah >> aw >> bh >> bw; --ah; --aw; --bh; --bw;
	for (int32_t h = 0; h < H; ++h) for (int32_t w = 0; w < W; ++w) {
		in >> map[h][w];
	}

	out << func(0, 0, true) << endl;;

	return 0;
}
#endif

満点

#include <iostream>
#include <cstdint>
#include <algorithm>


int32_t H, W;
int32_t ah, aw;
int32_t bh, bw;
int32_t map[1000][1000];

const int32_t DIST_MAX = 2000;
int64_t scoreA[DIST_MAX+2][DIST_MAX+2];//自分、相手
int64_t scoreB[DIST_MAX+2][DIST_MAX+2];//自分、相手

const int64_t INF = 100010002000000000;
int64_t dp[DIST_MAX + 2][DIST_MAX + 2];
int64_t func(int32_t a, int32_t b)
{
	if (a == DIST_MAX+1 && b == DIST_MAX+1)
	{
		return 0;
	}
	if (a > DIST_MAX+1 || b > DIST_MAX+1) {
		return INF;
	}
	if (dp[a][b] != INF) { return dp[a][b]; }
	return dp[a][b] = std::max(
		-func(a + 1, b) + scoreA[a][b],
		-func(a, b + 1) + scoreB[b][a]
	);
}

int main()
{
	using std::cin;
	using std::cout;
	using std::endl;
	for (auto& arr : dp)for (auto& i : arr) { i = INF; }
	cin >> H >> W;
	for (int32_t h = 0; h < H; ++h) for (int32_t w = 0; w < W; ++w) {
		cin >> map[h][w];
	}
	cin >> ah >> aw >> bh >> bw; --ah; --aw; --bh; --bw;

	int64_t sum = 0;
	for (int32_t h = 0; h < H; ++h) for (int32_t w = 0; w < W; ++w) {
		int32_t dist_a = std::abs(h - ah) + std::abs(w - aw);
		int32_t dist_b = std::abs(h - bh) + std::abs(w - bw);
		scoreA[dist_a][dist_b] += map[h][w];
		scoreB[dist_b][dist_a] += map[h][w];
		sum += map[h][w];
	}
	for (int32_t distme = 0; distme <= DIST_MAX; ++distme) {
		for (int32_t distopp = DIST_MAX-1; distopp >= 0; --distopp) {
			scoreA[distme][distopp] += scoreA[distme][distopp + 1];
			scoreB[distme][distopp] += scoreB[distme][distopp + 1];
		}
	}

	cout << (func(0, 0)+ sum)/2 << endl;
}

F - Three Gluttons(CODE FESTIVAL 2017 qual C)

この問題です。
F - Three Gluttons


というわけで解説と考察の道筋を書きます。

実際にした考察

「AとBの残っている寿司」と「あと何個食べるか」を引数にDPが出来そう

  • 「状態」が2^Nになるなぁ...。状態をNで表せるとO(N^3)で解けそう。
  • でも表せたとしてDPの遷移を思いつかないな...

...色々試します...
始めは必ず取らないといけないとか、最後二つは絶対に取れないとか考えましたが、そこから派生出来ない...
(真隣に依存する操作が無い為、端が決まっても嬉しくないなぁ...)

そのうち「逆順をやってみるか」と思います。
逆順で状態をNで表せるように頑張ります。
...そもそもこの問題の場合の逆順ってなんだ???(しばらく混乱)
(ちなみに考察中は逆順に「食べる」という用語で考察したんですが、書いてみたら紛らわしかったので「吐き出す」と書いておきます)

  1. けんかしないで最後まで取る=>0個のこる
  2. そこから一個取る前の状態に戻す
  3. ああ、後ろ二つは絶対に取れないんだっけ。後ろから三つ目に吐き出すか?
  4. なんで後ろから三つ目でないといけないんだ??<=ここ詰めよう
  5. DPみたいにしたいので、今吐き出したものの順位をa,b(0<=a,b<N)と置くか

Aさんが一個目にxを吐き出すとき、他の人はxを食べられないので、Bさんがxをb以上の順位にしていると困るな...
(補足:Bさんがxをbよりも上の順位にしている場合、xもB[b]も残っている状況ではBさんはxを取りたいのでけんかが起こります)
=>逆に言えば、Aさんが吐き出せるのはBさんにとってbよりも下の順位のものだけだな???
ということは...
Aにとってaより上の順位のもの:必ず吐き出すことが可能、下の順位のもの:後からは絶対に吐き出せない
(補足:a<jについてAさんはA[j]よりもA[a]を先に食べる<=>A[j]よりもA[a]を後に吐き出す)
Bも同じ
=>これなら「AとBの残っている(吐き出せる寿司)寿司」をa,bという境界を持ってやることでN^2通りで表せる!
=>よしO(N^3)DP出来た!!!

...これは罠で、DPの状態(引数)は決めることが出来ましたが、まだ遷移が出来ていません。
考えます。

吐き出せるやつを全部試すとN^2かかって間に合わないし...
...思いつかないですね。

仕方がないので「吐き出せるやつを全部試す」の方針をもう一度考えます。
...そういえばこれって、前の方のやつを全部足す形だな...
=>累積和が使えるパターンでは!??(ここは一般的なテクとして知識を持っておかないと辛い)

こういう問題の場合、僕はコードを実際に書いて、それを無理やり整形して解くことが多いので、出来そうという方針が立ったこの段階でコードを書き始めます。

DPの説明

後半にコードが書いてあるので、そちらと見比べながら見てください。

DPの定義式を考えます。
本番中僕は言語化せずに感覚的にやってしまったのですが、頑張って言語化します。

DP[a][b][taberu]を

  • 「Aはa、Bはbを直前に吐き出した」つまり「Aはaより好きなものを、Bはbより好きなものを吐き出すことが出来る」
  • 「A,B,Cはあとtaberu個吐き出す」

の条件を満たすようにCを作ったとき、作れるCの通り数
とします。
A,Bの先頭を吐き出すまでCの構成を続けるので、完成した場合であるa=0,b=0のときCの通り数は1です。
つまり
DP[0][0][0] = 1
です。

例えば、
入力例 3

6
1 2 3 4 5 6
2 1 4 3 6 5

の時は
DP[2][2][1]=20
みたいになります。
a,b,は0-indexed、taberuは個数(0個1個2個...N個)であることに注意してください。
(計算方法は後述)


「次にA,Bが吐き出すものの順位」をnext_a,next_bとします。(これは二重ループで決め打ちします)
A[i],B[i]を問題文通りに、i番目に好きな寿司とします。(コードでは0-indexed)
Aがxが何番目に好きかをN_EATED_A[x]、Bがxが何番目に好きかをN_EATED_B[x]とします。(変数の命名は突っ込まない約束です)
AがA[next_a]を吐き出す為には、BがB[next_b]よりもA[next_a]が嫌いである、つまりnext_b < N_EATED_B[A[next_a]]である必要があります。
同様にBがB[next_b]を吐き出す為にはnext_a < N_EATED_A[B[next_b]]である必要があります。
これを満たしているとき、AはA[next_a]、BはB[next_b]を吐き出します。
この時のCの通り数を計算します。

Cは自由に決められるので、吐き出すごとに生まれる制約を使ってCを少しずつ決めてやるイメージでやります。

Cが吐き出すものをA,Bと同じようにC[next_c]と仮置きします。あとN_EATED_C[x]も同じように仮置きします。
まず、A,Bの時と同じ理由で、next_c < N_EATED_C[A[next_a]] かつ next_c < N_EATED_C[B[next_b]]である必要が有ります。
なので、next_cの前にA[next_a]とB[next_b]を好きな順番で入れます。
また、これまたA,Bのときと同じ理由で、next_a < N_EATED_A[C[next_c]] かつnext_b < N_EATED_B[C[next_c]]である必要が有ります。
これを満たす為に、C[next_c]は上の条件を満たす寿司から一つ選んで吐き出します。
f:id:eiya5498513:20171023103858j:plain
この通り数が、コードの

*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next]- tabeta*3)

に相当します。
tabetaは「今までに吐き出した数」です。(コードは本番のものなので、「吐き出す」が「食べる」になっています)
始め二つが、「A[next_a]とB[next_b]を好きな順番で入れる」の通り数です。Cの中で順番が確定しているのは「今までにA,B,Cが吐き出した総数」個です。そこに好きな順番でA[next_a]とB[next_b]を入れるのでこうなります。
最後は、C[next_c]の選び方の通り数です。C_tori[a_next][b_next]は「next_a < N_EATED_A[x] かつnext_b < N_EATED_B[x]」を満たすxの数です。このうち、「今までにA,B,Cが吐き出した総数」個は既に吐き出されているので、Cが新たに吐き出せるのは(C_tori[a_next][b_next]- tabeta*3)個です。

a_next,b_nextが決まっているときの遷移は、Cを適当に決める=>次の状態に移るという動作をし、これがCの構成の一つのパターンです。
これで遷移を書くと↓のようになります。(言語での説明ができなかった人の顔)

mint res = 0;
int32_t tabeta = eat_all - taberu;
for (int32_t a_next = a-1; a_next >= 0; --a_next)
for (int32_t b_next = b-1; b_next >= 0; --b_next)
{
	//↓つまり、「AがA[a_next],BがB[b_next]を食べる」というのが可能ならば
	if (b_next &lt; N_EATED_B[A[a_next]] && a_next &lt; N_EATED_A[B[b_next]] && (C_tori[a_next][b_next] > tabeta*3)) {
		//Cを適当に決める=>次の状態に移るという動作をするので
		//通り数を数えるDPと同じようにしてやった後、Cの選び方をかける
		res += func(a_next, b_next, taberu - 1)*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next]- tabeta*3);
	}
}

↓考察ノート(本番に実際使ったもの)
f:id:eiya5498513:20171023000702j:plain

↓この段階でのコード(メモ化していないので、O(N^5)よりもさらに遅いです)
本番で使ったコードのバグを少し直しただけなので、「吐き出す」が「食べる」になっています。
mintの定義は省略してありますが、要はmodを勝手にとるintです。詳しくはこちら:C++14用mod_int - 永夜の記録

int32_t eat_all;
int32_t N_EATED_A[400];
int32_t N_EATED_B[400];
int32_t C_tori[400][400];//a,b
int32_t N;
int32_t A[400];
int32_t B[400];
mint func(int a, int b, int taberu)
{
	if (a == 0 || b == 0) {
		if (a == 0 && b == 0 && taberu == 0) {
			return 1_mi;
		}
		else {
			return 0_mi;
		}
	}
	if (taberu == 0) {
		assert(false);
		return 0_mi;
	}

	mint res = 0;
	int32_t tabeta = eat_all - taberu;
	for (int32_t a_next = a-1; a_next >= 0; --a_next)
	for (int32_t b_next = b-1; b_next >= 0; --b_next)
	{
		if (b_next < N_EATED_B[A[a_next]] && a_next < N_EATED_A[B[b_next]] && (C_tori[a_next][b_next] > tabeta*3)) {
			res += func(a_next, b_next, taberu - 1)*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next]- tabeta*3);
		}
	}
	return func3(a, b, taberu);
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N; eat_all = N / 3;
	for (int32_t i = 0; i < N; i++)
	{
		in >> A[i]; --A[i];
		N_EATED_A[A[i]] = i;
	}
	for (int32_t i = 0; i < N; i++)
	{
		in >> B[i]; --B[i];
		N_EATED_B[B[i]] = i;
	}


	for (int32_t a = N - 1; a >= 0; --a)
		for (int32_t b = N - 1; b >= 0; --b)
		{
			if (b == N - 1) {
				C_tori[a][b] = 0;
			}
			else {
				C_tori[a][b] = C_tori[a][b + 1];
				//B[b+1]が使えるようになる
				if (a < N_EATED_A[B[b + 1]]) {
					++C_tori[a][b];
				}
			}
			//for (int32_t i = 0; i < N; i++)
			//{
			//	if(a<N_EATED_A[i] && b<N_EATED_B[i])
			//		++C_tori[a][b];
			//}
		}

//Nよりも順位が良い全てのもの、つまり全ての寿司を吐き出せます

	out << func(N, N, eat_all) << endl;

	return 0;
}

オーダーを減らす

この段階で、O(N^5)の解法が出来たので、オーダーを減らします。
先ほども書きましたが、

for (int32_t a_next = a-1; a_next >= 0; --a_next)
for (int32_t b_next = b-1; b_next >= 0; --b_next)
{
	if (b_next < N_EATED_B[A[a_next]] && a_next < N_EATED_A[B[b_next]] && (C_tori[a_next][b_next] > tabeta*3)) {
		res += func(a_next, b_next, taberu - 1)*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next]- tabeta*3);
	}
}

が累積和っぽいテクを使うことで減らせます。(ここは発想ではなく知識です)
ここでeiya流雑なDPを使ってまずbのループを消していきます。

for (int32_t a_next = a-1; a_next >= 0; --a_next)
	res += func2(a_next,b,taberu);

になるようにfunc2を書きます。
とりあえずコピペしてメモ化します。

bool DP2_u[400][400][400];
mint DP2[400][400][400];
mint func2(int32_t a_next, int32_t b, int32_t taberu)
{
	if (DP2_u[a_next][b][taberu]) {
		return DP2[a_next][b][taberu];
	}
	DP2_u[a_next][b][taberu] = true;

	mint res = 0;
	int32_t tabeta = eat_all - taberu;
 
	for (int32_t b_next = b-1; b_next >= 0; --b_next)
	{
		if (b_next < N_EATED_B[A[a_next]] && a_next < N_EATED_A[B[b_next]] && (C_tori[a_next][b_next] > tabeta*3)) {
			res += func(a_next, b_next, taberu - 1)*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next]- tabeta*3);
		}
	}
	return DP2[a_next][b][taberu] = res;
}

func2は[0,b)の

if (b_next < N_EATED_B[A[a_next]] && a_next < N_EATED_A[B[b_next]] && (C_tori[a_next][b_next] > tabeta*3)) {
	res += func(a_next, b_next, taberu - 1)*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next]- tabeta*3);
}

の和なので、こうします。

bool DP2_u[400][400][400];
mint DP2[400][400][400];
mint func2(int32_t a_next, int32_t b, int32_t taberu)
{
	if(b==0){return 0_mi;}//0_miはmint(0)と同じ意味です。
	if (DP2_u[a_next][b][taberu]) {
		return DP2[a_next][b][taberu];
	}
	DP2_u[a_next][b][taberu] = true;

	mint res = 0;
	int32_t tabeta = eat_all - taberu;
 	
 	//b_next==b-1の処理
	int b_next = b-1;
 	if (b_next < N_EATED_B[A[a_next]] && a_next < N_EATED_A[B[b_next]] && (C_tori[a_next][b_next] > tabeta*3)) {
		res += func(a_next, b_next, taberu - 1)*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next]- tabeta*3);
	}
	//b_nextが[0,b-1)の処理
	res += func2(a_next, b-1, taberu);
	return DP2[a_next][b][taberu] = res;
}

これでfunc2の一回当たりの実行時間はO(1)になりました。

なのでfuncの

for (int32_t a_next = a-1; a_next >= 0; --a_next)
	res += func2(a_next,b,taberu);

はこの時点でO(N)です。

同じようにfuncのaのループも消すとこうなります。
実際に書いたコードはこっち:
Submission #1705609 - CODE FESTIVAL 2017 qual C

int32_t eat_all;
int32_t N_EATED_A[400];
int32_t N_EATED_B[400];
int32_t C_tori[400][400];//a,b
int32_t N;
int32_t A[400];
int32_t B[400];
mint func(int a, int b, int taberu);

bool DP2_u[400][400][400];
mint DP2[400][400][400];
mint func2(int32_t a_next, int32_t b, int32_t taberu)
{
	if (b == 0) { return 0_mi; }//0_miはmint(0)と同じ意味です。
	if (DP2_u[a_next][b][taberu]) {
		return DP2[a_next][b][taberu];
	}
	DP2_u[a_next][b][taberu] = true;

	mint res = 0;
	int32_t tabeta = eat_all - taberu;

	//b_next==b-1の処理
	int b_next = b - 1;
	if (b_next < N_EATED_B[A[a_next]] && a_next < N_EATED_A[B[b_next]] && (C_tori[a_next][b_next] > tabeta * 3)) {
		res += func(a_next, b_next, taberu - 1)*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next] - tabeta * 3);
	}
	//b_nextが[0,b-1)の処理
	res += func2(a_next, b - 1, taberu);
	return DP2[a_next][b][taberu] = res;
}

bool DP3_u[400][400][400];
mint DP3[400][400][400];
mint func(int a, int b, int taberu)
{
	if (a == 0 || b == 0) {
		if (a == 0 && b == 0 && taberu == 0) {
			return 1_mi;
		}
		else {
			return 0_mi;
		}
	}
	if (taberu == 0) {
		return 0_mi;
	}

	if (DP3_u[a][b][taberu]) {
		return DP3[a][b][taberu];
	}
	DP3_u[a][b][taberu] = true;

	auto a_next = a - 1;
	DP3[a][b][taberu] += func2(a_next, b, taberu);
	DP3[a][b][taberu] += func(a - 1, b, taberu);
	return DP3[a][b][taberu];
}

int main() {
//先ほどと同じなので省略
}

この時点でO(N^3)で、MLEです。

メモリ節約

DPのメモリを節約する一般的なテク、DP配列の使いまわしをします。(ここも知識)

DPが二つに分かれているので分かりにくいですが、再帰の起点であるfuncから処理を追っていくと、
taberu==tのときの更新の際、直接呼び出しているのは(つまり、漸化式に入っているのは)

  • a,bがより低くtaberu==tのfunc又はfunc2
  • taberu==t-1のfunc又はfunc2

のみであることが分かります。
よって、taberuを0~Nまで増やしていく方向にforDPをすると、taberuを節約できることが分かります。
この方針で再帰をforDPに書き直すとMLEを解決出来て、ACできます。

実際に書いたコード:Submission #1705841 - CODE FESTIVAL 2017 qual C
解説用に書き直したコード:Submission #1707527 - CODE FESTIVAL 2017 qual C

解いた経緯


(注:9時から19時まで模試でした)

旧AtCoderからbetaAtCoderに移るスクリプト(未完)

AtCoderからbetaAtCoderに移るtampermonkey用スクリプトです。
上の方に変なのが見えるようになります。
使えればよし精神を大事にしていこうな(逃げ)
僕にはこれが限界なので、もっと良いのを誰か作って。

追記>Luzhiledさんが作ってくれた。ありがとうございます。
Luzhiled's page


↓僕の (Luzhiledさんのを使うのがおススメですが、一応残しておきます)

// ==UserScript==
// @name         old atcoder to new atcoder
// @namespace    https://twitter.com/eiya5498513
// @version      1.0
// @description  ja
// @author       eiya
// @match        http://*.contest.atcoder.jp/*
// @match        https://*.contest.atcoder.jp/*
// @grant        none
// ==/UserScript==

(function() {
  'use strict';
  const url = location.href.replace(/\/&/, "");
  const contest_name = url.replace(/^https?:\/\//,'').split('.')[0];
  const end_name = url.replace(/^https?:\/\/.+\.contest\.atcoder\.jp\/?/,'');
  const beta_url = "https://beta.atcoder.jp/contests/"+contest_name + "\/" + end_name;
  const style = /font-family:Helvetica Neue, Helvetica, Arial,sans-serif;font-size:200%;/;
  const beta_html_text = "<div style=\"" + style + "\"><a href=\""+ beta_url + "\">beta版</a></div>";

  $('div.container').append(beta_html_text);
})();

動作図
f:id:eiya5498513:20171019231501j:plain

最古の遺跡解説

この問題です

ジャッジ:C - 最古の遺跡
問題:https://www.ioi-jp.org/joi/2006/2007-ho-prob_and_sol/2007-ho.pdf

オーダー的にO(N3)が辛くてO(N2)が通るので、O(N2)を考えます。 二点を固定して、残りの二頂点C,Dに点があるかを判定すれば良いです。
f:id:eiya5498513:20171008203034j:plain

まずは、C1,D1に頂点があるかを確認します。
この後はC1,D1をただC,Dと呼びます。

ここで予めある座標に頂点があるかどうかをbool配列でもっておくと、あとはC1,D1の座標を求めるだけであるなしが判定できます。

なんとなく正方形ABCDを回転していない正方形で囲ってみます。(なぜこの発想になるのかの説明は余裕があったら追記します...)
f:id:eiya5498513:20171008203947j:plain

x = Bx - Ax、y = By - Ayとなるようにx,yを取ります。そうするとx,yは上図のようになります。
ここで、三角形ABO1≡三角形CAO2なので、CO2==x、O2A==yです。
f:id:eiya5498513:20171008204448j:plain

よって、Cx = Ax - y、Cy = Ay + xで求められることが分かります。
又、DはDx = Cx + x、Dy = Cy + yで求まります。

この図はA->Bが右上がりの時の図なので、A->Bが右下がりの時どうなるか考えてみます。

どんどんBを下げていくと、こうなります。
f:id:eiya5498513:20171008205141j:plain
この時は三角形が作れないですが、無理やりy==0と考えてやると、上手く行くことが分かります。

Bをもっと下げてみます。
f:id:eiya5498513:20171008205336j:plain
図の形が変わりました。
xとyをそのまま負数に拡張してやると、図のようになり、式を変えずにそのまま計算することが出来ます。

xが負の時も同じように考えると、式を全く変形せずにCx = Ax - y、Cy = Ay + x、Dx = Cx + x、Dy = Cy + yの式で良いことが分かります。

次にC2,D2について考えます。
Aを中心にxとyを反転させる(Aを中心に紙を180度回す)と図のようになります。 回転後のBをA'、回転後のAをB'と考えると、C1',D1'がそれぞれC2,D2に対応します。
よって、「AとBを入れ替えてもう一度C1,D1を求める処理をする」とC2,D2の座標を求めることが出来ます。

ここで、C2,D2を求めるときに行っているのはAとBを交換する作業であることから、AとBの選び方をいつものように組み合わせを考えるときの以下のfor分

for(int a=0;a < N;++a)for(int b = a+1;b < N;++b)

を使うと思いますが、今回は

for(int a=0;a < N;++a)for(int b = 0;b < N;++b){
if(a==b){continue;}
//処理
}

とa,bの順番も考慮してやることで、C1,D1の座標を求めるコードのみにしてやることが出来ます。

ところで、a==bの時は何が起こるのでしょう。
この時は同じ頂点二つを使って正方形を作ろうとし、その4頂点は全て同じ座標に存在するので、正方形が作れてしまいます。
しかし実際は4頂点を選んで正方形を作らないといけないので、作ってはいけない正方形を作ってしまいます。これは弾く必要が有ります。
しかしよく考えると、この時正方形の面積は0、つまり正方形の最小の面積1よりも小さいので、実は「正方形が存在する場合は」弾いてやらなくても面積のmaxを取る段階で弾くことが出来ます。
逆に面積のmaxが0のときは正方形が一つも存在しないということなので、例外処理である0を出力する必要が有ります。
が、値が0の時に0を出力するという処理になっているので、結局そのまま出力すれば良いことが分かります。

この方針でコードを実装してやるとこうなります。短く書けるのでバグを埋め込みにくくなります。
Submission #1671065 - 第6回日本情報オリンピック 本選(オンライン)