AtCoder Regular Contest 066 D - Xor Sum
解法
import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; import java.util.TreeMap; /* _ooOoo_ o8888888o 88" . "88 (| -_- |) O\ = /O ____/`---'\____ .' \\| |// `. / \\||| : |||// \ / _||||| -:- |||||- \ | | \\\ - /// | | | \_| ''\---/'' | | \ .-\__ `-` ___/-. / ___`. .' /--.--\ `. . __ ."" '< `.___\_<|>_/___.' >'"". | | : `- \`.;`\ _ /`;.`/ - ` : | | \ \ `-. \_ __\ /__ _/ .-` / / ======`-.____`-.___\_____/___.-`____.-'====== `=---=' ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ pass System Test! */ public class Main { private static class Task { int MOD = (int) (1e9 + 7); TreeMap<Long, TreeMap<Long, Long>> dp = new TreeMap<>(); long func(long S, long X) { if (S == 0) return 1; TreeMap<Long, Long> d = dp.get(S); if (d == null) dp.put(S, d = new TreeMap<>()); else { Long ans = d.get(X); if (ans != null) return ans; } long ans = func(S / 2, X / 2) % MOD; ans = (ans + func((S - 1) / 2, (X - 1) / 2)) % MOD; if (S >= 2) ans = (ans + func((S - 2) / 2, X / 2)) % MOD; d.put(X, ans); return ans; } void solve(FastScanner in, PrintWriter out) throws Exception { long N = in.nextLong(); out.println(func(N, N)); } } /** * ここから下はテンプレートです。 */ public static void main(String[] args) throws Exception { OutputStream outputStream = System.out; FastScanner in = new FastScanner(); PrintWriter out = new PrintWriter(outputStream); Task solver = new Task(); solver.solve(in, out); out.close(); } private static class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int bufferLength = 0; private boolean hasNextByte() { if (ptr < bufferLength) { return true; } else { ptr = 0; try { bufferLength = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (bufferLength <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; } boolean hasNext() { skipUnprintable(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while (true) { if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } double nextDouble() { return Double.parseDouble(next()); } double[] nextDoubleArray(int n) { double[] array = new double[n]; for (int i = 0; i < n; i++) { array[i] = nextDouble(); } return array; } double[][] nextDoubleMap(int n, int m) { double[][] map = new double[n][]; for (int i = 0; i < n; i++) { map[i] = nextDoubleArray(m); } return map; } public int nextInt() { return (int) nextLong(); } public int[] nextIntArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; i++) array[i] = nextInt(); return array; } public long[] nextLongArray(int n) { long[] array = new long[n]; for (int i = 0; i < n; i++) array[i] = nextLong(); return array; } public String[] nextStringArray(int n) { String[] array = new String[n]; for (int i = 0; i < n; i++) array[i] = next(); return array; } public char[][] nextCharMap(int n) { char[][] array = new char[n][]; for (int i = 0; i < n; i++) array[i] = next().toCharArray(); return array; } public int[][] nextIntMap(int n, int m) { int[][] map = new int[n][]; for (int i = 0; i < n; i++) { map[i] = nextIntArray(m); } return map; } } }
ガールズ&パンツァー 9話
ガルパン Advent Calendar 2016 - Adventarの記事として書かれました。
ガルパン9話「絶体絶命です！」で泣いた視聴者は多いと思います。ご多分に漏れず、私も毎回泣くので、それについて書きます。
「無謀だったかもしれないけどさあ、あと1年、泣いて学校生活を送るより、希望を持ちたかったんだよ」
会長はどんなときでも弱音を吐きません。こんな絶望的な状況で、廃校を言い渡されたことを全員に説明しなければならないときでも、このように笑いながら話します。
背負ってきたものがあまりにも重かったのでしょう。学園の最高権力者として頂点に君臨していますが、劇中では学園の生徒だけではなく、学園艦で暮らす人々の生活の面倒も見ていることが感じられます。その学園艦がなくなるかもしれないという事態は、当然、学園艦で暮らす全ての人に不安を感じさせますから、生徒会長はできるだけ不安を感じさせないように、明るくしなければならないと感じているのかもしれません。泣けますね。
「だって、来年もこの学校で戦車道をやりたいから。みんなと」
大洗女子学園に来てから、西住みほの戦車道への気持ちが変わってきていることは劇中で何度か言及がありましたが、大洗女子のみんなと戦車道がやりたいと明言したのは、このシーンが初めてな気がします。「黒森峰・西住流の戦車道をやりたくないが、それ以外の戦車道なら楽しいかも」という気持ちから、「大洗女子のみんなと戦車道をやりたい」という気持ちへと積極性が増す変化があったことが感じられます。
「だって、来年もこの学校で戦車道をやりたいから」で少し間を空けるのがずるいですよね。ここだけ聞くと、「そうだね、黒森峰から逃げてきてよかったね」という感じですが、その後に「みんなと」が入ると全く違った意味になり、込み上げてくるものがあります。泣けますね。
「敵に四方を囲まれこの悪天候。きっと戦意も・・・」「それはどうかしら」
実際には、このあと完全に戦意を喪失していることが確認されるわけですが、ダージリンは大洗女子は戦意を喪失していないことを確信しています。本人たちよりも強く信じているんですね。最初に1回試合をしただけで、しかも負かしている相手を、これほどまでに信じているという、ダージリンの大洗女子や西住みほに対する気持ちの強さが表れています。泣けますね。
「あたしらをここまで連れてきてくれて、ありがとね」
普段はやりたい放題、細かいことはあまり気にせず、いつも笑い飛ばしている印象がある生徒会長ですが、出撃前のこの僅かなタイミングで、唐突にお礼を言ってきます。実は普段の底抜けに明るいキャラは作っているキャラで、本当は気遣いの達人であることが感じられます。また、それだけ生徒会長として、普段からみんなに望まれる役割を演じていることも感じられます。泣けますね。
「突撃」
「ところてん作戦」とは、生徒会長率いるカメさんチームが陽動として正面の敵車輌を足止めし、その隙に敵包囲網を一気に突破するという作戦でした。生徒会長という、生徒の中でのヒエラルキーの頂点にありながら、戦車道の時は一兵卒として西住隊長の指示に従う。しかも、敵包囲網に正面から突撃するという危険な役割を積極的に引き受けていく。こういった、しっかりした切り替えのできるところも生徒会長の細やかさの一面でしょうし、そういった生徒会長がいるから西住隊長も他の生徒たちも安心して試合に臨めるのだと思います。泣けますね。
「正面の4輌引き受けたよ！上手くいったらあとで合流すんね！」
プラウダの硬い戦車の中に単機で突っ込んでいくシーンです。「上手くいったらあとで合流すんね！」とは言っていますが、多勢に無勢で上手くいく可能性はほとんどありません。自身は絶望的な戦場に突撃していくところだというにも関わらず、ここでも心配症な西住隊長が安心して離脱できるように気を遣っているのです。泣けますね。
「せーのっ！」
軽快な音楽に合わせて会長が撃ちまくるシーンです。38(t)ではプラウダのソ連製戦車は貫通できないのでゼロ距離で戦いをしかけており、絶望的な戦況なのですが、その状況とリズミカルな音楽のギャップが感情を揺さぶってきます。泣けますね。
「いや〜ごめ〜ん。2輌しかやっつけられなかった上にやられちゃった。あとはよろしくね」
陽動として敵の正面戦力に突っ込んで、案の定やられてしまったシーンです。勝てないと分かっていてもみんなのために前に出て散っていく。生徒会長の器の大きさが感じられます。泣けますね。
「私たちのことはいいから、アヒルさん守ろ！」
ウサギさんチームがIS-2からフラッグ車を護るために壁になるシーンです。それだけで泣けますね。劇場版でウサギさんチームがIS-2と対峙するシーンで思い出すともう一度泣けますね。
「泣くな！涙はバレー部が復活したその日のためにとっておけ！」
こんな絶望的な状況でも、勝利、学園の存続、そしてその先にあるバレー部復活への思いを絶やすことはありません。バレー部復活まで泣くことも許されないアヒルさんチームは一体どんな修羅場をくぐってきたのか。想像するだけで泣けますね。
レオポンさんチーム車長 ナカジマ
ガルパン Advent Calendar 2016 - Adventarの記事として書かれました。
出典: http://girls-und-panzer.jp/chara_nakajima.html
ナカジマといえば、終盤の決勝戦からポルシェティーガーとともに参戦した自動車部のレオポンさんチームの車長ですが、自動車部の存在自体は「あとは自動車部が整備しておいてくれる」的な感じで序盤から言及されており、ナカジマ自身も8話のプラウダ戦直前でIV号の長砲身化のために登場しています。
西住隊長の盾となる活躍
レオポンさんチームにとって初陣となった決勝戦では、同じく決勝戦からの参加となったものの開戦直後にリタイアしたアリクイさんチームと対称に、あらゆる場面でフラッグ車を護る盾となる活躍をします。
まずは山を降りるこのシーン。圧倒的な火力を誇る黒森峰の重戦車部隊に正面から突破するシーンですが、ここでは最前線で盾となって全員を護りながら突撃します。ルノーしか重戦車のなかった大洗女子でしたが、ポルシェティーガーが加わったことで、正面装甲の厚さで押し切るという戦い方が出来るようになりました。
また、最後の一騎打ちの裏では、他の戦車を足止めする役割を担っています。大量の重戦車を抱える黒森峰を倒すにため、「どちらもフラッグ車は1台」ということに着目し、フラッグ車同士での一騎打ちを仕掛けます。ここで、他の戦車を隔離するため、レオポンさんチームが壁となって時間稼ぎをしています。このような戦い方も、ポルシェティーガーあってこそ出来るものです。
高地包囲戦では、一歩間違えば袋叩きにあって全滅してしまいかねませんし、ティーガーIとの一騎打ちでも、ティーガーIIやヤークトパンターなどの高火力戦車を確実に足止めしなければIV号では太刀打ちできません。このようなギリギリの作戦を決行に踏み切れたのも、レオポンさんチームへの厚い信頼があったからではないかと思います。
小隊長としての活躍
黒森峰戦での活躍もあってか、エキシビションマッチでは守備隊を率いる小隊長に抜擢されています。
カモさんチームや知波単学園と一緒にプラウダの別動隊を足止めすることに成功しています。この防衛線が強固なものであったことは直後の「もっと簡単に敵を突破できると思ったのよ！」というカチューシャのセリフからもわかりますね。
さらになんと、大洗市街戦ではOI12地点での防衛線の指揮も任されています。大洗5輌と知波単2輌を率いて、プラウダとグロリアーナの戦車をまとめて足止めしています。
このように、黒森峰戦でも西住隊長のナカジマやレオポンさんチームへの厚い信頼が感じられましたが、エキシビションではハッキリと右腕のような存在になったのではないかと思います。最終章でも活躍が楽しみですね。
自動車部として輝く瞬間
さて、安定感があって西住隊長からの信頼も厚いという面を取り上げましたが、やはり自動車部、魔改造ポルシェティーガーで爆走するシーンは最高ですよね！
冷静さや頼もしさを備えつつ、マシンへの情熱も燃やすナカジマの魅力が存分に感じられる良いシーンです。「いけっ！超音速の貴公子！！」
おわりに
出るのが遅かったけど自動車部は全体的にいいキャラですよね。
DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦 C - 01文字列
解法
ある位置を決めて、そこから前を操作1で、そこから後ろを操作2で作ることを考えます。決め打ちすべき位置はセグメントの隙間だけで良く、置換操作は位置の前後のセグメントの数で決めることができます。置換操作の回数をできるだけ少なくしたいので、決め打ちした位置の前後のセグメントで共通化出来る置換操作は共通化してしまいましょう。
コード
import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.NoSuchElementException; /* _ooOoo_ o8888888o 88" . "88 (| -_- |) O\ = /O ____/`---'\____ .' \\| |// `. / \\||| : |||// \ / _||||| -:- |||||- \ | | \\\ - /// | | | \_| ''\---/'' | | \ .-\__ `-` ___/-. / ___`. .' /--.--\ `. . __ ."" '< `.___\_<|>_/___.' >'"". | | : `- \`.;`\ _ /`;.`/ - ` : | | \ \ `-. \_ __\ /__ _/ .-` / / ======`-.____`-.___\_____/___.-`____.-'====== `=---=' ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ pass System Test! */ public class Main { private static class Task { long A, B, C; String s; void solve(FastScanner in, PrintWriter out) throws Exception { A = in.nextInt(); B = in.nextInt(); C = in.nextInt(); s = in.next(); char[] S = s.toCharArray(); int N = S.length; ArrayList<Integer> heads = new ArrayList<>(); heads.add(0); for (int i = 1; i < N; i++) { if (S[i - 1] == S[i]) continue; heads.add(i); } heads.add(N); if (heads.size() == 2) { long cost0 = A * N; long cost1 = B * N; if (S[0] == '1') cost0 += C; else cost1 += C; out.println(Math.min(cost0, cost1)); return; } long ans = Long.MAX_VALUE; for (int i = 0; i < heads.size(); i++) { int frontSegments = i; int backSegments = heads.size() - 1 - i; int pos = heads.get(i); int replace; if (i == 0) { replace = backSegments - 1; if (S[N - 1] == '0') replace++; } else if (i == heads.size() - 1) { replace = frontSegments - 1; if (S[0] == '1') replace++; } else { int back = backSegments - 1; if (S[N - 1] == '0') back++; int front = frontSegments - 1; if (S[0] == '1') front++; replace = Math.max(front, back); if (front > 0 && back > 0 && front % 2 != back % 2) { replace++; } } long cost = C * replace; cost += A * pos; cost += B * (N - pos); if (ans > cost) ans = cost; } out.println(ans); } } /** * ここから下はテンプレートです。 */ public static void main(String[] args) throws Exception { OutputStream outputStream = System.out; FastScanner in = new FastScanner(); PrintWriter out = new PrintWriter(outputStream); Task solver = new Task(); solver.solve(in, out); out.close(); } private static class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int bufferLength = 0; private boolean hasNextByte() { if (ptr < bufferLength) { return true; } else { ptr = 0; try { bufferLength = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (bufferLength <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; } boolean hasNext() { skipUnprintable(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while (true) { if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } double nextDouble() { return Double.parseDouble(next()); } double[] nextDoubleArray(int n) { double[] array = new double[n]; for (int i = 0; i < n; i++) { array[i] = nextDouble(); } return array; } double[][] nextDoubleMap(int n, int m) { double[][] map = new double[n][]; for (int i = 0; i < n; i++) { map[i] = nextDoubleArray(m); } return map; } public int nextInt() { return (int) nextLong(); } public int[] nextIntArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; i++) array[i] = nextInt(); return array; } public long[] nextLongArray(int n) { long[] array = new long[n]; for (int i = 0; i < n; i++) array[i] = nextLong(); return array; } public String[] nextStringArray(int n) { String[] array = new String[n]; for (int i = 0; i < n; i++) array[i] = next(); return array; } public char[][] nextCharMap(int n) { char[][] array = new char[n][]; for (int i = 0; i < n; i++) array[i] = next().toCharArray(); return array; } public int[][] nextIntMap(int n, int m) { int[][] map = new int[n][]; for (int i = 0; i < n; i++) { map[i] = nextIntArray(m); } return map; } } }
CODE FESTIVAL 2016 Elimination Tournament Round 1 A - グラフ / Graph
解法
求めるべき2つの木は元のグラフの最小全域木の部分木であることは明らかなので、最初に最小全域木を作ります。
S-Tパスの最も大きい辺を切るのが最適なので、各クエリに対してS-T間の最大の辺を答える問題になります。N=4000なので、あらかじめ各頂点から愚直にDFSしておくことでS-T間の最大の重みを求めることができます。
コード
import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.NoSuchElementException; import java.util.PriorityQueue; /* _ooOoo_ o8888888o 88" . "88 (| -_- |) O\ = /O ____/`---'\____ .' \\| |// `. / \\||| : |||// \ / _||||| -:- |||||- \ | | \\\ - /// | | | \_| ''\---/'' | | \ .-\__ `-` ___/-. / ___`. .' /--.--\ `. . __ ."" '< `.___\_<|>_/___.' >'"". | | : `- \`.;`\ _ /`;.`/ - ` : | | \ \ `-. \_ __\ /__ _/ .-` / / ======`-.____`-.___\_____/___.-`____.-'====== `=---=' ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ pass System Test! */ public class Main { private static class Task { ArrayList<Edge>[] tree; void dfs(int v, int p, int start, int curMax, int[] max) { for (Edge edge : tree[v]) { if (edge.to == p) continue; int nextMax = Math.max(curMax, edge.weight); max[edge.to] = nextMax; dfs(edge.to, v, start, nextMax, max); } } void solve(FastScanner in, PrintWriter out) throws Exception { int N = in.nextInt(); int M = in.nextInt(); PriorityQueue<Edge> queue = new PriorityQueue<>(); for (int i = 0; i < M; i++) { int a = in.nextInt() - 1; int b = in.nextInt() - 1; int c = in.nextInt(); queue.add(new Edge(a, b, c)); } UnionFind uf = new UnionFind(N); tree = new ArrayList[N]; for (int i = 0; i < N; i++) { tree[i] = new ArrayList<>(); } long total = 0; while (!queue.isEmpty()) { Edge edge = queue.poll(); if (uf.isSame(edge.from, edge.to)) continue; total += edge.weight; tree[edge.from].add(new Edge(edge.from, edge.to, edge.weight)); tree[edge.to].add(new Edge(edge.to, edge.from, edge.weight)); uf.unite(edge.from, edge.to); } ArrayList<int[]>[] queries = new ArrayList[N]; for (int i = 0; i < N; i++) { queries[i] = new ArrayList<>(); } int Q = in.nextInt(); for (int i = 0; i < Q; i++) { int s = in.nextInt() - 1; int t = in.nextInt() - 1; queries[s].add(new int[]{t, i}); } long[] ans = new long[Q]; int[] max = new int[N]; for (int i = 0; i < N; i++) { Arrays.fill(max, 0); dfs(i, -1, i, 0, max); for (int[] q : queries[i]) { int t = q[0]; int n = q[1]; ans[n] = total - max[t]; } } for (long a : ans) out.println(a); } class Edge implements Comparable<Edge> { int from, to, weight; Edge(int from, int to, int weight) { this.from = from; this.to = to; this.weight = weight; } @Override public int compareTo(Edge o) { return this.weight - o.weight; } } class UnionFind { // par[i]：データiが属する木の親の番号。i == par[i]のとき、データiは木の根ノードである private int[] par; // sizes[i]：根ノードiの木に含まれるデータの数。iが根ノードでない場合は無意味な値となる private int[] sizes; // 木の数 private int size; UnionFind(int n) { par = new int[n]; sizes = new int[n]; size = n; Arrays.fill(sizes, 1); // 最初は全てのデータiがグループiに存在するものとして初期化 for (int i = 0; i < n; i++) par[i] = i; } /** * データxが属する木の根を得る * * @param x * @return */ int find(int x) { if (x == par[x]) return x; return par[x] = find(par[x]); // 根を張り替えながら再帰的に根ノードを探す } /** * 2つのデータx, yが属する木をマージする。 * マージが必要なら true を返す * * @param x * @param y * @return */ boolean unite(int x, int y) { // データの根ノードを得る x = find(x); y = find(y); // 既に同じ木に属しているならマージしない if (x == y) return false; // xの木がyの木より大きくなるようにする if (sizes[x] < sizes[y]) { int tx = x; x = y; y = tx; } // xがyの親になるように連結する par[y] = x; sizes[x] += sizes[y]; sizes[y] = 0; // sizes[y]は無意味な値となるので0を入れておいてもよい size--; return true; } /** * 2つのデータx, yが属する木が同じならtrueを返す * * @param x * @param y * @return */ boolean isSame(int x, int y) { return find(x) == find(y); } /** * データxが含まれる木の大きさを返す * * @param x * @return */ int partialSizeOf(int x) { return sizes[find(x)]; } /** * 木の数を返す * * @return */ int size() { return size; } } } /** * ここから下はテンプレートです。 */ public static void main(String[] args) throws Exception { OutputStream outputStream = System.out; FastScanner in = new FastScanner(); PrintWriter out = new PrintWriter(outputStream); Task solver = new Task(); solver.solve(in, out); out.close(); } private static class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int bufferLength = 0; private boolean hasNextByte() { if (ptr < bufferLength) { return true; } else { ptr = 0; try { bufferLength = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (bufferLength <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; } boolean hasNext() { skipUnprintable(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while (true) { if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } double nextDouble() { return Double.parseDouble(next()); } double[] nextDoubleArray(int n) { double[] array = new double[n]; for (int i = 0; i < n; i++) { array[i] = nextDouble(); } return array; } double[][] nextDoubleMap(int n, int m) { double[][] map = new double[n][]; for (int i = 0; i < n; i++) { map[i] = nextDoubleArray(m); } return map; } public int nextInt() { return (int) nextLong(); } public int[] nextIntArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; i++) array[i] = nextInt(); return array; } public long[] nextLongArray(int n) { long[] array = new long[n]; for (int i = 0; i < n; i++) array[i] = nextLong(); return array; } public String[] nextStringArray(int n) { String[] array = new String[n]; for (int i = 0; i < n; i++) array[i] = next(); return array; } public char[][] nextCharMap(int n) { char[][] array = new char[n][]; for (int i = 0; i < n; i++) array[i] = next().toCharArray(); return array; } public int[][] nextIntMap(int n, int m) { int[][] map = new int[n][]; for (int i = 0; i < n; i++) { map[i] = nextIntArray(m); } return map; } } }
リクルートコミュニケーションズ (RCO) におけるプログラミングコンテストの活用について
この記事は Recruit Engineers Advent Calendar 2016 の3日目の記事です。
RCO プロコン部
RCO アドテク部には、プロコン部、Kaggle 部、SET (Sushi is Everything) などのサークルがあります。プロコン部は気ままにプログラミングコンテスト（プロコン）に参加するサークル、Kaggle 部は気ままに機械学習コンペの Kaggle に参加するサークルで、SET は寿司を食べているようです。
そもそもプロコンとは
「プログラミングのコンテスト」というと範囲が広くなりますが、ここでは、「与えられたプログラミングの問題を、制限時間内に早く正確に解くコンテスト」のことを指します。2時間程度で4問ほど出題されることが多いです。様々なコンテストサービスがあり、以下のサービスを利用することが多いです。
どんな人が参加しているの？
プロコン部と名乗って入るものの、何か決まったメンバーのサークルがあるわけではなく、コンテストになると集まってくる感じです。
よくいるメンバーとしては uwi さん、shiratty8 さん、KenjiH さん、dpforest さん、iehn さん、kenkoooo などがいますが、それ以外の人たちもたまに来たりします。機械学習エンジニアよりもアプリケーション開発エンジニアの方がよく参加している印象です。
日々の活動
プロコン部の日々の活動としては以下のようなものが挙げられます。
- 社内チャットの「プロコン部ルーム」に溜まる
- コンテストに参加する
- 社内 wiki に自分が解いた問題の解説記事を投稿する
- アルゴリズムイントロダクションを輪読する
これらの活動について書いていきます。
社内チャットの「プロコン部ルーム」に溜まる
参加したコンテストの問題の感想や、好きなデータ構造について話したりします。分からない問題などについても聞けたりします。
コンテストに参加する
業務時間中にコンテストがある場合、勉強会としてみんなで集まってコンテストに参加します。TopCoder SRM や HackerRank HourRank などは1〜2時間程度で終わるので、その後1時間ほど問題について議論する時間を設けます。その日に競技プログラミングを始めた人から世界トップクラスの人まで様々なレベルの人が集まるので、解法を議論したり、時間内に通らなかったコードをレビューしたり、別解を検討したりします。
プロコン部ご飯 pic.twitter.com/Ag7azgiAz9
— 宇宙ツイッタラーX (@kenkoooo) October 13, 2016
3時間の長丁場になるので、会社から弁当が支給されます。予算は1人1500円までで、ネット注文しておくこともあれば、八重洲が近いので東京駅まで駅弁を買い出しに行くこともあります。
このように、弁当で体力をつなぎつつ、コンテストを題材にした内容の濃い勉強会を行っています。
社内 wiki に自分が解いた問題の解説記事を投稿する
自分が解いた問題についてチャットで感想を言うこともありますが、内容を残しておきたい問題などについては社内の wiki に投稿することもあります。
アルゴリズムイントロダクションを輪読する
アルゴリズムイントロダクションを読む会が行われています*2。この本は、アルゴリズムの正当性や計算量の上界の証明が丁寧に書かれている教科書で、「プログラミングコンテストチャレンジブック（蟻本）」などと違ってプロコンに直接役立つ本ではありませんが、計算量の議論などはプロコン慣れしている方がやはり分かりやすく、参加者はプロコン勢がほとんどです。
進め方としては、毎週1人担当者を決め、発表者が好きな章を選んで発表しています。最近は、重たい章だけが残ってきたので、何回かに分けて発表します。
※僕が最大フローの章を担当した時の資料
業務の役に立つのか
このように RCO ではプログラミングコンテストを仕事に取り入れていますが、業務では役に立つのでしょうか。
実装が速くなる
個人的な感覚ですが、競プロ勢は実際の業務での実装スピードがかなり速いように感じます。もちろん設計などはまた別の問題で、素早く実装したコードが必ずしも優れた実装であるとは限りませんが、少なくとも自分の知る範囲では、他の人が5営業日かかる実装をプロコン勢は1日や2日で終わらせてしまうような気がします。
これにはいくつか要因が考えられますが、以下のような感じでしょうか。
- プロコンで何度もバグを埋め込んだおかげで、自分がバグを埋めやすい箇所などを把握しているため、バグに振り回される時間が短い。
- プロコンで何度も調べたおかげで、標準ライブラリや言語仕様の知識が蓄積していて、調べる回数が少なくて済む。
- プロコンでできるだけ共通化して記述量を減らすコツが蓄積していて、記述量が少なくて済む。
- プロコン用に設定やスニペットをゴリゴリに積んだ IDE を使っているのでスピードが出る。*3
プロコン特有のものではなく、単に四六時中プログラミングしていると身につくようなことばかりですね。ただ、プロコンでは特にまっさらな状態から実装するため、できるだけ速く少なく正確に実装する訓練が詰めるのかもしれません。
より強くなってくると、実装を始める前に頭のなかでコーディングを終えてしまうらしいので、さらに速くなるのかもしれません。早くその境地に達したいですね。
計算量の大まかな感覚がつかめる
プロコンで出題される問題の多くは「データのサイズが小さければ簡単に解ける問題」であることが多いです。
例えば、次のスライドに出てくる問題を見てみましょう。
スライドの中で、この問題は N=10 程度まであれば簡単に解けるが、N=1000などは発想を変えなければならないという話をしています。
実際の業務の中で、例えば最大フローや動的計画法などのアルゴリズムを駆使して計算を高速化する場面は多くはありませんが、計算量の感覚というのは重要だと思います。特にRCOアドテク部ではリアルタイム処理を行うことがあり、そういった分野では計算量の感覚は不可欠です。
コンピュータがざっくり1秒間に10億回くらい計算できると考えて、サービスに対して秒間10万のクエリが来るとき、1クエリあたり1万回くらいの計算ならできそうということが分かります。3億件のユーザーデータを抱えているので、ユーザー数を N とするとユーザー検索は O(log N) で終わらせる必要がありますね。
この「コンピュータが1秒間に計算できる回数」、「各操作にかかる計算回数」の感覚は非常に重要で、これがチーム内で共有されていることで「この関数は毎秒10万回呼ばれるから中の操作はこのくらいにしないと」「この関数は毎秒1000回しか呼ばれないから、計算量は少し悪くても可読性を優先しよう」などを考えることができます。
おわりに
プロコンは単純にゲームとして非常に面白いと思いますが、同時にプログラマの実装力を高めるかもしれません。色んな会社にプロコンを業務として取り入れる動きが広まってほしいですね。
いつの日か、ACM-ICPC のように会社対抗プログラミングコンテストが開催されるのを楽しみにしています。
