2016-2017 ACM-ICPC Southwestern European Regional F Performance Review
問題
根つき木があって、各頂点にはランクとコストが定められています。各頂点について、その頂点の子孫であり、かつ、その頂点のランク未満のランクをもつ頂点のコストの合計を計算してください。
解法
オイラーツアーで子孫となる範囲を計算しておきます。こうすることで、各頂点について、子孫を数列上の範囲として管理できます。このような処理をしておくと、以下のようなクエリを処理する問題になります。
- 場所 pos に数字 cost を入れる。
- 範囲 (start, end) に含まれる数字の合計を計算する。
これは Fenwick tree を使うことで処理できます。
解法
import java.io.PrintWriter; import java.util.*; public class F { ArrayList<Integer>[] tree; int[] start; int[] end; private void solve(Scanner in, PrintWriter out) { int N = in.nextInt(); tree = new ArrayList[N]; for (int i = 0; i < N; i++) tree[i] = new ArrayList<>(); start = new int[N]; end = new int[N]; int[] costs = new int[N]; int[] ranks = new int[N]; int rootId = -1; for (int i = 0; i < N; i++) { int parent = in.nextInt() - 1; int rank = in.nextInt(); int cost = in.nextInt(); costs[i] = cost; ranks[i] = rank; if (parent >= 0) { tree[i].add(parent); tree[parent].add(i); } else { rootId = i; } } dfs(rootId, -1); int[][] nodes = new int[N][2]; for (int i = 0; i < N; i++) { nodes[i][0] = ranks[i]; nodes[i][1] = i; } Arrays.sort(nodes, Comparator.comparingInt(o -> o[0])); FenwickTree bit = new FenwickTree(2 * N); long[] ans = new long[N]; int addHead = 0; int sumHead = 0; while (addHead < N) { int curRank = nodes[addHead][0]; while (addHead < N && nodes[addHead][0] == curRank) { int i = nodes[addHead][1]; ans[i] = bit.sum(start[i], end[i]) / 2; addHead++; } while (sumHead < N && nodes[sumHead][0] == curRank) { int i = nodes[sumHead][1]; bit.add(start[i], costs[i]); bit.add(end[i], costs[i]); sumHead++; } } for (long a : ans) out.println(a); } int now = 0; void dfs(int v, int p) { start[v] = now; now++; for (int u : tree[v]) { if (u == p) continue; dfs(u, v); } end[v] = now; now++; } public class FenwickTree { int N; long[] data; FenwickTree(int N) { this.N = N + 1; data = new long[N + 1]; } void add(int k, long val) { for (int x = k; x < N; x |= x + 1) { data[x] += val; } } // [0, k) long sum(int k) { if (k >= N) k = N - 1; long ret = 0; for (int x = k - 1; x >= 0; x = (x & (x + 1)) - 1) { ret += data[x]; } return ret; } // [l, r) long sum(int l, int r) { return sum(r) - sum(l); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); new F().solve(in, out); in.close(); out.close(); } }
AtCoder Regular Contest 065 F - シャッフル / Shuffling
解法
dp[x][y] := x 文字目まで決めて1をy個使ってできる決め方の数
とします。
l 文字目まで見るとき、どこまでがシャッフルされる範囲に含まれるかというのを前もって計算しておけば良いです。
コード
import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; public class Main { private void solve(Scanner in, PrintWriter out) { final int MOD = (int) (1e9 + 7); int N = in.nextInt(); int M = in.nextInt(); char[] S = in.next().toCharArray(); int[] right = new int[N]; Arrays.fill(right, -1); for (int i = 0; i < M; i++) { int l = in.nextInt() - 1; int r = in.nextInt() - 1; if (right[l] < r) right[l] = r; } int max = 0; for (int i = 0; i < N; i++) { max = Math.max(max, i); max = Math.max(max, right[i]); right[i] = max; } int[] sum = new int[N]; for (int i = 0; i < N; i++) sum[i] = S[i] - '0'; for (int i = 0; i < N - 1; i++) sum[i + 1] += sum[i]; long[][] dp = new long[N + 1][N + 1]; dp[0][0] = 1; for (int i = 0; i < N; i++) { for (int usedOne = 0; usedOne < N; usedOne++) { int r = right[i]; int restOne = sum[r] - usedOne; if (restOne < 0) continue; if (restOne > 0) dp[i + 1][usedOne + 1] = (dp[i + 1][usedOne + 1] + dp[i][usedOne]) % MOD; if (r - i + 1 != restOne) dp[i + 1][usedOne] = (dp[i + 1][usedOne] + dp[i][usedOne]) % MOD; } } out.println(dp[N][sum[N - 1]]); } public static void main(String[] args) { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); new Main().solve(in, out); in.close(); out.close(); } }
Codeforces Round #385 (Div. 1) B. Hongcow's Game
問題
http://codeforces.com/contest/744/problem/B
n x n の行列があります。行列の要素は全て非負整数で、対角成分はすべて0です。この行列に対して、n以下の自然数の集合Sをクエリとして投げると、各行についてとなる x 列目の要素のうち最小のものを返します。20クエリ以内で各行の対角成分以外の最小値を求めてください。
解法
集合Sをクエリとして投げた時に返ってくる数列 のうち、
は i 行目の最小値である可能性があります。つまり、j 行目の最小値が知りたいときは j を含まない集合 S をいくつか作り、かつ、それらの和集合が j 以外の全ての n 以下の自然数を含むようにしなければなりません。
を j と i ビット目が異なる自然数の集合とします。
は j を含みませんが、j 以外の 10 ビット以下のすべての自然数を含みます。n は 1000 以下で 10 ビット以内に収まるので、各jについて上記のような和集合をクエリとして投げれば良いです。
コード
import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; import java.util.TreeSet; public class B { private void solve(Scanner in, PrintWriter out) { int N = in.nextInt(); int[] ans = new int[N]; Arrays.fill(ans, Integer.MAX_VALUE); TreeSet<Integer>[] sets = new TreeSet[2]; for (int i = 0; i < 2; i++) sets[i] = new TreeSet<>(); for (int i = 0; i < 10; i++) { sets[0].clear(); sets[1].clear(); for (int j = 0; j < N; j++) { sets[(j >> i) & 1].add(j); } if (!sets[0].isEmpty()) { query(sets[0]); read(sets[0], ans, in); } if (!sets[1].isEmpty()) { query(sets[1]); read(sets[1], ans, in); } } System.out.println(-1); for (int a : ans) System.out.print(a + " "); System.out.println(); } private void query(TreeSet<Integer> s) { System.out.println(s.size()); for (int a : s) System.out.print((a + 1) + " "); System.out.println(); } private void read(TreeSet<Integer> s, int[] ans, Scanner in) { int N = ans.length; for (int j = 0; j < N; j++) { int x = in.nextInt(); if (!s.contains(j)) ans[j] = Math.min(ans[j], x); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); new B().solve(in, out); in.close(); out.close(); } }
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輌を率いて、プラウダとグロリアーナの戦車をまとめて足止めしています。
このように、黒森峰戦でも西住隊長のナカジマやレオポンさんチームへの厚い信頼が感じられましたが、エキシビションではハッキリと右腕のような存在になったのではないかと思います。最終章でも活躍が楽しみですね。
自動車部として輝く瞬間
さて、安定感があって西住隊長からの信頼も厚いという面を取り上げましたが、やはり自動車部、魔改造ポルシェティーガーで爆走するシーンは最高ですよね！
冷静さや頼もしさを備えつつ、マシンへの情熱も燃やすナカジマの魅力が存分に感じられる良いシーンです。「いけっ！超音速の貴公子！！」
おわりに
出るのが遅かったけど自動車部は全体的にいいキャラですよね。
