久々にリアルタイムでAtcoderのコンテストに出られたので、せっかくだしブログに。
今回のはABC033です。満点を狙うも、叶わず・・・！
しかし、時間に追われながらのコンテストはやはり楽しいですね。
仕事やらの関係で難しいですが、出られるようならたまにはやっていきたいものです。
さて、今回は3問完答+部分点 という結果でした。
3問目まではバラバラの言語で解くというよく分からん結果になりました。
解答はこんな感じ。
まずA問題。
これは単純に、入力が1111で割れるかを調べればよいですね。
"0000"(=0)が入力の場合にも上手く動くかどうかだけ、ちゃんと確かめてからSubmit。無事AC。
これはSchemeで出しました。
(define N (read)) (define ans (if (= 0 (modulo N 1111)) "SAME" "DIFFERENT")) (display ans) (newline)
次にB問題。
これも単純に調べるだけですね。
普通の数字の話＆配列が出てくるので、Javaで解きました。
毎回そのまま書いてますが、今回もバカ長いテンプレ文もそのまま載せます。
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; public class Main { public static void main(String[] args) { InputReader sc = new InputReader(System.in); int n = sc.nextInt(); String[] names = new String[n]; int[] peoples = new int[n]; int sumcount = 0; int maxcount = 0; int maxindex = 0; for(int i = 0; i < n ; i++){ names[i] = sc.nextStr(); peoples[i] = sc.nextInt(); sumcount += peoples[i]; if(peoples[i] > maxcount){ maxcount = peoples[i]; maxindex = i; } } if(maxcount * 2 > sumcount){ System.out.println(names[maxindex]); }else{ System.out.println("atcoder"); } } //ここからテンプレ 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); } } }
完答できたのはここまで、C問題。
数式がどうの、という問題です。
ただ、
・負の数が出てこない
・足しまくった結果が0
→ 全て0を足している
ということですね。
そして掛け算して1つでも0があれば積は0なので、
①足される要素に分ける
②分けたあと、掛け算のどれかの中に0が入っているかをチェック
入っていないならどれか1つを0にかえなければならない
というやり方です。
年末年始にちょろっとやろうとして、挫折したpythonで書きました。
pythonは文字列処理便利ですね。スマートに書けたと思います。
l = raw_input().split("+") count = 0 for var in range(0, len(l)): if not "0" in l[var]: count = count + 1 print count
そして完答できなかった4問目。部分点まででした。
正直、計算量を落とす方法が全く分からず・・・
解説スライドを見て勉強しようと思います。
最後に、とりあえず部分点までのコードを。Javaです。
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; class henlen implements Comparable{ int len; int smallnum; int largenum; public int compareTo(Object other){ henlen otherlen = (henlen)other; return otherlen.len - len; } } public class Main { public static void main(String[] args) { InputReader sc = new InputReader(System.in); int n = sc.nextInt(); int[] xs = new int[n]; int[] ys = new int[n]; for(int i = 0; i < n; i++){ xs[i] = sc.nextInt(); ys[i] = sc.nextInt(); } henlen[] lens = new henlen[(n * (n - 1)) / 2]; int indexcount = 0; for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ henlen nowlen = new henlen(); nowlen.len = (xs[i] - xs[j]) * (xs[i] - xs[j]) + (ys[i] - ys[j]) * (ys[i] - ys[j]); nowlen.smallnum = i; nowlen.largenum = j; lens[indexcount] = nowlen; indexcount++; } } boolean[][] checkbox = new boolean[n][n]; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ checkbox[i][j] = false; } } //見終わったものにはtrueが付く Arrays.sort(lens); int eikaku = 0; int chokkaku = 0; int donkaku = 0; for(int i = 0; i < (n * (n - 1)) / 2; i++){ int minnum = lens[i].smallnum; int bignum = lens[i].largenum; checkbox[minnum][bignum] = true; checkbox[bignum][minnum] = true; int nowx1 = xs[minnum]; int nowx2 = xs[bignum]; int nowy1 = ys[minnum]; int nowy2 = ys[bignum]; for(int j = 0; j < n; j++){ if(checkbox[j][bignum] || checkbox[j][minnum] || j == minnum || j == bignum){continue;} int naiseki = (nowx1 - xs[j]) * (nowx2 - xs[j]) + (nowy1 - ys[j]) * (nowy2 - ys[j]); if(naiseki < 0){ donkaku++; }else if(naiseki == 0){ chokkaku++; }else{ eikaku++; } } } System.out.printf("%d %d %d\n", eikaku, chokkaku, donkaku); } //nextChar を追加したよ！ //System.out.printf("? %d %d\n", i, j); // LinkedList<Integer>[] setsu = new LinkedList[n]; // for(int i = 0; i < n; i++){ // setsu[i] = new LinkedList<Integer>(); // } //ここからテンプレ 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); } } }
これからもたまにやっていければ。
Kaggleもやっていきたいですが。
以上です。
