ARC12とZOJ

Contest ARC Java ZOJ C++

最近ようやくEclipseのテンプレート機能を有効活用し始めました。for文とか早く入力出来て便利ですねー。もっと早くScannerとPrintWriterをテンプレート化しておけば良かった。

AtCoder Regular Contest #012

http://arc012.contest.atcoder.jp/

A - 週末

英語の曜日が与えられる。週末（土曜、日曜）までの日数を求める問題。

書くだけ。スペルミスが怖くて1分くらい確認してました。

http://arc012.contest.atcoder.jp/submissions/69939

B - アキレスと亀

有名なアキレスと亀のパラドックス（http://ja.wikipedia.org/wiki/%E3%82%BC%E3%83%8E%E3%83%B3%E3%81%AE%E3%83%91%E3%83%A9%E3%83%89%E3%83%83%E3%82%AF%E3%82%B9）のシミュレーション。小学校の時にクイズを出すのが好きな先生がいて、その先生が出した最終問題がこれが正しくないことの証明でした（全く分からなかった）。

Bには珍しくこれも実装するだけ。

http://arc012.contest.atcoder.jp/submissions/70129


10分くらいでA, Bが終わったのにC, Dは全く分からず。

2問で順位は58位。なにげに過去最高順位な気がしますが、この辺りの順位は相当団子になっていました。あと5分遅かったら100位くらい。
再びARCのC問題が解ける日は来るのだろうか・・・。

Zhejiang University Online Judge

http://acm.zju.edu.cn/onlinejudge/

弾幕ゲーム東方プロジェクトの問題が出ているとのことで興味を惹かれて登録。何回か東方オンリーのコンテストが行われているので、問題セットを解き始めてみました。
http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=313
http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=328

何故かコンテストページからだとジャッジされない（？）みたいなので、Problem Setから問題名で検索してみた方がいいです。

3381. Osaisen Choudai!

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3381

日数n( < 50000)とそれぞれの日について、賽銭金額s、賽銭をもらってはいけない日数x、賽銭をもらわなければならない日数yが与えられたとき、霊夢が受け取る賽銭金額を最大化する問題。

なかなか上手い解法が浮かばなかったが、日数を後ろから構成し、i日目の賽銭金額をdp[i]とすると、
dp[i] = s[i] + max(i + dp[i + x[i]], ... , i + dp[i + y[i]])
とできる。
maxの部分はセグメント木で求める。セグメント木のサイズはnでなく、nを越える最初の2の冪乗であることに注意が必要。

参考 :
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
http://www.slideshare.net/iwiwi/ss-3578491

import java.io.PrintWriter;
import java.util.Scanner;

public class Q3381 {

	static int[] rmq;
	static int qn = 0;

	public static void main(String[] args) {
		doIt();
	}
	static void doIt() {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		while(sc.hasNext()){
			int n = sc.nextInt();
			int[] s = new int[n];
			int[] x = new int[n];
			int[] y = new int[n];
			qn = pow2(n);
			rmq = new int[qn*4];
			for (int i = 0; i < n; i++) {
				s[i] = sc.nextInt();
				x[i] = sc.nextInt();
				y[i] = sc.nextInt();
			}
			int[] dp = new int[n];
			for (int i = n - 1; 0 <= i; i--) {
				dp[i] = s[i] + get(i + x[i], i + y[i]);
				add(i, dp[i]);
			}
			pw.println(dp[0]);
		}
		pw.close();
	}

	static int get(int a, int b){
		return getMax(0, a, b, 0, qn);
	}
	static int getMax(int i, int a, int b, int l, int r){
		int ret = 0;
		if(b <= l || r <= a) return ret;
		else if(a <= l && r <= b) ret = rmq[i];
		else ret = Math.max(getMax(2*i + 1, a, b, l, (l + r) / 2), getMax(2*i + 2, a, b, (l + r) / 2, r));

		return ret;
	}
	static void add(int i, int e){
		i += qn - 1;
		rmq[i] = e;
		while(0 < i){
			i = (i - 1) / 2;
			rmq[i] = Math.max(rmq[i], e);
		}
	}
	//numを上回る最小の2のベキ乗を返す
	static int pow2(int num){
		int c = 1;
		while(c < num) c*= 2;
		return c;
	}
}
3383. Shiro? Kuro?

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3383

HTMLのカラーコードで表現されたビットマップが与えられ、それを与えられた基準に従って白黒に変換する問題。

実装するだけ。ただ、結構勉強になった。

Javaのn進文字列を数字に変える方法。

Integer.parseInt("AA", 16); //170

parseIntの引数に基数を入れる。

Stringの部分文字列を取る方法。インデックスの1から2までは

"ABC".substring(1, 3); //BC

で取れる。結構間違えそう。

import java.io.PrintWriter;
import java.util.Scanner;

public class Q3383 {

	public static void main(String[] args) {
		doIt();
	}
	
	static int calc(String s){
		return (Integer.parseInt(s.substring(1, 3), 16)*11 + Integer.parseInt(s.substring(3, 5), 16) * 16 + Integer.parseInt(s.substring(5, 7), 16) * 5) / 32;
	}
	
	static void doIt() {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		while(sc.hasNext()){
			String s = sc.next();
			String[] input = s.split("x");
			int w = Integer.parseInt(input[0]);
			int h = Integer.parseInt(input[1]);
			int[][] f = new int[h][w];
			int sum = 0;
			for (int i = 0; i < f.length; i++) {
				for (int j = 0; j < f[0].length; j++) {
					f[i][j] = calc(sc.next());
					sum += f[i][j];
				}
			}
			int threshold = (192 + 2 * (sum / (w*h))) / 3;
			pw.println(s);
			for (int i = 0; i < f.length; i++) {
				if(f[i][0] < threshold) pw.print(9);
				else pw.print(" ");
				for (int j = 1; j < f[0].length; j++) {
					if(f[i][j] < threshold) pw.print(" 9");
					else pw.print("  ");
				}
				pw.println();
			}
		}
		pw.close();
	}

}
3384. Yuyuko and Youmu

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3384

日数nが与えられる。各日ごとに幽々子が食べる量と妖夢が準備する量が与えられる。幽々子がなるべく新鮮なものを食べれるような割り当てを求める問題。

前から考えると難しそうなので、逆から考える。後ろの日から見ていって幽々子が食べる量だけ食料を減らしていく。

import java.io.PrintWriter;
import java.util.Scanner;

public class Q3384 {

	public static void main(String[] args) {
		doIt();
	}
	
	static void doIt(){
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		while(sc.hasNext()){
			int n = sc.nextInt();
			int[] a = new int[n];
			int[] b = new int[n];
			long[] ans = new long[n];
			for(int i = 0; i< n; i++) a[i] = sc.nextInt();
			for(int i = 0; i< n; i++) b[i] = sc.nextInt();
			for(int i = n - 1; 0 <= i; i--){
				for(int j = i; 0 <= j; j--){
					int m = Math.min(a[i], b[j]);
					a[i] -= m;
					b[j] -= m;
					ans[j] += m;
					if(a[i] == 0) break;
					else if(b[j] == 0) continue;
				}
			}
			if(a[0] == 0) print(ans, pw);
			else pw.println("Myon");
		}
		pw.close();
	}
	static void print(long[] a, PrintWriter pw){
		pw.print(a[0]);
		for(int i = 1; i < a.length; i++) pw.print(" " + a[i]);
		pw.println();
	}

}
3633. Alice's present

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3633

配列とクエリ(u, v)が与えられる。配列の区間[u, v]の中に同じ要素があるかどうかを判定する問題。

配列長が500000あるので、DPを使う。
配列の各位置について、自分より左側で一番近い要素がダブる位置とその位置の配列値を覚えておく。

JavaでやったらTLEになったので、C++で実装。
そのまま手動で変換したらWAだったので、デバッグしてみたらC++のmapって既に存在するキーでinsertしても無視されるんですね・・・。Javaだと上書きされるのに。なので、同じキーでinsertするときはその前にそのキーを消しておきます。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
typedef pair<int, int> P;

void doIt(){
	int n, m, v, left, right, input[500001], dp[500001][2];
	while(scanf("%d", &n) != EOF){
		for(int i = 0; i < n; i++) scanf("%d", &input[i]);
		dp[0][1] = -1;
		map<int, int> maps;
		maps.insert(P(input[0], 0));
		for(int i = 1; i < n; i++) {
			if(maps.count(input[i]) == 1){
				v = maps.find(input[i])->second;
				if(v >= dp[i - 1][1]){
					dp[i][0] = input[i];
					dp[i][1] = v;
				}
				else{
					dp[i][0] = dp[i - 1][0];
					dp[i][1] = dp[i - 1][1];
				}
				maps.erase(input[i]);
			}
			else{
				dp[i][0] = dp[i - 1][0];
				dp[i][1] = dp[i - 1][1];
			}
			maps.insert(P(input[i], i));
		}
		scanf("%d", &m);
		for(int i = 0; i < m; i++) {
			scanf("%d", &left);
			scanf("%d", &right);
			left--;right--;
			if(left <= dp[right][1]) printf("%d\n", dp[right][0]);
			else printf("OK\n");
		}
		printf("\n");
	}
}


int main(){
	doIt();
	return 0;
}