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)
ARC12とZOJ
最近ようやくEclipseのテンプレート機能を有効活用し始めました。for文とか早く入力出来て便利ですねー。もっと早くScannerとPrintWriterをテンプレート化しておけば良かった。
AtCoder Regular Contest #012
http://arc012.contest.atcoder.jp/
A - 週末
英語の曜日が与えられる。週末（土曜、日曜）までの日数を求める問題。
書くだけ。スペルミスが怖くて1分くらい確認してました。
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; }
コンテストラッシュ2
ここ（http://wikiwiki.jp/kyopro/?FrontPage）を見て面白そうなOnline Judgeがあったのでいくつか登録してみました。あとFacebook Hacker Cupの結果を。
Facebook Hacker Cup 2013 Round 1
https://www.facebook.com/hackercup/problems.php?round=189890111155691
1問目だけ挑戦。時間が午前3時開始という鬼畜時間。
1.Card Game
数字が書かれているN種類のカードからK枚選ぶ。手札の強さを手札の中の最大値とするとき、全ての手札の強さの総和（ % 1 000 000 007）を求める問題。
手札を数字順にソートして、残りの枚数からk枚取る組み合わせを計算していけば良い。
組み合わせの計算が難しい。割り算が入ってくるので、公式通りに真面目にやると誤差が出てしまいそうである。
しかし、総和の% 1 000 000 007を求めれば良く、これは素数である。そこでフェルマーの小定理（http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Fermat.html）を使うと、
a / b (mod 1 000 000 007) = a * b^(1 000 000 007 - 2) (mod 1 000 000 007)
と出来るのでこれを利用する。
前にARC（http://arc009.contest.atcoder.jp/tasks/arc009_3）で解いたことがあるので出来ました（参考 : http://d.hatena.ne.jp/ty70/20121028/1351418377）。
あと、BigIntegerのmodInverse関数で逆元が計算出来るみたいなので、これを使っても良さそう（http://www.tutorialspoint.com/java/math/biginteger_modinverse.htm）。
ただ、念のためにと思って入れておいた条件が邪魔して、k = 1のときに上手くいかなくてWA。これからは上限だけじゃなくて下限もチェックするように心がけます・・・。
正解コード
import java.io.PrintWriter; import java.util.Collections; import java.util.PriorityQueue; import java.util.Scanner; public class Q2013_R1_1 { static final int MOD = 1000000007; public static void main(String[] args) { doIt(); } static void doIt(){ Scanner sc = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); int t = sc.nextInt(); for(int i = 0; i < t; i++){ int n = sc.nextInt(); int k = sc.nextInt(); if(n == 1){ out.println("Case #" + (i + 1) + ": " + sc.nextInt()); continue; } PriorityQueue<Long> queue = new PriorityQueue<Long>(n, Collections.reverseOrder()); for(int j = 0; j < n; j++) queue.add(sc.nextLong()); long ans = 0; n--;k--; while(k <= queue.size() && k <= n){ long b = queue.poll(); ans += (b * combi(n--,k)) % MOD; ans %= MOD; } out.println("Case #" + (i + 1) + ": " + ans); } out.flush(); } static long pow(long n, long p){ long ans = 1; while(p != 0){ if((p&1) == 1) ans = (ans*n) % MOD; n = (n*n) % MOD; p = p>>1; } return ans; } static long combi(long n, long k){ long a = 0; if(n - k < k) a = n - k; else a = k; long m = 1; long c = 1; for(int i = 0; i < a; i++){ m = (m * (n - i)) % MOD; c = (c * (a - i)) % MOD; } return (m * pow(c, MOD - 2)) % MOD; } }
結局0問正解で全然だめでした。解説はこちら（https://www.facebook.com/notes/facebook-hacker-cup/2013-round-1-solutions/606859202663318）。2問目はいつか余裕があったら解きたいなー。
Project Euler
コンテストじゃないけど、数学より（？）のオンラインジャッジ。ソースコードじゃなく、答えを提出する形式。
特訓のためにHaskellで挑戦しています。Project EulerはHaskellと相性がいいです（びっくりなことにWikiに乗ってる : http://www.haskell.org/haskellwiki/Euler_problems/）。久しぶりに1問解いてみました。
13. Large Sum(http://projecteuler.net/problem=13)
50桁の数字100個が与えられる。総和の始めの10桁を求める問題。
Haskellのプログラムに文字列として直接書き込むと改行があるためにコンパイルが通らない。そこで入力はファイルに書いておいてreadFileで読み込む。
main = do str <- readFile "input.txt" print $ (take 10) $ show $ sum $ map read (words $ str)
CodeChef
ランキングがインド人、インド人以外で分けられてるOnline Judge。
今February 2013 Challengeという長期間のコンテストに挑戦中なので、終わったら記事にします（多分）。
Caribbean Online Judge
The COJ Progressive Contest #5 （http://coj.uci.cu/contest/cproblems.xhtml?cid=1229）という長期間のコンテストがあったので出てみました。解けたやつだけ解説。
1. Wordstorm
ゲームのシミュレーション。書くだけ。
import java.util.Scanner; public class Main { public static void main(String[] args) { doIt(); } static void doIt(){ Scanner sc = new Scanner(System.in); while(sc.hasNext()){ char[] input = sc.next().toCharArray(); char cent = input[4]; int[] alpha = new int[26]; for(char c : input) alpha[c - 'A']++; int n = sc.nextInt(); for(int ii = 0; ii < n; ii++){ String word = sc.next(); int[] alpha2 = new int[26]; for(int i = 0; i < 26; i++) alpha2[i] = alpha[i]; boolean bOK = true; boolean bCent = false; if(4 <= word.length()){ for(int i = 0; i < word.length(); i++){ if(alpha2[word.charAt(i) - 'A']-- < 1){bOK = false;break;} else if(word.charAt(i) == cent) bCent = true; } } if(bOK && bCent) System.out.println(word + " is valid"); else System.out.println(word + " is invalid"); } } } }
3. Sandwich
A1, A2, .. , AMの配列が与えられた時に、A1[j1] <= A2[j2] <= ··· <= AM[jM] となるようなインデックスの集合の中で、AM[jM]-A1[j1]が最小のものを見つける問題。
配列Aiの各要素を見て、自分より小さい中で一番大きい配列A(i -1)の要素を見つけてそこに最終的に到達するAMの値を伝播していけばよい。floorEntryのように、「n以下で一番大きいkeyを見つける」機能があるTreeMapを使うと簡単。
始め、TreeMapの配列の作り方が分からなかった（参考 : http://www.javaroad.jp/bbs/answer.jsp?q_id=20101125114042213）。
import java.io.PrintWriter; import java.util.Map.Entry; import java.util.Scanner; import java.util.TreeMap; public class Main { static final int INI = (int)2.0e9; public static void main(String[] args) { doIt(); } static void doIt(){ Scanner sc = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); int t = sc.nextInt(); for(int ii = 0; ii < t; ii++){ int m = sc.nextInt(); TreeMap<Integer, Integer>[] map = new TreeMap[m]; for(int i = 0; i < m - 1; i++){ map[i] = new TreeMap<Integer,Integer>(); int n = sc.nextInt(); for(int j = 0; j < n; j++) map[i].put(sc.nextInt(), INI); } map[m-1] = new TreeMap<Integer,Integer>(); int n = sc.nextInt(); for(int j = 0; j < n; j++){ int k = sc.nextInt(); map[m-1].put(k, k); } for(int i = m - 1; 1 <= i; i--){ for(Entry<Integer, Integer> e : map[i].entrySet()){ int v = e.getValue(); if(v != INI){ Entry<Integer, Integer> tar = map[i - 1].floorEntry(e.getKey()); if(tar != null) map[i-1].put(tar.getKey(), Math.min(v, tar.getValue())); } } } int min = INI; for(Entry<Integer, Integer> e : map[0].entrySet()) { int key = e.getKey(); int val = e.getValue(); if(val != INI && val - key < min) min = val - key; } out.println(min == INI? -1 : min); } out.flush(); } }
4. Benevolent Dictator
Name a bの記述がいくつか与えられる。これをコストaでb得られるとすると、全てを実行出来るかという問題。
順番は任意なので、始めに0 <= b - aの処理を行い、その後にb - a < 0の処理を全部やって、総和が非負であればよい。
（C++で挑戦。始め入出力をcin,coutでやっててTLEになった）
#include <iostream> #include <vector> #include <algorithm> #include <cstdio> using namespace std; typedef unsigned long long ull; typedef pair<ull, ull> P; void doIt(){ ull n, m; while(true){ //cin >> n >> m; scanf("%llu %llu", &n, &m); if(n + m == 0) break; vector<P> plus; vector<P> minus; for(int i = 0; i < n; i++){ while(true){ string s; char cc[1024]; //cin >> s; scanf("%s", cc); s = cc; if(s.find(":") != string::npos) break; }; ull c, r; //cin >> c >> r; scanf("%llu %llu", &c, &r); if(c <= r) plus.push_back(P(c, r)); else minus.push_back(P(c, r)); } sort(plus.begin(), plus.end()); bool bOK = true; for(int i = 0; i < plus.size(); i++){ if(plus[i].first <= m) m += plus[i].second - plus[i].first; else{bOK = false; break;} } for(int i = 0; i < minus.size(); i++){ if(minus[i].first <= m) m += minus[i].second - minus[i].first; else{bOK = false; break;} } if(bOK && 0 <= m) printf("BENEVOLENT DICTATORSHIP\n");//cout << "BENEVOLENT DICTATORSHIP" << endl; else printf("SOCIETY RESISTS CHANGE\n");//cout << "SOCIETY RESISTS CHANGE" << endl; } } int main(){ doIt(); return 0; }
7. Quite a Problem
文章が与えられた時に"problem"の文字列が含まれているかを判定する問題。
バカ正直にやってもいけるのかもしれないが、念のためメモ化で実装。後ろから見ていく。
改行だけの行に注意が必要。
import java.io.PrintWriter; import java.util.Scanner; public class Main { public static void main(String[] args) { doIt(); } static void doIt(){ Scanner sc = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); while(sc.hasNext()){ char[] line = sc.nextLine().toCharArray(); int n = line.length; if(n == 0){out.println("no"); continue;} int[] dp = new int[n]; if(line[n - 1] == 'm' || line[n - 1] == 'M') dp[n - 1] = 1; boolean bContain = false; for(int i = n - 2; 0 <= i; i--){ switch(line[i]){ case 'p': case 'P': if(dp[i + 1] == 6) bContain = true; break; case 'r': case 'R': if(dp[i + 1] == 5) dp[i] = 6; break; case 'o': case 'O': if(dp[i + 1] == 4) dp[i] = 5; break; case 'b': case 'B': if(dp[i + 1] == 3) dp[i] = 4; break; case 'l': case 'L': if(dp[i + 1] == 2) dp[i] = 3; break; case 'e': case 'E': if(dp[i + 1] == 1) dp[i] = 2; break; case 'm': case 'M': dp[i] = 1; break; default: break; } } if(bContain) out.println("yes"); else out.println("no"); } out.flush(); } }
18. Hitting the Targets
いくつかの図形と点が与えられたとき、各点がいくつの図形に含まれているかを判定する問題。
図形が円と四角形だけなので、簡単に判定出来る。
import java.io.PrintWriter; import java.util.Scanner; public class Main { static final int RECT = 1; static final int CIRC = 2; public static void main(String[] args) { doIt(); } static void doIt(){ Scanner sc = new Scanner(System.in); PrintWriter pw = new PrintWriter(System.out); int m = sc.nextInt(); Shape[] ary = new Shape[m]; for(int i = 0; i < m; i++){ String s = sc.next(); if(s.equals("rectangle")) ary[i] = new Shape(RECT, sc.nextInt(),sc.nextInt(),sc.nextInt(),sc.nextInt()); else ary[i] = new Shape(CIRC, sc.nextInt(),sc.nextInt(),sc.nextInt()); } int n = sc.nextInt(); for(int i = 0; i < n; i++){ int x = sc.nextInt(); int y = sc.nextInt(); int c = 0; for(int j = 0; j < m; j++){ if(ary[j].contain(x, y)) c++; } pw.println(c); } pw.flush(); } } class Shape{ int type, x1, y1, x2, y2, r; Shape(int t, int x1, int y1, int x2, int y2){ type = t; this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; } Shape(int t, int x1, int y1, int r){ type = t; this.x1 = x1; this.y1 = y1; this.r = r; } boolean contain(int x, int y){ boolean ret = false; if(type == 1){ if(x1 <= x && x <= x2 && y1 <= y && y <= y2) ret = true; } else{ if(Math.sqrt(Math.pow(x1 - x, 2) + Math.pow(y1 - y, 2)) <= r) ret = true; } return ret; } }
22. Ragged Right
最終問題なのに実装するだけ。サービス問題？
import java.util.Scanner; import java.util.Vector; public class Main { public static void main(String[] args) { doIt(); } static void doIt(){ Scanner sc = new Scanner(System.in); Vector<Integer> v = new Vector<Integer>(); int max = 0; while(sc.hasNext()){ String s = sc.nextLine(); int m = s.length(); v.add(m); max = Math.max(m, max); } int sum = 0; for(int i = 0; i < v.size() - 1; i++){ sum += Math.pow(max - v.get(i), 2); } System.out.println(sum); } }
6/22問でAC率35.29％、450点で11/116位でした。母数が少ないとはいえ、この順位は嬉しい。
COJの難易度は結構自分に合っていると思うので、解けなかった問題も解いてみようと思います。
コンテストラッシュ
最近プログラミングコンテストがやけに集中して開催されていたので、いくつか出てみました。
Facebook Hacker Cup 2013 Qualification Round
就活のためにと思って登録したFacebookでしたけど、コンテストなんてやっているとは。
1.Beautiful strings
https://www.facebook.com/hackercup/problems.php?pid=475986555798659&round=185564241586420
各アルファベットに1〜26の点数を割り当てたとき、与えられた文字列の点数を最大化する問題。
単純にアルファベットの数を数え、出現回数が多い順に高い点数を当てはめていけば良い。
#include <iostream> #include <algorithm> using namespace std; typedef pair<int, int> data; int doIt(){ int m = 0; int ary[26]; string input; data ans[26]; cin >> m; cin.ignore(); for(int i = 0; i < m; i++){ getline(cin, input); fill(ary, ary + 26, 0); for(int j = 0; j < input.size(); j++){ char c = input[j]; if('a' <= c && c <= 'z') ary[c - 'a']++; else if('A' <= c && c <= 'Z') ary[c - 'A']++; } for(int j = 0; j < 26; j++) ans[j] = data(ary[j], j); sort(ans, ans + 26); int val = 1; for(int j = 0; j < 26; j++) ary[ans[j].second] = val++; int res = 0; for(int j = 0; j < input.size(); j++){ char c = input[j]; if('a' <= c && c <= 'z') res += ary[c - 'a']; else if('A' <= c && c <= 'Z') res += ary[c - 'A']; } cout << "Case #" << (i + 1) << ": " << res << endl;; } } int main(){ doIt(); }
2.Balanced Smileys
https://www.facebook.com/hackercup/problems.php?pid=403525256396727&round=185564241586420
丸括弧と顔文字（「:)」、「:(」）のある文法でかっこのバランスが正しいかどうかを判定する問題。
始めは研究で使っているPackrat Parsingで解こうと思ったが、よく考えると上手くいかない。
文字列長が高々100なので、ネストのレベルは高々100となる。そこで、文字列を解析してあり得るネストのレベルを並列に覚えておくことにした。
1.「:(」が来たらネストのレベルを0、1増やす。
2.「:)」が来たらネストのレベルを0、1減らす。
3.「(」が来たらネストのレベルを1増やす。
2.「)」が来たらネストのレベルを1減らす。
これで最後にネストレベル0があり得たら"YES"、あり得なかったら"NO"とすればよい。
と、これで出来たのですが、始めに書いたコードにバグがあり、それを修正したコードを書いたのに間違えて始めに書いたコードを提出してWAというorz
正解コード
import java.util.Scanner; public class Q2012_2 { public static void main(String[] args) { doIt(); } static void doIt(){ Scanner sc = new Scanner(System.in); int t = sc.nextInt(); sc.nextLine(); for(int i = 0; i < t; i++){ char[] input = sc.nextLine().toCharArray(); boolean[] nest = new boolean[101]; boolean bColon = false; nest[0] = true; for(int j = 0; j < input.length; j++){ char c = input[j]; if(c == ':'){ bColon = true; continue; } if(c == '('){ if(bColon){ for(int k = 99; 0 <= k; k--) if(nest[k]) nest[k + 1] = true; } else{ for(int k = 99; 0 <= k; k--) if(nest[k]){ nest[k] = false; nest[k + 1] = true; } } } else if(c == ')'){ if(bColon){ for(int k = 1; k < 100; k++) if(nest[k]) nest[k - 1] = true; } else{ if(nest[0]) nest[0] = false; for(int k = 1; k < 100; k++) if(nest[k]){ nest[k - 1] = true; nest[k] = false; } } } else{ if('a' <= c && c <= 'z' || c == ' ' || c == ':'){ } else{nest[0] = false;break;} } bColon = false; } System.out.println("Case #" + (i + 1) + ": " + (nest[0]? "YES" : "NO")); } } }
3問目は全く分かりませんでした。
結局1問正解で7319 / 11392位でした。2問目を落としたのが本当に悔やまれる。
一応次のラウンドに進めました。
Codeforces Round #164 (Div. 2)
http://codeforces.com/contest/268
今度こそはCを解こう！と意気込んで参加。
A.Games
始めはスポーツスケジューリング問題かと思ったけど違った。シミュレーション。
import java.util.Scanner; public class A { public static void main(String[] args) { doIt(); } static void doIt(){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] uni = new int[n][2]; for(int i = 0; i < n; i++){ uni[i][0] = sc.nextInt(); uni[i][1] = sc.nextInt(); } int count = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(uni[i][0] == uni[j][1]) count++; } } System.out.println(count); } }
B.Buttons
正解のボタンを押し続けると錠が解ける金庫を最悪ケース何回押さないといけないかを求める問題。
ボタンの個数がn個とすると、1個目のボタンは最悪でn回押さないといけない。2個目のボタンはn-1*(2)回、k個目のボタンは(n - (k - 1))*(k)回押さないと行けない。
import java.util.Scanner; public class B { public static void main(String[] args) { doIt(); } static void doIt(){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int inc = 1; int sum = 0; for(int i = n; 0 < i; i--){ sum += (i-1)*inc; inc++; } System.out.println(sum + n); } }
C. Beautiful Sets of Points
n * mの二次元座標が与えられたとき、各点間の距離が整数にならないように点を配置したとき、その最大数と各点の座標を求める。ただし(0, 0)には置けない。
上手く解けませんでした。
始めに、(i, j)に点を置くとそれ以降にi行目とj列目には点が置けなくなるので、おそらく点の数はmin(n, m) + 1になるというのは分かった。
小さいところから貪欲に置いていけばいいのかと思ったのですが、(0, 1)、(4, 4)の距離が5になるなど問題が発生してしまう。
結局時間切れで駄目でした。後日、人に訊いてみたら「右斜め下の端から左斜め上に向けて置いていけば絶対大丈夫なんじゃない？」と言われ、その通りに実装したら通りました。言われてみれば簡単なんだけどなー。コロンブスの卵。
あとこれはあまり関係ないけど、この問題のように正しい要素とその総数を出力する問題の場合、コードの実行順に出力すると要素→総数となってしまいます。
PrintWriterを使うと、flushを呼ぶまで出力を遅延出来るので（初めて知った）、PrintWriterに要素の出力を溜めておき、総数をSystem.out.printlnで出力し、その後にPrintWriterをflushすると総数→要素の順に出せます。
正解コード
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 out = new PrintWriter(System.out); int n = sc.nextInt(); int m = sc.nextInt(); //boolean[] usedX = new boolean[n + 1]; boolean[] usedY = new boolean[m + 1]; int count = 0; for(int i = n; 0 <= i; i--){ for(int j = 0; j <= m; j++){ if(0 < i+j && usedY[j] == false){ count++; out.println(i + " " + j); usedY[j] = true; break; } } } System.out.println(count); out.flush(); } }
D,Eは見ていません。
結局2問正解で1126 / 3001位でした。今回は全然駄目だったなー。
Rating : 1435(Rank 956) → 1406(Rank 854)
SRM568 (Div. 1)
初Div.1！過去のDiv.1 Easyを見ても全く解けなかったので緊張しながら参加。
Easy. BallsSeparating
http://community.topcoder.com/stat?c=problem_statement&pm=12398
n個の箱に赤、緑、青のボールがいくつかずつ入っている。全ての箱のボールを1色にするようにボールを移動させるとき、その最小個数はいくつか。
単純にやりました。
各箱について、一番個数が多い色以外の色のボールを移動すれば良い。
でも、ある一つの色がどの箱でも最大個数で無い場合に、その色の行き先の箱がなくなってしまう。その場合は各箱を見て、その色の個数と最大個数の差が最小になる箱を見つけて、その差分を結果に足せば良い。
一番難しいのは全ての箱で一つの色が最大個数になっているとき。この場合は残りの二色とその色の差分を昇順にソートして、それぞれ一番少ない差分を足せば良い。インデックスが同じ場合は一番と二番を比較すればよい。
と思ったんですが、Systm Testで落とされてました。なんか駄目みたいです。なんで？？
medium以降は全く分からなかったので、1問目の撃墜しようとコーナーケースを作ってました。
でも、Challenging Phaseで何も出来ずorz
結局1問も解けず、Div2に降格。Div1は僕にはまだ早いですね・・・。
Rating : 1287 → 1172
追記(2013/01/30)
初その日のうちに追記！
TopCoderもCodeforcesみたいにテストケースが見れることをさっき知りました。僕の解答は以下のやつです。
http://community.topcoder.com/stat?c=problem_solution&rm=315694&rd=15488&pm=12398&cr=23103815
分析してみると、駄目な原因が分かりました。1つの色がどの箱でも最大個数でない場合に、コンテスト中に提出したコードではその色と最大個数との差分が一番小さいものを無条件に使っていたのですが、その最大個数の色がその箱しか無い場合にその色を入れる箱が無くなってしまうために上手くいかないんですね。思いつきませんでした。
import java.util.Arrays; //import java.util.*; public class BallsSeparating { public int minOperations(int[] red, int[] green, int[] blue) { int ret = 0; int n = red.length; pair[][] diff = new pair[3][n]; int[] max = new int[n]; int[] bFlag = new int[3]; if(n < 3) return -1; for(int i = 0; i < n; i++){ int r = red[i]; int g = green[i]; int b = blue[i]; if(r <= g && b <= g){max[i] = 1;diff[0][i] = new pair(g - r, i);diff[1][i] = new pair(0, i); diff[2][i] = new pair(g - b, i);bFlag[1] += 1;ret += r + b;} else if(r <= b && g <= b){max[i] = 2;diff[0][i] = new pair(b - r, i);diff[1][i] = new pair(b - g, i); diff[2][i] = new pair(0, i);bFlag[2] += 1;ret += r + g;} else{max[i] = 0;diff[0][i] = new pair(0, i);diff[1][i] = new pair(r - g, i); diff[2][i] = new pair(r - b, i);bFlag[0] += 1;ret += g + b;} } int count = 0; for(int i = 0; i < 3; i++){if(bFlag[i] == 0) count++;} if(count == 0) ; else if(count == 1){ int tar = 0; for(int i = 0; i < 3; i++){if(bFlag[i] == 0) tar = i;} Arrays.sort(diff[tar]); for(int i = 0; i < n; i++){if(bFlag[max[diff[tar][i].index]] > 1){ret += diff[tar][i].diff; break;}}; } else{ int[] tar = new int[2]; int index = 0; for(int i = 0; i < 3; i++){if(bFlag[i] == 0){tar[index] = i;index++;}} Arrays.sort(diff[tar[0]]); Arrays.sort(diff[tar[1]]); if(diff[tar[0]][0].index == diff[tar[1]][0].index){ret += Math.min(diff[tar[0]][0].diff + diff[tar[1]][1].diff, diff[tar[0]][1].diff + diff[tar[1]][0].diff);} else ret += diff[tar[0]][0].diff + diff[tar[1]][0].diff; } return ret; } // BEGIN CUT HERE public static void main(String[] args) { int[] red = {852057, 889141, 662939, 340220};//{10, 5, 8}; int[] green = {600081, 390298, 376707, 372199};//{8,2,2}; int[] blue = {435097, 40266, 145590, 505103};//{9,2,2}; BallsSeparating temp = new BallsSeparating(); System.out.println(temp.minOperations(red, green, blue)); } // END CUT HERE } class pair implements Comparable<pair>{ int diff = 0; int index = 0; pair(int d, int i){ diff = d; index = i; } public int compareTo(pair o) { return diff - o.diff; } }
typedef pair<int, int> data;
みたいにsort可能なお手軽な2つ組のクラスがあるといいんですが。他のコンテストならC++使えば良いんですが、TopCoderはエディタの設定が大変なのできついです。pairクラスのテンプレートを作っておくしかないのかなあ。
追記2：2013/02/24
Facebook Hacker Cup Qualification Roundの3問目Find the Min(https://www.facebook.com/hackercup/problems.php?pid=494433657264959&round=185564241586420)を解説(http://www.facebook.com/notes/facebook-hacker-cup/qualification-round-solutions/598486173500621)を見ながら解きました。
・bとかcはlongにしとかないと危険。
・解説にある通りmapを使う。始めHashMapを使おうと思ったんだけど、HashMapには最小のキーを取る関数が無かったのでTreeMapを使用。pollFirstEntryで最小のキーを取得しながらmapから取り除くことが可能。超便利。
・コード下部のposを合わせるのがちょっと大変だった・・・。
import java.util.TreeMap; import java.util.Scanner; public class Q2013_QR_3 { public static void main(String[] args) { doIt(); } static void doIt(){ Scanner sc = new Scanner(System.in); int t = sc.nextInt(); sc.nextLine(); for(int i = 0; i < t; i++){ int n = sc.nextInt(); int k = sc.nextInt(); int a = sc.nextInt(); long b = sc.nextInt(); long c = sc.nextInt(); long r = sc.nextInt(); int[] ans = new int[k + 1]; boolean[] nums = new boolean[k + 1]; int[] m = new int[k]; int[] time = new int[k + 1]; m[0] = a; if(0 <= a && a <= k){nums[a] = true; time[a] = 0;} TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(); for (int j = 1; j < k; j++) { long e = (b * m[j - 1] + c) % r; m[j] = (int)e; if(0 <= e && e <= k && m[j] < k + 1){nums[m[j]] = true; time[m[j]] = j;} } for (int j = 0; j <= k; j++) { if(!nums[j]) map.put(j, 0); } boolean[] nums2 = new boolean[k + 1]; for (int j = 0; j < k; j++) { int e = map.pollFirstEntry().getKey(); ans[j] = e; if(m[j] <= k && !nums2[j] && time[m[j]] <= j){ map.put(m[j], 0); nums2[j] = true; } } ans[k] = map.pollFirstEntry().getKey(); int pos = (n - k - 1) % (k + 1); System.out.println("Case #" + (i + 1) + ": " + ans[pos]); } } }
Codeforces Round #162 (Div. 2)に参加してみた！
http://codeforces.com/contest/265
登録したもののなかなか参加出来なかったCodeforcesについに参加しました。
Codeforcesは形式がTopCoderに似ていて、得点は時間依存で、hackというTopCoderの撃墜があります。ただし、hackはコーディング中に行うという点が違います。
以下記録です。
A. Colorful Stones (Simplified Edition)
実装するだけ。でも問題文が英語なので理解に時間がかかりました。3回くらい読み直してようやく分かりました。15分くらい。
import java.util.Scanner; public class A { public static void main(String[] args) { doIt(); } static void doIt(){ Scanner sc = new Scanner(System.in); char[] s = sc.next().toCharArray(); char[] t = sc.next().toCharArray(); int pos = 0; for(int i = 0; i < t.length; i++){ if(s[pos] == t[i]) pos++; } System.out.println(pos + 1); } }
B. Roadside Trees (Simplified Edition)
これも実装するだけ。でも問題文が英語なので（略
one secondが1,2のことかと思った自分はもう駄目かもしれない。
これも15分くらい。
import java.util.Scanner; public class B { public static void main(String[] args) { doIt(); } static void doIt(){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] h = new int[n]; for(int i = 0; i < n; i++) h[i] = sc.nextInt(); int height = h[0]; int sec = h[0] + 1; for(int i = 1; i < n; i++){ if(height > h[i]){ sec += height - h[i]; height = h[i]; } sec++; sec += h[i] - height; height = h[i]; sec++; } System.out.println(sec); } }
C. Roadside Trees (Simplified Edition)
降ってくる石を与えられたように左、右に避け続けた時の最終的な石の並び順を求める問題。
単に左右に石を配置してコードを提出したところ、コンテスト終了直前にhackされてWAでした。
やっぱりシミュレーションかと思ってコンテスト終了後にdoubleで石の位置を覚えておいて、最後にソートしてみたけどWA。どうもdoubleの精度の問題で最後の方は値が同じになってしまい、TreeMapにkeyが同じと見なされているっぽい。どうすればいいんだろう？
D. Good Sequences
与えられた数字の配列から順序を保持し、「隣り合う数字のgcdが2以上」という条件のもとで出来る部分列の最長の長さを求める問題。単純にDPで実装してみたけど、計算量がn^2になり、n <= 10^5なので全然無理。これも分からない。
Eはやってません。
次回参加することがあったらとりあえずCを解くことを目標にします。
C、Dは時間があったら解き直したいなー。
Rating : Unrated → 1435
2013/1/26 追記
C解けました。
アルゴリズムは合っていたっぽいのですが、TLEになっていました。
前はVectorで配列を作りながらシミュレートしていたのと、出力にSystem.out.printlnを使っていたために遅いみたいです。
なのでシミュレートをやめ、出力はPrintWriterでやったところAC。
import java.io.PrintWriter; import java.util.Scanner; public class C2 { public static void main(String[] args) { doIt(); } static void doIt(){ Scanner sc = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); char[] input = sc.next().toCharArray(); for(int i = 0; i < input.length; i++){ if(input[i] == 'r') out.println(i+1); } for(int i = input.length - 1; 0 <= i; i--){ if(input[i] == 'l') out.println(i+1); } out.flush(); } }
次はDをなんとかしたい。
AtCoder Regular Contest #011に参加してみた
久々のプロコン！
A - 鉛筆リサイクルの新技術
そのまま実装すればOK。10分くらい。
ソースコード
B - ルイス・キャロルの記憶術
Bにはめずらしくこれも基本的に実装するだけ。終わった時点で30分くらい経過。
ソースコード
C - ダブレット
ある単語first、lastとN個の単語リストが与えられる。1文字ずつfirstから1文字ずつ変えて単語リストの文字を経由してlastにたどり着くまでの過程を調べる問題。
前に似てる問題がDPで使われているのを見たことがあるのでDPかと思いきや単語数が1000。とても状態数を保持できない。
一応BFSで行けるのかなあと思って実装。経路1→7→5をStringで"1 7 5"で保存するという駄目そうな実装で、WA + TLE。全然だめでした。
終了後に他の人のコードを参考に再実装。重要な点は2つで、
1. 一度調べた単語を2度と調べる必要は無い（あとでまた調べるのは冗長）。
2. 経路の覚え方は前から覚えておくのは大変だが、後ろから覚えれば簡単。
データ構造をやけに豊富に使いました。集合はHashSet、キューはLinkedList、スタックはStackです。
ソースコード。
2問解けたのでまあまあ満足な回でした。でも3問目は頑張れば出来る問題だったなあ。惜しいことをした。順位は99位(2問)。次回も100位以内を目指します。
JavaScript Engine
研究でJavaScriptを使うことになり、JavaScriptを簡単に実行出来る環境が必要になりました。
Google Chromeを使ってやるのも無理ではないのですが、やはり毎回ブラウザを立ち上げたくないです。RubyのirbとかPythonのREPLみたいな対話式環境と、jsファイルを簡単に実行出来る環境が欲しい。
というわけで探してみました。
node.js
まず始めにうちの研究室でよく使われているnode.js(http://nodejs.org/)を使ってみることに。しかし、どうもMac OS X 10.5.8ではサポートされていないようです(参考 : http://therobotsbrain.blogspot.com.au/2012/03/installing-nodejs-on-os-x-105.html)。
V8
C++で書かれたGoogle Chromeにも使われている高速エンジン。
こちらのページ(http://shinya-blog.blogspot.jp/2011/01/macjavascriptv8.html)を参考にやってみるも、エラー。どうも今のバージョンのビルドはSconでは駄目で、GYPというのを使わなければいけないようです。でも上手くいかなかったので断念。
Rhino
Javaで書かれたMozillaの作ったエンジン。ビルドがすごい簡単で、簡単に導入できました(参考 : http://d.hatena.ne.jp/Snaka/20100917/1284700063)。
ただ、readlineの機能がなく、非常に使いづらいです(historyとかないし、方向キーも効かない)。そこで調べてみたところ、rlwrapというのがあり、これを使うとreadlineの機能がないエンジンにreadlineの機能を付加出来るらしいです(http://d.hatena.ne.jp/secondlife/20060607/1149653094)。すごい！
さっそくインストールしてみるも、失敗。readlineのバージョンが4.2以上でないといけないらしいので、readlineをアップデート。しかしrlwrapはインストール出来ませんでした。どうもreadlineのインストールが完全に上手くいっていないようです。
Homebrewでrlwrapをインストールできるみたいなので、Homebrewを使うことに。しかし、brew installが上手く動かず。HomebrewはOS X 10.5ではXcode3.1.4が入っていないと駄目だそうです。
仕方ないのでApple Developer IDを取得してXcode3.1.4を入手し、「brew install rlwrap」。今度は成功。しかも上手く使えます。Homebrew便利！
SpiderMonkey
こちらもMozillaが管理するエンジン。FireFoxに使われている（いた？）とか。Cで書かれており、Rhinoより早いようです
(http://stackoverflow.com/questions/9060841/rhino-vs-spidermonkey-performance-tests)。
手動でのインストールは失敗したのですが(参考 : http://d.hatena.ne.jp/yutakikuchi/20110904/1315105395)、「brew install spidermonkey」なら上手くいくかもと思い実行。みごと成功しました。
もしかしてV8もbrewでいける？とやってみるも失敗。どうもSVN(Subversion)のエラーっぽいので「brew install svn」でSVNをバージョンアップしたらSVNのエラーは消えるも、なんかPythonファイルでエラー発生。/Library/Python/2.5/site-packages/gyp/input.pyの「except ImportError as e:」がSyntax Error。検索してみると、Python3.xでは駄目だとか(http://stackoverflow.com/questions/10418209/django-can-not-get-django-admin-py-to-run-anything)。でも2.5だしなあ・・・。
「brew install python」でPythonのバージョンを2.7.3に更新し、「brew install v8」で今度こそ成功しました。
でも「make native -j2 library=shared snapshot=on console=readline」でインストールされていた(http://code.google.com/p/v8/wiki/BuildingWithGYP)けど、v8(sample shell)で起動してもd8(console)で起動してもreadlineが効かない。どういうこと？それにv8とd8の違いはなんなんだろう？？多分d8を使うのがいいんだろうけど。
SpiderMonkeyとV8のどっちが速いかは難しいけど、若干V8の方が良さそうなので(http://stackoverflow.com/questions/2137320/javascript-engines-advantages、http://favo.asia/2012/01/v8-vs-spidermonkey/)、しばらく「rlwrap d8」でJavaScriptを動かしてみようと思います。
おまけ
node.jsのエンジンをv8からSpiderMonkeyに変えたSpidernodeっていうのがあるらしいです(http://www.moongift.jp/2011/05/20110503-3/)。
