Blur(AOJ No. 0091), Calculation of Area(AOJ No. 0094), Surf Smelt Fishing Contest(AOJ No. 0095), Sum of 4 Integers II(AOJ No. 0096), Sum of Integers II(AOJ No. 0097), Maximum Sum Sequence II(AOJ No. 0098), Surf Smelt Fishing Contest II(AOJ No. 0099)

https://github.com/kanetai/JAVA
https://github.com/kanetai/CPP
以前、
Now judge is temporally not available for this problem. We are earnestly making necessary data. Sorry for the inconvenience.
になってたやつが、ジャッジできるようになってたので、解いた。

Blur(AOJ No.0091)

10x10の布が与えられる。真っ白(all 0)の状態から、大中小のいずれかの染料を使って、与えられた布の状態にする。
各染料を使うとその周囲の区画の値が+1される。布の端に使って染料がはみ出るような使い方はしない。
使用した染料の回数xが与えられたとき、与えられた布の状態にする操作(染料を使うx座標,y座標,染料の大きさの系列)を求める。

□■□　■■■　
■■■　■■■　
□■□　■■■　　
　小　　　中　　　

□□■□□
□■■■□
■■■■■
□■■■□
□□■□□
　　大

制約
$0 < x \leq 12$
出力する操作の順序は自由、実現可能な入力が与えられる。

アルゴリズム

染料の種類数size=3, 布の広さ HxW=10x10とすると、全探索した場合、
$(size\times H\times W)^{x} = 300^{12} = 5.31441\times 10^{29}$
なので、ムズそうだが、上手く枝刈りするだけで通った。
与えられた布から真っ白な状態にするほうこうで深さ優先にした。
染料を使った位置は、現在の布を右上から順に見て、一番始めに見つけた白でない区画(x,y)に基づいて決める。
色の付いた状態から、白の状態に戻すように考えているので、この(x,y)の濃度を下げるように決める。
(x,y)の濃度を下げるには、大の場合.(x,y+2), 中の場合(x+1,y+1), 小の場合(x, y+1)を中心として、サイズに対応した範囲の濃度を下げる(区画の値をデクリメントする)。
(x,y)より上または、左の区画は、既に白なので、この３つだけ考えればいい。
はみ出したりして、どのサイズを使っても濃度を下げられないなら、(x,y)の区画を白にすることができないので、バックトラックする。また、各区画の濃度の総和を計数しておき、大の場合は13, 中の場合は9, 小の場合は5より小さければ、これ以上調べるまでもなく実現不可能と分かるので、バックトラックできる。

コード

ムズそうだったので、先にC++で解いたが、はみ出さないように染料を使用するという記述を見落としてただけで、思ったより簡単だった。C++11が使えたので、使ってみた。
ラムダ式使ってるところは、単にbreakで２重ループを抜けるためにフラグを用意するのが面倒だったから。
goto使った方がましかもしれませんが...
拡張for文が使えるようになったので、だいぶ楽になりましたが、indexを使いたいときがあるのでやっぱ#define REP使っちゃう。
vectorの{}初期化は使いやすいネ。
C++版は00.00 s、Java版は00.05 s。

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <cassert>
#include <sstream>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)n;++i)
typedef pair<int,int> Point;
const int N = 10, M = 12;
int blur[N][N], COUNT, TOTAL, total;
enum Size{ LARGE, MID, SMALL, N_SIZE };
vector<Point> delta[] = { //dx,dy
    vector<Point> {
        Point(0,0), Point(-1,0), Point(0,-1), Point(1,0), Point(0,1),
        Point(-1,-1), Point(1,-1), Point(1,1), Point(-1,1),
        Point(-2,0), Point(0,-2), Point(2,0), Point(0,2)
    }, vector<Point> {
        Point(0,0), Point(-1,0), Point(0,-1), Point(1,0), Point(0,1),
        Point(-1,-1), Point(1,-1), Point(1,1), Point(-1,1)
    }, vector<Point>{
        Point(0,0), Point(-1,0), Point(0,-1), Point(1,0), Point(0,1)
    },
};
int minimul_count[]={13, 9, 5};
Point target[]{ Point(0,2), Point(1,1), Point(0,1) };
struct Data {
    int x, y, size;
    Data(){}
    Data(int x, int y, int size): x(x), y(y), size(size){}
    string description() const {
        ostringstream oss;
        oss << x << " " << y << " " << N_SIZE-size;
        return oss.str();
    }
};
Data history[M];
inline bool canSub(const Data &data){
    for(const Point &d: delta[data.size]){
        Data p(data.x+d.first, data.y+d.second, data.size);
        if(!(0 <= p.x && p.y < N && 0 <= p.x && p.x < N && blur[p.y][p.x] != 0)) return false;
    }
    return true;
}
inline void add(const Data &d){
    for(const Point &p: delta[d.size]){ ++blur[d.y+p.second][d.x+p.first]; ++total;}
}
inline void sub(const Data &d){
    for(const Point &p: delta[d.size]){ --blur[d.y+p.second][d.x+p.first]; --total;}
}
bool solve(const Data &b, int d){
    if(d == COUNT && total == 0) return true;
    Point p(-1,-1);
    [&](){ REP(y,N) REP(x,N) if(blur[y][x] > 0){ p.first = x; p.second = y; return; } }();
    if(p.first < N-1 && p.second < N-1 && p.first != -1){
        REP(size,N_SIZE){
            if(minimul_count[size] > total) continue;
            Data data = Data(p.first + target[size].first, p.second + target[size].second, size);
            if(canSub(data)){
                sub(data);
                history[d] = data;
                if(solve(data, d+1)) return true;
            }
        }
    }
    add(b);
    return false;
}
int main(){
    cin >> COUNT;
    REP(i,N) REP(j,N){ cin >> blur[i][j]; TOTAL += blur[i][j]; }
    total = TOTAL;
    assert(solve(Data(),0));
    REP(i,COUNT) cout << history[i].description() << endl;
}

import java.util.*;
import java.awt.Point;
public class aoj0091 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 10, M = 12, N_SIZE = 3, blur[][] = new int[N][N], minimul_count[]={13, 9, 5};
	static final Data[] history = new Data[M];
	static int COUNT, TOTAL, total;
	public static void main(String[] args) {
		COUNT = stdin.nextInt();
		for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
			blur[i][j] = stdin.nextInt(); TOTAL += blur[i][j];
		}
		total = TOTAL;
		solve(new Data(),0);
		for(int i = 0; i < COUNT; ++i) System.out.println(history[i].toString());
	}
	static final Point delta[][] = {
		{
			new Point(0,0), new Point(-1,0), new Point(0,-1), new Point(1,0), new Point(0,1),
			new Point(-1,-1), new Point(1,-1), new Point(1,1), new Point(-1,1),
			new Point(-2,0), new Point(0,-2), new Point(2,0), new Point(0,2)
		}, {
			new Point(0,0), new Point(-1,0), new Point(0,-1), new Point(1,0), new Point(0,1),
			new Point(-1,-1), new Point(1,-1), new Point(1,1), new Point(-1,1)
		}, {
			new Point(0,0), new Point(-1,0), new Point(0,-1), new Point(1,0), new Point(0,1)
		}
	};
	static final Point target[]={ new Point(0,2), new Point(1,1), new Point(0,1) };
	static class Data {
		int x, y, size;
		Data(){}
		Data(int x, int y, int size){ this.x = x; this.y = y; this.size = size; }
		@Override public String toString(){ return x+" "+y+" "+(N_SIZE-size); }
	};
	static final boolean canSub(Data data){
		for(Point d: delta[data.size]){
			Data p = new Data(data.x+d.x, data.y+d.y, data.size);
			if(!(0 <= p.x && p.y < N && 0 <= p.x && p.x < N && blur[p.y][p.x] != 0)) return false;
		}
		return true;
	}
	static final void add(Data d){
		for(Point p: delta[d.size]){ ++blur[d.y+p.y][d.x+p.x]; ++total;}
	}
	static final void sub(Data d){
		for(Point p: delta[d.size]){ --blur[d.y+p.y][d.x+p.x]; --total;}
	}
	static final boolean solve(Data b, int d){
		if(d == COUNT && total == 0) return true;
		Point p = new Point(-1,-1);
		LOOP: for(int y = 0; y < N; ++y)
			for(int x = 0; x < N; ++x)
				if(blur[y][x] > 0){ p.x = x; p.y = y; break LOOP; }
		if(p.x < N-1 && p.y < N-1 && p.x != -1){
			for(int size = 0; size < N_SIZE; ++size){
				if(minimul_count[size] > total) continue;
				Data data = new Data(p.x + target[size].x, p.y + target[size].y, size);
				if(canSub(data)){
					sub(data);
					history[d] = data;
					if(solve(data, d+1)) return true;
				}
			}
		}
		add(b);
		return false;
	}
}

Calculation of Area(AOJ No.0094)

要するにSystem.out.println(stdin.nextInt()*stdin.nextInt()/3.305785);

import java.util.*;
public class aoj0094 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		System.out.println(stdin.nextInt()*stdin.nextInt()/3.305785);
	}
}

Surf Smelt Fishing Contest(AOJ No. 0095)

a,bの系列が与えられて、bの最も大きいレコードを答える。最大のbが複数あった場合は、aが小さい方を答える。各レコードのaは互いに異なる。

import java.util.*;
public class aoj0095 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int n = stdin.nextInt();
		List<int[]> l = new ArrayList<int[]>(n);
		while(n-->0) l.add(new int[]{stdin.nextInt(), stdin.nextInt()});
		Collections.sort(l, new Comparator<int[]>(){
			@Override public int compare(int[] o1, int[] o2) { return o1[1]!=o2[1] ? o2[1]-o1[1] : o1[0]-o2[0]; }
		});
		System.out.println(l.get(0)[0]+" "+l.get(0)[1]);
	}
}

Sum of 4 Integers II(AOJ No. 0096)

nが与えられたとき、a+b+c+d=nとなるa,b,c,dの組み合わせ数を答える。
制約
$0 < n < 4,000$
$0 \leq a.b.c.d \leq 1,000$

アルゴリズム

半分全列挙戦法で、a+bで1〜nを作る場合の組み合わせ数 $AB(n)$ を求めておく。それをつかって、n = 0〜4,000としたときの、組み合わせ数を求める。a+bとnが決まれば, c+dは自動的に決まるので $LUT(n) = \sum_{c+d=0}^{2,000} AB(n-(c+d))AB(c+d)$

コード

import java.util.*;
public class aoj0096 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 4000, M = 1000, AB[] = new int[N+1], LUT[] = new int[N+1];
	public static void main(String[] args) {
		for(int a = 0; a <= M; ++a) for(int b = 0; b <= M; ++b) AB[a+b]++;
		for(int i = 0; i <= N; ++i)
			for(int cpd = 0; cpd <= M+M; ++cpd){
				int apb = i - cpd;
				if(0 <= apb && apb <= N && AB[apb]> 0 && AB[cpd] > 0){
					LUT[i] += (AB[apb]*AB[cpd]);
				}
			}
		while(stdin.hasNext()) System.out.println(LUT[stdin.nextInt()]);
	}
}

Sum of Integers II(AOJ No. 0097)

$n, s$ が与えられたとき、 $s = \sum_{i=1}^s x_i$ となる組み合わせ数を答える。ただし、 $0\leq x_i \leq 100$ の整数で互いに異なる数字を使う。
制約
$1\leq n \leq 9$
$1\leq s \leq 1,000$
組み合わせ数 $\leq 10^{10}$

アルゴリズム

互いに異なる数字を使うということなので、 $x_{i+1} > x_i$ として考える。
$DP_{i,j,k}:=$ [0,k]の中から互いに異なる整数をi個使って和をjにする組み合わせ数
とすると、
$DP_{0,0,0} = DP_{1,0,0} = 1$ で初期化、 $1\leq k \leq 100$ 、 $1\leq i \leq 9$ 、 $k\leq j\leq 1,000$ について、
$DP_{i,j,k}=DP_{i,j,k-1} + DP_{i-1,j-k,k-1}$ ([0,k]の異なるi-1個の整数を使って和をj-kにし、kを加えて、和をjにする組み合わせ数を加算する)
答えは、 $DP_{n,s,9}$
ループの順序を考えれば、2次元配列で済む。
$DP_{i,j}:=$ 異なる整数i個を使って和をjにする組み合わせ数とし、kを一番外側のループで回す。
$DP_{0,0}=1$ で初期化し、 $9\geq i \geq 0$ , $k\leq j \leq 1,000$ について、
$DP_{i,j} += DP_{i,j-k}$ で更新。答えは、 $DP_{n,s}$
注意点は、iのループの順序。iを1〜9で回すと、同じkのループ内で更新した値を使うことになるので、0+0+0みたいなものもカウントしてしまう。逆順にすれば、更新前の値を使って、更新できるので問題ない。

コード

long使わないとWAだったと思う。

import java.util.*;
public class aoj0097 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 9, S = 1000, K = 100;
	static final long DP[][] = new long[N+1][S+1];
	public static void main(String[] args) {
		DP[0][0] = 1;
		for(int k = 0; k <= K; ++k)
			for(int i = N; i > 0; --i)
				for(int j = k; j <= S; ++j)
					DP[i][j] += DP[i-1][j-k];
		while(true){
			int n = stdin.nextInt(), s = stdin.nextInt();
			if((n|s) == 0) break;
			System.out.println(DP[n][s]);
		}
	}
}

Maximum Sum Sequence II(AOJ No. 0098)

nxn行列Aが与えられ、その部分行列の各要素の総和の最大値を求める。
制約
$1\leq n \leq 100$
$-10,000 \leq a_{i,j} \leq 10,000$

アルゴリズム

$S_{i,j} = \sum_{i'=1}^i \sum_{j'=1}^j a_{i',j'}$
とすれば、 $a_{i,j}$ を(k,l)要素とするkxl行列の各要素の総和 $M_{i,j,k,l}$ は、
$M_{i,j,k,l}=S_{i,j}+S_{i-k,j-l}-S_{i,j-l}-S_{i-l,j}$ で求まる。
$\max_{i,j,k,l}\{M_{i,j,k,l}\}$ が答え。
ただし、i=0 or j=0 なら $S_{i,j}=0$ 。 $O(n^4)\rightarrow 100^4 = 10^8$

コード

ans = -1で初期化しててWA食らった。

import java.util.*;
public class aoj0098 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int n = stdin.nextInt();
		int[][] M = new int[n+1][n+1];
		for(int i = 1; i <= n; ++i )
			for(int j = 1, s = 0; j <= n; ++j){
				s += stdin.nextInt();
				M[i][j] = s + (i >= 1 ? M[i-1][j] : 0);
			}
		int ans = Integer.MIN_VALUE;
		for(int k = 1; k <= n; ++k)
			for(int l = 1; l <= n; ++l)
				for(int i = k; i <= n; ++i)
					for(int j = l; j <= n; ++j)
							ans = Math.max(ans, M[i][j] + M[i-k][j-l] - M[i][j-l] - M[i-k][j]);
		System.out.println(ans);
	}
}

Surf Smelt Fishing Contest II(AOJ No. 0099)

ワカサギ釣りの参加者数n, イベント数qが与えられて、イベント系列 $(a_i, v_i)$ が与えられる。
$a_i, v_i$ はそれぞれ、 $i$ 番目のイベントで参加者(ID) $a_i$ のワカサギが $v_i$ 増える(負の数ならリリース)。
各イベントの後に、釣ったワカサギが最も多い人のIDと、ワカサギの数を求める。ただし、同順位の人が複数いれば、IDが最も小さい人のID, ワカサギの数を出力する。

コード

配列で、IDから現在釣っているワカサギの数を管理し、イベントで更新された物をpriorityQueueに入れ、１位のレコードを取り出す。
ただし、更新前のレコードがpriorityQueueに残っているので、配列の値と比較して、異なる場合はpopする。

import java.util.*;
public class aoj0099 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 1000000, A[] = new int[N+1];
	public static void main(String[] args) {
		stdin.nextInt();
		int q = stdin.nextInt();
		PriorityQueue<int[]> Q = new PriorityQueue<int[]>(N, new Comparator<int[]>(){
			@Override public int compare(int[] o1, int[] o2) {
				return o1[1] != o2[1] ? o2[1] - o1[1] : o1[0] - o2[0];
			}
		});
		while(q-- > 0){
			int a = stdin.nextInt(), v = stdin.nextInt();
			Q.add(new int[]{a,(A[a] += v)});
			while(A[Q.peek()[0]] != Q.peek()[1]) Q.poll();
			System.out.println(Q.peek()[0] + " " + Q.peek()[1]);
		}
	}
}

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Blur(AOJ No. 0091), Calculation of Area(AOJ No. 0094), Surf Smelt Fishing Contest(AOJ No. 0095), Sum of 4 Integers II(AOJ No. 0096), Sum of Integers II(AOJ No. 0097), Maximum Sum Sequence II(AOJ No. 0098), Surf Smelt Fishing Contest II(AOJ No. 0099)

Blur(AOJ No.0091)

アルゴリズム

コード

Calculation of Area(AOJ No.0094)

Surf Smelt Fishing Contest(AOJ No. 0095)

Sum of 4 Integers II(AOJ No. 0096)

アルゴリズム

コード

Sum of Integers II(AOJ No. 0097)

アルゴリズム

コード

Maximum Sum Sequence II(AOJ No. 0098)

アルゴリズム

コード

Surf Smelt Fishing Contest II(AOJ No. 0099)

コード