Codeforces Round #166, CodeChefとか
EclipseのC++プラグインCDTがすごい使いやすいんですが、最近デバッグすると飛んだりします。しかも恐ろしいことに頻度が上がってきているような気がする・・・。
February 2013 Challenge
CodeChefのロングランコンテストに出てみました。
このコンテストはなんとミスっても点数が減りません。ゆったり出来ます。
Buy1-Get1
書くだけ・・・のはずなのに3REと1CE。調子に乗ってPythonで書いてみたところ、どうも標準入力の改行文字とかまで処理してたみたいです。かなり焦りました。
Climbing Stairs
N段の階段を1段か2段ずつ上るときの総数をMとする。その時村人の推測（二進数の1の数に等しい数字）がM % 1000000007と等しければ"CORRECT"、等しくなければINCORRECTを出力する。
問題文がすごい長い問題。読解が大変でした。始め50桁の2進数を処理するのかと思いましたw
Little Elephant and Cards
1000ラウンドのゲームをする。カードに1から1000の番号がふられている。始めにN枚のカードから一部を自分が取り、残りを相手が取る。kラウンド目のゲームでは（自分のk色のカードの枚数） - （相手のk色のカードの枚数）を得る。得点を＋にする組み合わせは何通りあるかを求める問題。
よく考えると色を考える必要は全くなく、カードを半分以上持っていれば良い。
Rubyで書いたら普通にTLEだった（http://www.codechef.com/viewsolution/1773670）のでJavaに人力変換。
http://www.codechef.com/viewsolution/1773822
結果は3問でした。
Magic Board (http://www.codechef.com/FEB13/problems/MBOARD)は機会があったら解法を知りたい。
Long Contest Rating : 1000 → 1784
ZOJの東方問題
いくつか（カンニングして）解いたので一応書いておきます。
しかし、解説が中国語だったので苦労しました。あと日本人でやってる人が少ないorz 中国語が読めればなと思ったのは初めて。
参考 :
http://spinda2.blog48.fc2.com/blog-entry-472.html
http://topcoder.g.hatena.ne.jp/nodchip/20110828/1314530784
http://edward-mj.com/?cat=1&paged=12
http://blog.watashi.ws/touhou-monthly/touhou-monthly-solutions/
3520. Hello, Gensokyo
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3520
N人の女の子が両想いだが、三角関係はない。両想いの数は最大いくつか。
グラフにするのかと思ったら、解説によると二部グラフの辺の数に還元出来るらしいです。
import java.io.PrintWriter; import java.util.Scanner; public class Q3520 { 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()){ long n = sc.nextLong(); pw.println((n/2) * ((n+1)/2)); } pw.close(); } }
3523. Bookcase
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3523
与えられた文字列の配列をASCIIに従って並び替えるとき、交換回数の最小を求める問題。
LIS（最長増加部分列 : Longest Increasing Subsequence）に還元するらしいです。この列に入ってる部分は変えなくてよい。
import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; public class Q3523 { 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 m = sc.nextInt(); sc.nextLine(); int ans = 0; for(int ii = 0; ii < n; ii++) { String[] input = new String[m]; int[] lis = new int[m]; for(int i = 0; i < input.length; i++) input[i] = sc.nextLine(); for(int i = 0; i < input.length; i++) { for(int j = 0; j < i; j++) { if(lis[i] <= lis[j] && 0 <= input[i].compareTo(input[j])) lis[i] = lis[j] + 1; } } Arrays.sort(lis); ans += m - (lis[m - 1] + 1); } pw.println(ans); } pw.close(); } }
3528. Parterre
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3528
N * Mの花壇に周りから幅1の四角形で外側から花を埋めていく。範囲のクエリが与えられるので、範囲内の花の種類数と最大数の花の種類と数を答える問題。
全く(ry
幅1の四角形を4本の直線に分割して保存しておき、クエリの範囲との共通部分の面積を出す。
Javaで書いたら通らなかったのでC++に人力変換。ZOJはJavaは危険な気がしてきました。多分これからはC++で解きます。
#include <iostream> #include <cstdio> #include <algorithm> #include <map> #include <cmath> using namespace std; typedef pair<int, int> P; #define MAXNUM 251 #define MAX 502 void doIt(){ int n, m, q, num, left, right, top, bottom, t, l, b, r, size, kind, maxV, maxI; int kinds[MAXNUM*4], type[MAXNUM*4], pos[MAXNUM*4], range[MAXNUM*4][2], maxValue[MAX]; const int VER = 0, HOR = 1; while(scanf("%d %d", &n, &m) != EOF){ num = (int)ceil(min(n, m) / 2.0); left = 0, right = m - 1, top = 0, bottom = n - 1, size = 0; for(int i = 0; i < num; i++) { scanf("%d", &kind); if(left < right){ kinds[size] = kind; type[size] = VER; range[size][0] = top; range[size][1] = bottom; pos[size++] = left++; } if(left <= right){ kinds[size] = kind; type[size] = VER; range[size][0] = top; range[size][1] = bottom; pos[size++] = right--; } if(left <= right){ if(top < bottom){ kinds[size] = kind; type[size] = HOR; range[size][0] = left; range[size][1] = right; pos[size++] = top++; } if(top <= bottom){ kinds[size] = kind; type[size] = HOR; range[size][0] = left; range[size][1] = right; pos[size++] = bottom--; } } } scanf("%d", &q); for (int i = 0; i < q; i++) { map<int, int> numKinds; scanf("%d %d %d %d", &t, &l, &b, &r); fill(maxValue, maxValue + MAX, 0); maxV = 0, maxI = kinds[0]; for(int j = 0; j < size; j++) { int kind = kinds[j]; if(type[j] == VER && l <= pos[j] && pos[j] <= r){ int len = min(range[j][1], b) - max(range[j][0], t) + 1; if(0 < len){ int tmp = len + maxValue[kind]; if(numKinds.count(kind) == 0) numKinds.insert(P(kind, 0)); if(tmp == maxV && kind < maxI){maxI = kind;} else if(maxV < tmp){ maxV = tmp; maxI = kind; } maxValue[kind] = tmp; } } else if(type[j] == HOR && t <= pos[j] && pos[j] <= b){ int len = min(range[j][1], r) - max(range[j][0], l) + 1; if(0 < len){ if(numKinds.count(kind) == 0) numKinds.insert(P(kind, 0)); int tmp = len + maxValue[kind]; if(tmp == maxV && kind < maxI){maxI = kind;} else if(maxV < tmp){ maxV = tmp; maxI = kind; } maxValue[kind] = tmp; } } } printf("%zd %d %d\n", numKinds.size(), maxI, maxV); } } } int main(){ doIt(); return 0; }
3378. Attack the NEET Princess（http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3378）を解いてみたいのだけど、解説(http://blog.watashi.ws/touhou-monthly/touhou-monthly-solutions/kaguya/)見てもよく分からない。でもブリッジを求めるなんて面白そうなので時間が出来たら解こうと思います。
Codeforces Round #166 (Div. 2)
http://codeforces.com/contest/271
さっき終わったばっかのCodeforcesです！
A. Beautiful Year
与えられた年より大きい2013年のように全ての桁の数字が違う年を求める問題。
書くだけ。
import java.io.PrintWriter; import java.util.Scanner; public class A { public static void main(String[] args) { doIt(); } static void doIt() { Scanner sc = new Scanner(System.in); PrintWriter pw = new PrintWriter(System.out); int year = sc.nextInt() + 1; while(true){ char[] cyear = Integer.toString(year).toCharArray(); boolean[] num = new boolean[10]; boolean bOK = true; for (int i = 0; i < cyear.length; i++) { if(num[cyear[i] - '0']){bOK = false;break;} num[cyear[i] - '0'] = true; } if(bOK) break; year++; } System.out.println(year); } }
B. Prime Matrix
N * Mの行列が与えられる。
少なくとも一つの行か列の要素を全て素数にするには何回1を足さないといけないかを求める問題。
ある要素eが素数で無い場合に、eより大きい最小の素数を求める方法に迷った。単純にeから上を調べていってもいいのかもしれないが、怖かったのでTreeMapを使うことに。TreeMapのceilKeyとかfloorKeyは本当に便利。
import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; import java.util.TreeMap; public class B { static final int MAX = 100500; public static void main(String[] args) { doIt(); } static void doIt() { Scanner sc = new Scanner(System.in); PrintWriter pw = new PrintWriter(System.out); boolean[] prime = new boolean[MAX]; Arrays.fill(prime, true); prime[0] = prime[1] = false; TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(); for (int i = 2; i < prime.length; i++) { if(prime[i]){ map.put(i, 0); for (int j = i*2; j < prime.length; j += i) { prime[j] = false; } } } int n = sc.nextInt(); int m = sc.nextInt(); int[][] matrix = new int[n][m]; int[] rowsum = new int[n]; int[] clmsum = new int[m]; for (int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { int e = sc.nextInt(); if(prime[e]) matrix[i][j] = 0; else matrix[i][j] = map.ceilingKey(e) - e; rowsum[i] += matrix[i][j]; clmsum[j] += matrix[i][j]; } } Arrays.sort(rowsum); Arrays.sort(clmsum); System.out.println(Math.min(rowsum[0], clmsum[0])); } }
C. Secret
1からnまでの数字をk個に分割する。その際、各分割内で昇順に並べた時に、各要素の隣との差分が一定ではいけないという条件をつける。このとき、n, kから1つの分割割り当てを作る問題。
まず思いついたのが1, 2, .., k, k, k-1, ... , 1みたいに割り当てる方法。でも普通に駄目。
1, 1, 2, ..., k, k, k, k-1, ...みたいにずらしていけばいいのかと思ったけど、処理が面倒そう。
ラスト30分くらいで思いついたのが、条件よりk * 3 <= nを満たすので、1, 2, 3, .. , k, 1, 2, 3, .., k, [k], 1, 2, ..と並べる方法。これならk*3 = nでも上手く動作する。k*3以上の要素については適当に割り振れば良い。
import java.io.PrintWriter; import java.util.Scanner; public class C { public static void main(String[] args) { doIt(); } static void doIt() { Scanner sc = new Scanner(System.in); PrintWriter pw = new PrintWriter(System.out); int n = sc.nextInt(); int k = sc.nextInt(); if(k * 3 > n){System.out.println(-1); return;} int odd = 1; int even = 2; int p = 1; int[] ans = new int[n + 1]; for (int i = 1; i <= 2*k; i++) { ans[i] = p++; if(k < p) p = 1; } ans[3*k] = 1; p = 2; for (int i = 2*k + 1; i < ans.length; i++) { ans[i] = p++; if(k < p) p = 1; } pw.print(ans[1]); for (int i = 2; i < ans.length; i++) { pw.print(" " + ans[i]); } pw.println(); pw.close(); } }
ドキドキしながら結果を待ってたけど、なんとか全部AC。初めてCを通せました。
その甲斐あって3問解いて2174点で順位はRoomで4/40位、全体で666/1930位でした。上出来。
これからもこれくらいのペースで頑張りたいです。
Rating : 1406(Rank 854) → 1499(Rank 478)
