CodeChef November Challenge 2012 参加記 - nanikakaのAOJ航海日誌

コンテストリンク CodeChef November Challenge 2012

問題	結果
Coin Flip	AC
Sridhar Likes Travelling	AC
Delicious Dishes	1RE AC
A Wonderful Chocolate	2WA AC
Candy Collecting Game	AC
Lucky Balance	AC
Jam Board	26RE 9TLE
Many Left	-
Arithmetic Progressions	-
Martial Arts	-

6 / 10
Score: 6
Rank: 148 (Global)

自分にしては結構解けた方かなーっと。JamBoardは許さない。

Coin Flip

概要

N枚のコインを全て同じ向き（表か裏）を決めて並べる。全部でNラウンド試行を試す。kラウンド目には、1〜kのコインの向きを全てひっくり返す。最終的に指定した向きのコインが何枚あるか答えよ。

解法

Nの偶奇と最初のコインの向きで場合分けする

ソース

import java.util.Arrays;

//Coin Flip
public class CONFLIP {

	void run(){
		Scanner sc = new Scanner();
		int T = sc.nextInt();
		while(T--!=0){
			int G = sc.nextInt();
			while(G--!=0){
				int I = sc.nextInt(), N = sc.nextInt(), Q = sc.nextInt();
				int nt = 0, nh = 0;
				if(I==1){
					nt = (N+1)>>1; nh = N-nt;
				}
				else{
					nh = (N+1)>>1; nt = N-nh;
				}
				System.out.println(Q==1?nh:nt);
			}
		}
	}

	class Scanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
	}

	void debug(Object...o){
		System.out.println(Arrays.deepToString(o));
	}

	public static void main(String[] args){
		new CONFLIP().run();
	}
}

Sridhar Likes Travelling

概要

N-1枚のカードに「出発都市到着都市コスト」が書かれている。カードに書いてある通りに移動することができる。カードには全部でN種類の都市が記述されているので、全ての都市を巡るようにカードを並べ替えよ。また、コストの合計も答えよ。

解法

到着都市に指定されていない唯一の都市が出発都市なので、あとは一意にカードの順が決まる。

ソース

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

//Sridhar Likes Travelling
public class TOURMAP {

	class R{
		String f, t;
		int c;
		public R(String f, String t, int c) {
			this.f = f;
			this.t = t;
			this.c = c;
		}
	}
	
	void run(){
		Scanner sc = new Scanner();
		int T = sc.nextInt();
		while(T--!=0){
			int N = sc.nextInt(), cost = 0;
			Set<String> towns = new HashSet<String>(), to = new HashSet<String>();
			Map<String, R> ref = new HashMap<String, R>();
			for(int i=0;i<N-1;i++){
				String f = sc.next(), t = sc.next();
				int c = sc.nextInt();
				cost+=c;
				towns.add(f); towns.add(t); to.add(t);
				ref.put(f, new R(f, t, c));
			}
			String start = "";
			for(String s:towns)if(!to.contains(s)){
				start = s; break;
			}
			for(int i=0;i<N-1;i++){
				R r = ref.get(start);
				System.out.println(r.f+" "+r.t+" "+r.c+"$");
				start = r.t;
			}
			System.out.println(cost+"$");
		}
	}
	
	class Scanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
		long nextLong() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextLong();
				long res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		String next() {
			try {
				StringBuilder res = new StringBuilder("");
				int c = System.in.read();
				while (Character.isWhitespace(c))
					c = System.in.read();
				do {
					res.append((char) c);
				} while (!Character.isWhitespace(c = System.in.read()));
				return res.toString();
			} catch (Exception e) {
				return null;
			}
		}
		String nextLine(){
			try{
				StringBuilder res =new StringBuilder("");
				int c = System.in.read();
				while (c=='\r' || c=='\n')
					c = System.in.read();
				do {
					res.append((char) c);
					c = System.in.read();
				} while (c!='\r' && c!='\n');
				return res.toString();
			}catch (Exception e) {
				return null;
			}
		}
	}
	
	void debug(Object...o){
		System.out.println(Arrays.deepToString(o));
	}
	
	public static void main(String[] args){
		new TOURMAP().run();
	}
}

Delicious Dishes

概要

ある整数Xが「おいしい数字」とはXの各桁に同じ数字が2度以上登場しないものをいう。L以上R以下の範囲においしい数字はいくつあるか答えよ。

解法

関数F(X)を「0以上X以下にあるおいしい数字の個数」とする。これを使うと答えはF(R)-F(L-1)で求まる。
F(X)は上の桁から数字を決める再帰で何とか書ける。数字を決めていったときに、もうX以下になることが確定する時がある。そのときはそれ以上潜る必要はない。そのとき、余っているn個の数字をk桁分並べる組み合わせ数を計算すればよい。この値は何度も必要になるので、前もって、com[N][K]の表に計算しておくと吉。ただ、X以下が確定した時に0リーディングが続いている場合、0リーディングを更に続けた数字を作らなければならない。例えば、X=5678で、先頭の桁を0にしたときX以下になることが確定する。
5678
0___ ←何が来てもよい
残っている数字は1〜9の9つでこれを3ケタ並べるわけだが、組み合わせ数を9P3とだけしてしまうと
0022
とか
0007
とかがカウントされない。なので、リーディング0の場合はこれも数えるように一工夫する必要がある。

ソース

import java.util.Arrays;

//Delicious Dishes
public class DDISH {

	char[] s;
	boolean[] u;
	long[][] com;

	long zeros(int n, int k){
		if(k==1)return n;
		return (n-1)*com[n-1][k-1]+zeros(n, k-1);
	}
	
	long f(int k, boolean zero, boolean free){
		if(s.length-k>10)return f(k+1, zero, true);
		if(k==s.length)return 1;
		if(free){
			int n = 0, m = s.length-k;
			for(boolean b:u)if(!b)n++;
			if(m==1)return n;
			return zero?zeros(n, m):com[n][m];
		}
		long res = 0;
		for(int i=0;i<=s[k]-'0';i++)if(!u[i]){
			if(i==0){
				if(zero){
					res+=f(k+1, zero, free|i<s[k]-'0');
				}
				else{
					u[i] = true;
					res+=f(k+1, zero, free|i<s[k]-'0');
					u[i] = false;
				}
			}
			else{
				u[i] = true;
				res+=f(k+1, false, free|i<s[k]-'0');
				u[i] = false;
			}
		}
		return res;
	}
	
	void run(){
		Scanner sc = new Scanner();
		int T = sc.nextInt();
		u = new boolean[10];
		com = new long[11][11];
		for(int n=1;n<=10;n++)for(int k=1;k<=n;k++){
			if(k==1)com[n][k]=n;
			else com[n][k] = n*com[n-1][k-1];
		}
		while(T--!=0){
			long L = sc.nextLong()-1, R = sc.nextLong();
			Arrays.fill(u, false);
			s = (R+"").toCharArray();
			long res = f(0, true, false);
			s = (L+"").toCharArray();
			res-=f(0, true, false);
			System.out.println(res);
		}
	}
	
	class Scanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
		long nextLong() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextLong();
				long res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		String next() {
			try {
				StringBuilder res = new StringBuilder("");
				int c = System.in.read();
				while (Character.isWhitespace(c))
					c = System.in.read();
				do {
					res.append((char) c);
				} while (!Character.isWhitespace(c = System.in.read()));
				return res.toString();
			} catch (Exception e) {
				return null;
			}
		}
		String nextLine(){
			try{
				StringBuilder res =new StringBuilder("");
				int c = System.in.read();
				while (c=='\r' || c=='\n')
					c = System.in.read();
				do {
					res.append((char) c);
					c = System.in.read();
				} while (c!='\r' && c!='\n');
				return res.toString();
			}catch (Exception e) {
				return null;
			}
		}
	}
	
	void debug(Object...o){
		System.out.println(Arrays.deepToString(o));
	}
	
	public static void main(String[] args){
		new DDISH().run();
	}
}

A Wonderful Chocolate

概要

1*1の正方形がa*b個の長方形で並んでいる。正方形は黒か白の色をしている。a*bのチョコレートの見栄えが良いとは、「幅が1より大きい且つ高さが1より大きい、同じ色の長方形がない」ことをいう。見栄えがよい長方形をいくつ作ることができるか。

解法

a <= 6, b < 2^63というベリークレイジーな大きさなので、DPが絶望的。aの小ささを利用しようと試みる。
色々とペンを動かしてみたところ次のような解法を思い付く。
縦1列のチョコレートを考えると、2^a個しかない。この2^a個に番号をつけ、iのチョコレートの右側に置いても、見栄えを損なわないチョコレートjを見つける。この関係を2次元配列で持つ。この行列をb乗する。
b乗したあと、黒と白が交互にならんでいるような状態の行の総和が答え ← (!?
いや、サンプルの(a,b)=(3,3)を紙に書いていてですね、そこで求まったとある数字の列が、上述した遷移行列の3乗のとある行にぴったり一致したわけですよ。その行がどうも黒と白が交互にならんでいるような状態の位置に来るようなのですよ。試しに、submitしたら通っちゃったわけですよ。笑ってしまった。要Editorialですね、はい。

ソース

import java.util.Arrays;
import java.util.Scanner;

//A Wonderful Chocolate
public class CBARS {

	long[][] modpow(long[][] A, long n, long M){
		long[][] res = new long[A.length][A.length];
		for(int i=0;i<A.length;i++){
			res[i][i] = 1L;
		}
		while(n>0){
			if((n&1)>0){
				res = modmul(res, A, M);
			}
			A = modmul(A, A, M);
			n>>=1;
		}
		return res;
	}
	
	long[][] modmul(long[][] A, long[][] B, long M){
		long[][] res = new long[A.length][B[0].length];
		for(int i=0;i<A.length;i++){
			for(int j=0;j<B[0].length;j++){
				for(int k=0;k<A[0].length;k++){
					res[i][j] = (res[i][j] + A[i][k]*B[k][j]);
					if(M <= res[i][j])res[i][j]%=M;
				}
			}
		}
		return res;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		long b = sc.nextLong();
		long MOD = (long) (1e9+7);
		long[][] A = new long[1<<a][1<<a];
		for(int i=0;i<1<<a;i++)for(int j=i;j<1<<a;j++){
			boolean f = true;
			for(int k=0;k<a-1;k++){
				if(((i>>k)&1)==((j>>k)&1) && ((i>>k)&1)==((j>>(k+1))&1) && ((i>>(k+1))&1)==((j>>k)&1) && ((i>>(k+1))&1)==((j>>(k+1))&1))f=false;
			}
			A[i][j]=A[j][i]=f?1:0;
		}
		A = modpow(A, b, MOD);
		long res = 0;
		int i = a==1?1:a==2?1:a==3?5:a==4?5:21;
		for(int j=0;j<1<<a;j++)res+=A[i][j];
		System.out.println(res%MOD);
	}
	void print(long[][]A, int n){
		for(int i=0;i<1<<n;i++){
			for(int j=0;j<1<<n;j++)System.out.printf("%3d", A[i][j]);
			System.out.println();
		}
	}
	
	void debug(Object...o){
		System.out.println(Arrays.deepToString(o));
	}
	
	public static void main(String[] args) {
		new CBARS().run();
	}
}

Candy Collecting Game

概要

N*Mの各グリッドにA[i][j]個のキャンディーがある。これを使ってaliceとbobがゲームをする。
ルールはめんどいので書きません。

解法

ゲームのグリッドの状態は4つの変数で表すことができる(上から何行選択したか、下から何行選択したか、左から何列選択したか、右から何列選択したか）。あるグリッドの状態から、ゲームを進行したとき、結果は常に一緒になるのでDPで解くことができる。今回はメモ化DPで解いた。
(r1, r2, c1, c2)をゲームの状態とする。状態数は単純に計算すると50^4だが、実際には、r1+r2<=Nかつc1+c2<=Mという制約があるので、状態数はもっと小さい。よって、DP表を初期化するときは、この制約を満たす範囲のみ初期化すればプログラムが速くなる。
dp[r1][r2][c1][c2]は、bobが取得できるキャンディーの最大値を返すことにする。
r1+r2==Nもしくはc1+c2==Mのとき、キャンディーがグリッドから無くなるので、これが基底状態になる。各行、各列に対して、キャンディーの累積和を作っておくと、以降必要なキャンディーの個数が一発で計算できる。
r1+r2+c1+c2が偶数のとき、アリスの手番となる。アリスの動き方は一意に決まるので楽。
偶数のとき、bobは4種類の選び方全てを試して最大値を計算すればよい。
問題の答えとしては、res = dp[0][0][0][0]の値が使える。このresとグリッド上のキャンディの総数sumを使う。res == sum/2のとき、ゲームは引き分けになり、キャンディ総取りになるので答えはsumになる。そうでないとき、max(res, sum-res)が答えになる。

ソース

import java.util.Arrays;

//Candy Collecting Game
public class CANDYGAM {

	long[][][][] dp;
	int h, w;
	long[][] a;
	long[][] sumRow, sumCol;
	
	long get(int r1, int r2, int c1, int c2){
		if(dp[r1][r2][c1][c2]!=-1)return dp[r1][r2][c1][c2];
		if(r1+r2==h || c1+c2==w)return dp[r1][r2][c1][c2]=0;
		if(((r1+r2+c1+c2)&1)==0){
			long min = sumRow[r1+1][w-c2]-sumRow[r1+1][c1];
			int idx = 0;
			if(sumRow[h-r2][w-c2]-sumRow[h-r2][c1] < min){
				min = sumRow[h-r2][w-c2]-sumRow[h-r2][c1]; idx = 1;
			}
			if(sumCol[c1+1][h-r2]-sumCol[c1+1][r1] < min){
				min = sumCol[c1+1][h-r2]-sumCol[c1+1][r1]; idx = 2;
			}
			if(sumCol[w-c2][h-r2]-sumCol[w-c2][r1] < min){
				min = sumCol[w-c2][h-r2]-sumCol[w-c2][r1]; idx = 3;
			}
			if(idx==0)return dp[r1][r2][c1][c2] = get(r1+1, r2, c1, c2);
			if(idx==1)return dp[r1][r2][c1][c2] = get(r1, r2+1, c1, c2);
			if(idx==2)return dp[r1][r2][c1][c2] = get(r1, r2, c1+1, c2);
			else return dp[r1][r2][c1][c2] = get(r1, r2, c1, c2+1);
		}
		else{
			long res = Math.max(sumRow[r1+1][w-c2]-sumRow[r1+1][c1]+get(r1+1, r2, c1, c2), sumRow[h-r2][w-c2]-sumRow[h-r2][c1]+get(r1, r2+1, c1, c2));
			res = Math.max(res, Math.max(sumCol[c1+1][h-r2]-sumCol[c1+1][r1]+get(r1, r2, c1+1, c2), sumCol[w-c2][h-r2]-sumCol[w-c2][r1]+get(r1, r2, c1, c2+1)));
			return dp[r1][r2][c1][c2] = res;
		}
	}
	
	void run(){
		Scanner sc = new Scanner();
		//rowup, rowdown, colleft, colright
		dp = new long[51][51][51][51];
		int T = sc.nextInt();
		while(T--!=0){
			h = sc.nextInt(); w = sc.nextInt();
			for(int i=0;i<=h;i++)for(int j=0;i+j<=h;j++)for(int n=0;n<=w;n++)for(int m=0;n+m<=w;m++)dp[i][j][n][m]=-1;
			long sum = 0;
			a = new long[h+1][w+1];
			sumRow = new long[h+1][w+1]; sumCol = new long[w+1][h+1];
			for(int i=1;i<=h;i++)for(int j=1;j<=w;j++){
				int x = sc.nextInt();
				a[i][j] = x;
				sum+=x;
				sumRow[i][j] = sumRow[i][j-1]+x;
				sumCol[j][i] = sumCol[j][i-1]+x;
			}
			long max = get(0, 0, 0, 0), res;
			if(max==sum-max)res = sum;
			else res = Math.max(max, sum-max);
			System.out.println(res);
		}
	}
	
	class Scanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
	}
	
	void debug(Object...o){
		System.out.println(Arrays.deepToString(o));
	}
	
	public static void main(String[] args){
		new CANDYGAM().run();
	}
}

Lucky Balance

概要

4と7からなる長さNの数列Sがある。Sがバランスしているとは、[1, x)にある4の個数と(x, N]にある7の個数が等しくなるようなxが1つ以上存在することを言う。Sの各数字は好きに並べ替えできる。バランスしている数列をいくつ作れるか答えよ。

解法

4の個数をn4、7の個数をn7とする。バランスするときの4と7の個数kを[1, min(n4, n7)]について試す。個数kでバランスするときの数列の集合と、個数k'でバランスするときの数列の集合は同じ数列を含まないので、各kについての組み合わせ数の総和を取れば答えになる。
k個でバランスするときの数列はいくつあるかは場合分けで数える。xの位置に来るのが4のときと7のときで場合分けする(kによっては、どちらかが置けない場合もある)。以下、4の時で説明する。
xの左側で作れる組み合わせ数Lと右側で作れる組み合わせ数Rを数え、この積が個数をkとしたときで、xの位置に4を採用したときの組み合わせ数になる。
Rについて。n4-k-1個の4とk個の7で作れる数列の個数が分かればよい。シンプルにCOMBI(n4-k-1, k) mod Mになるので、modInverseとか使えば求まる（実はmod Mのコンビネーションは最近勉強したばっかりで使えて嬉しかった）。
Lについても同様で、n7-k個の7と、k個の4で作れる数列の個数がLである。
xの値を7にしたときも同様に計算する。
xの値を4にしたときと7にしたときの結果の和が、個数をkに固定したときの値にしたいところだが、実は両者には重複している文字列があるので、その分を引かなければならない。その文字列は、xの値を4にしたとき、xのすぐ左隣りに7が来るようなものになる。なので、xの値を4にしたとき、同時にこの組み合わせ数も計算しておけばいい。

ソース

import java.util.Arrays;

//Lucky Balance
public class LUCKY9 {

	long M = 1000000007;
	
	long[] exgcd(long x, long y){
		long r0 = x, r1 = y, a0 = 1, a1 = 0, b0 = 0, b1 = 1;
		long q1, r2, a2, b2;
		while(0 < r1){
			q1 = r0/r1;
			r2 = r0%r1;
			a2 = a0-q1*a1;
			b2 = b0-q1*b1;
			r0 = r1; r1 = r2;
			a0 = a1; a1 = a2;
			b0 = b1; b1 = b2;
		}
		return new long[]{a0, b0, r0};
	}
	
	long modInverse(long a, long m){
		long[] r = exgcd(a, m);
		return r[2]==1?(m+r[0])%m:-1;
	}
	
	long[] fact, inv;
	
	long f(int k, int r4, int r7){
		long L = 0, R = 0;
		L = fact[k+r7];
		L = (L*inv[k])%M;
		L = (L*inv[r7])%M;
		R = fact[k+r4];
		R = (R*inv[k])%M;
		R = (R*inv[r4])%M;
		return (L*R)%M;
	}
	
	void run(){
		Scanner sc = new Scanner();
		fact = new long[5001];
		inv = new long[5001];
		fact[0] = fact[1] = inv[0] = inv[1] = 1;
		for(int i=2;i<=5000;i++){
			fact[i] = fact[i-1]*i;
			if(M <= fact[i])fact[i]%=M;
			inv[i] = inv[i-1]*modInverse(i, M);
			if(M <= inv[i])inv[i]%=M;
		}
		int T = sc.nextInt();
		while(T--!=0){
			char[] s = sc.next().toCharArray();
			int n4 = 0, n7 = 0;
			for(char c:s)if(c=='4')n4++;else n7++;
			int min = Math.min(n4, n7);
			long res = 0;
			for(int k=0;k<=min;k++){
				int r4 = n4-k, r7 = n7-k;
				long cnt;
				if(r4==0){
					r7--;
					if(r7 < 0)cnt = 0;
					else if(r7==0)cnt = 1;
					else {
						cnt = fact[k+r7];
						cnt = (cnt*inv[r7])%M;
						cnt = (cnt*inv[k])%M;
					}
				}
				else if(r7==0){
					r4--;
					if(r4 < 0)cnt = 0;
					else if(r4==0)cnt = 1;
					else{
						cnt = fact[k+r4];
						cnt = (cnt*inv[r4])%M;
						cnt = (cnt*inv[k])%M;
					}
				}
				else {
					long case4 = f(k, r4-1, r7), case7 = f(k, r4, r7-1), cross = 0;
					if(r7==0)cross = 0;
					else{
						cross = fact[r7-1+k];
						cross = (cross*inv[r7-1])%M;
						cross = (cross*inv[k])%M;
						long R = fact[k+r4-1];
						R = (R*inv[k])%M;
						R = (R*inv[r4-1])%M;
						cross = (cross*R)%M;
					}
					cnt = (case4+case7-cross+M)%M;
				}
				res+=cnt;
				if(M <= res)res-=M;
			}
			System.out.println(res);
		}
	}
	
	class Scanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
		String next() {
			try {
				StringBuilder res = new StringBuilder("");
				int c = System.in.read();
				while (Character.isWhitespace(c))
					c = System.in.read();
				do {
					res.append((char) c);
				} while (!Character.isWhitespace(c = System.in.read()));
				return res.toString();
			} catch (Exception e) {
				return null;
			}
		}
	}
	
	void debug(Object...o){
		System.out.println(Arrays.deepToString(o));
	}
	
	public static void main(String[] args){
		new LUCKY9().run();
	}
}

Jam Board

概要

N個のコマンドを実行しろ（書くのが面倒になってきた）

思考

どう考えても、UnionFindゲーに見える。R*Cの大きさのunionfindになって、各グループに対して、接続されている電源の個数を管理して、Lコマンドが来たら、電源の個数が0と、それ以外になっているかいないかを見るだけで...。だが無情なTLE。0.5秒とか頭おかしい。
仮に命令が全部Lだったとき、println("ON"or"OFF");をN回実行するだけで1秒近くかかるようなので、StringBuilder()で答えを5000個くらい蓄えて一気に出力しようとしたらREで死ぬ。きっとMLEで死んでいるのだと思うんだけれど、なんか納得いかない。
モヤモヤしたまま終了。なんぞこれー。UnionFindは罠なのかしら。

Many Left

概要

スーパーマリオRPGのクッパ城でハンマーブロスに吹っかけられる鉄球使ったミニゲームがテーマ。ただこの問題は、鉄球をたくさん残して詰みになりたい。

思考

こーいう問題とんでもなく苦手。何から手をつけたらいいのか分からない。とりあえず、何も考えず、ただ単に詰みの状態までシミュレートするプログラム投げつけてやろうかと思ったけどむなしいのでやらなかった。

Arithmetic Progressions

概要

N個の数字が並んでいる。i

思考

Ai+Ak = 2Aj に式変形したりしたけど解法の糸口はつかめず。

Martial Arts

概要

2チームに分かれて、戦わせて、でも相手チームは1回だけ試合結果を無効にできて、みたいなノリだったはず。

思考

難易度最強のようだったので考えなかった。

感想

最初の方に解いた問題の解法を思い出すのに苦労しました(Lucky9とか）。
キャンディーゲームやラッキーバランスを1発で通せたので嬉しいです。特にラッキーは勉強したての知識がまんま使えたので手ごたえバッチリでした。チョコレートはまぐれで解けたようなものです。