AtCoder Grand Contest 023 に出ました。
AtCoder Grand Contest 023 - AtCoder Grand Contest 023 | AtCoder
結果は2問正解でした。
AtCoderのレーティングについて、なんか出始めて序盤(10回以内くらい)はレーティングが低く出る傾向にあるらしいので、頑張って出場していこうと思います。
さて、とりあえず2問分のコード。
1問目。
A: Zero-Sum Ranges - AtCoder Grand Contest 023 | AtCoder
2回WAを出しながら、何とか正答しました。というのも、2回のWAの原因がどっちともintの桁オーバーという・・・もったいない!気を付けよう!
解説動画(下記)では、累積和を取る⇒各地点での累積和をソート⇒同じ数のものがいくつあるか、コンビネーション取りながら数え上げ、でした。
https://www.youtube.com/watch?v=8BHBFMrZ8VM
ただ、そういうやり方が思いつかず、別のやり方で解きました。おそらく上記解説動画でも、僕の解き方でも、オーダーは n * log(n) かと思います。
僕の解き方は、
1.まず、「合計が0のケースが1回あった」をメモ
2.数字を読み込む毎にそれまでの累積和を計算し、「それより前の累積和で同じ数字が出たか?」をチェック
という進め方です。
はじめからn番目までの和がSで、それまでに累積和がSになっていることが2回あった場合、このタイミングで"和が0になる連続した部分列"が2つ見つかったことになりますね、ということです。
コードは下記のような感じ。割とシンプルなコードにできたかと…!
初めてTreeMapという構造を使いました。
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.TreeSet; import java.util.TreeMap; import java.math.*; public class Main { public static void main(String[] args) { InputReader sc = new InputReader(System.in); int n = sc.nextInt(); long sum = 0; TreeMap<Long,Long> counters = new TreeMap<>(); counters.put((long)0,(long)1); long count = 0; for(int i = 0; i < n; i++){ sum += sc.nextInt(); if(counters.containsKey(sum)){ long nowcount = counters.get(sum); count += nowcount; counters.remove(sum); counters.put(sum, nowcount + 1); }else{ counters.put(sum, (long)1); } } System.out.println(count); } //ここからテンプレ static class InputReader { private InputStream stream; private byte[] buf = new byte[1024]; private int curChar; private int numChars; private SpaceCharFilter filter; public InputReader(InputStream stream) { this.stream = stream; } public int next() { if (numChars == -1) throw new InputMismatchException(); if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } public String nextStr() { int c = next(); while(isSpaceChar(c)){c = next();} StringBuffer str = new StringBuffer(); do{ str.append((char)c); c = next(); }while(!isSpaceChar(c)); return str.toString(); } public char nextChar() { int c = next(); while(isSpaceChar(c)){c = next();} char ret; do{ ret = (char)c; c = next(); }while(!isSpaceChar(c)); return ret; } public int nextInt() { int c = next(); while (isSpaceChar(c)) c = next(); int sgn = 1; if (c == '-') { sgn = -1; c = next(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res *= 10; res += c - '0'; c = next(); } while (!isSpaceChar(c)); return res * sgn; } public boolean isSpaceChar(int c) { if (filter != null) return filter.isSpaceChar(c); return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } public interface SpaceCharFilter { public boolean isSpaceChar(int ch); } } }
2問目。
B: Find Symmetries - AtCoder Grand Contest 023 | AtCoder
こちらは、とりあえず全探索でやってTLEになったあと、1段階オーダーを落として解けました。
解説動画と同じ解き方かと。
https://www.youtube.com/watch?v=8BHBFMrZ8VM
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; import java.util.LinkedList; import java.util.PriorityQueue; public class Main { public static void main(String[] args) { InputReader sc = new InputReader(System.in); int n = sc.nextInt(); String[] strings = new String[n]; for(int i = 0; i < n; i++){ strings[i] = sc.nextStr(); } char[][] banmen = new char[n][n]; int count = 0; for(int a = 0; a < n; a++){ // for(int b = 0; b < n; b++){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ banmen[(i + a) % n][j] = strings[i].charAt(j); } } boolean clear = true; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(banmen[i][j] != banmen[j][i]){ clear = false; break; } } } if(clear){ count += n; // } } } System.out.println(count); } //ここからテンプレ static class InputReader { private InputStream stream; private byte[] buf = new byte[1024]; private int curChar; private int numChars; private SpaceCharFilter filter; public InputReader(InputStream stream) { this.stream = stream; } public int next() { if (numChars == -1) throw new InputMismatchException(); if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } public String nextStr() { int c = next(); while(isSpaceChar(c)){c = next();} StringBuffer str = new StringBuffer(); do{ str.append((char)c); c = next(); }while(!isSpaceChar(c)); return str.toString(); } public char nextChar() { int c = next(); while(isSpaceChar(c)){c = next();} char ret; do{ ret = (char)c; c = next(); }while(!isSpaceChar(c)); return ret; } public int nextInt() { int c = next(); while (isSpaceChar(c)) c = next(); int sgn = 1; if (c == '-') { sgn = -1; c = next(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res *= 10; res += c - '0'; c = next(); } while (!isSpaceChar(c)); return res * sgn; } public boolean isSpaceChar(int c) { if (filter != null) return filter.isSpaceChar(c); return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } public interface SpaceCharFilter { public boolean isSpaceChar(int ch); } } }
以上です。
頑張ってレーティングあげてくぞー!