久々にAtCoderやりました。
abc101.contest.atcoder.jp
途中から参戦して、3問目まで解けました。4問目は解けず・・・4問目解けた人は、Beginnerの方にはほとんどいませんでした。数学的な問題で、取り組みがいがありました。
1〜3問目までの解答と、4問目も思考の経過を書きます。全部Java。いつもの長ったらしいテンプレ部分も書いてます。ご了承下さい。
1問目
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); String n = sc.nextStr(); int ans = 0; for(int i = 0; i < n.length(); i++){ if(n.charAt(i) == '+'){ ans++; }else{ ans--; } } System.out.println(ans); } //ここからテンプレ 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問目
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(); int m = n; int s = 0; while(m > 0){ s += m % 10; m /= 10; } if(n % s == 0){ System.out.println("Yes"); }else{ System.out.println("No"); } } //ここからテンプレ 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); } } }
3問目
最期の状態を考えてみると、結局全部1になるわけですね。
コーナーケースとして、「1がはじっこにあるもの」と、下記のようなケースに注意です。
7 3 2 3 6 1 5 4 7
※この場合、
2 3 6 1 5 4 7 2 3 1 1 1 4 7 1 1 1 1 1 4 7 1 1 1 1 1 1 1
と3回でできます。
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(); int k = sc.nextInt(); int[] nums = new int[n]; int oneind = 0; for(int i = 0; i < n; i++){ nums[i] = sc.nextInt(); if(nums[i] == 1){ oneind = i; } } int ans = 0; int yoyuu1 = 0; int yoyuu2 = 0; for(int i = 0; i < oneind; i += k - 1){ ans++; yoyuu1 = i + k - 1; } for(int i = n - 1; i > oneind; i -= k - 1){ ans++; yoyuu2 = i - k + 1; } if(yoyuu1 - yoyuu2 >= k - 1){ ans--; } if(oneind == n - 1){ ans++; } System.out.println(ans); } //ここからテンプレ 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); } } }
コーナーケース処理が一部ちゃんとできておらず、強引な書き方になりました。
4問目の途中経過(解けず・・・)
とりあえず、下記のようなコードを書いて、ideoneで試しました。
単純に全部試していくコードです。
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(); int count = 0; double[] nums = new double[n + 1]; nums[0] = 0.0; for(int i = 1; i < n + 1; i++){ int ketawa = 0; int j = i; while(j > 0){ ketawa += j % 10; j /= 10; } nums[i] = (double)i / (double)ketawa; } for(int i = 1; i < n; i++){ boolean check = true; for(int j = i + 1; j < n; j++){ if(nums[i] > nums[j]){ check = false; } } if(check){ System.out.println(i); } } } //ここからテンプレ 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); } } }
入力を1000000にしたら、こんな感じででてきました。
1 2 3 4 5 6 7 8 9 19 29 39 49 59 69 79 89 99 199 299 399 499 599 699 799 899 999 1099 1199 1299 1399 1499 1599 1699 1799 1899 1999 2999 3999 4999 5999 6999 7999 8999 9999 10999 11999 12999 13999 14999 15999 16999 17999 18999 19999 20999 21999 22999 23999 24999 25999 26999 27999 28999 29999 39999 49999 59999 69999 79999 89999 99999 109999 119999 129999 139999 149999 159999 169999 179999 189999 199999 209999 219999 229999 239999 249999 259999 269999 279999 289999 299999 309999 319999 329999 339999 349999 359999 369999 379999 389999 399999 499999 599999 699999 799999 899999 999999
とここでギブアップ。規則性を見つけられそうで見つけられず・・・
残念でした。
でも、久々にガッツリ目の問題に長く取り組めて楽しかったです。
それでは、CodingGameに戻ります。