企業さんが主催ですが、Ratedとのことで参加しました。
atcoder.jp
絶対4完するぞ!と思いながら取り組むも、4問目であるD問題がTLEのまま終了・・・(しかも現在も理由がわかっていない)
ただ、無事レーティングはほぼ変わらずという結果になりました。D問題いつもより難しかったよね。
というわけで、D問題のTLEのコードも含め、書いていきます。A、B問題はメインの部分だけ、C、 D部分はフルなコードを書きます。
A問題
public static void main(String[] args) { InputReader sc = new InputReader(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int d = sc.nextInt(); int ans = 0; for(int i = n; i <= m; i++){ if(i % d == 0){ ans++; } } System.out.println(ans); }
シンプルに全探索で数え上げ。割り算使って高速なものにもできるが、ミスが怖くこの形に。
B問題
public static void main(String[] args) { InputReader sc = new InputReader(System.in); int n = sc.nextInt(); int ans = 0; for(int i = 0; i < n; i++){ int nownum = sc.nextInt(); if(i % 2 == 0 && nownum % 2 == 1){ ans++; } } System.out.println(ans); }
これもそのまま探索。今思うと、forループの3つ目のやつ、i++じゃなくてi=i+2にしてたらif文ももう少しシンプルに書けたし、そっちの方がミスしなさそう。
C問題
これのACが出たのが開始から9分半というタイミング。おかげで、あまりレーティングを落とさずに済みました。
Nを固定して探していくのではなく、(x,y,z)のペアを全探索→その結果できるNの値をカウントしていく
というのがポイントですね。
x^2+y^2+z^2+xy+yz+zx という、「おっ因数分解か?」みたいな式にしているのがいやらしい。
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(); int[] sums = new int[n+1]; for(int i = 1; i <= n; i++){ sums[i] = 0; } for(int x = 1; x < 101; x++){ for(int y = 1; y < 101; y++){ for(int z = 1; z < 101; z++){ int nowsum = x * x + y * y + z * z + x * y + y * z + z * x; if(nowsum <= n){ sums[nowsum]++; } } } } for(int i = 1; i <= n; i++){ System.out.println(sums[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); } } }
D問題
回答と同じように書けたと思うのですが、TLE・・・Schemeだからなのか、どこか致命的な間違いをしているのか?
あと、書きながら考えながらとSchemeを書いていくと毎回かなり汚いコードになってしまうので、そこは直したい。
ちなみに開始から70分で提出しTLEでした。
あと、複数の入力例に対してTLEとACの数がいくつだったか表示されるようになってました!このコードはAC*8、TLE*13でした。このシステム、いいですね。助かる〜
(define n (read)) (define str (read)) (define digitnum (number->string str)) (define (add0 str ketalimit) (if (>= (string-length str) ketalimit) str (add0 (string-append "0" str) ketalimit))) (define (ruijo2 i modseed) (cond ((= i 0) 1) ((= i 1) (modulo 2 modseed)) ((= (modulo i 2) 0) (let* ((half (modulo (ruijo2 (quotient i 2) modseed) modseed))) (modulo (* half half) modseed))) (#t (let* ((half (modulo (ruijo2 (quotient (- i 1) 2) modseed) modseed))) (modulo (* 2 half half) modseed))))) (define (popcount n) (cond ((= n 0) 0) ((= (modulo n 2) 0) (popcount (quotient n 2))) (#t (+ 1 (popcount (quotient n 2)))))) (define (loopcount n);一発目終わった後はこの関数使えばいい、最後に+1 (if (= n 0) 0 (+ 1 (loopcount (modulo n (popcount n)))))) (define (string-mod str modseed) (define (sub keta sum) (cond ((>= keta (string-length str)) sum) ((char=? (string-ref str keta) #\0) (sub (+ keta 1) sum)) (#t (sub (+ keta 1) (modulo (+ sum (ruijo2 (- (string-length str) (+ keta 1)) modseed)) modseed))))) (sub 0 0)) (define (count1 str) (define (sub keta sum) (cond ((>= keta (string-length str)) sum) ((char=? (string-ref str keta) #\1) (sub (+ keta 1) (+ sum 1))) (#t (sub (+ keta 1) sum)))) (sub 0 0)) (define (baseplus str) (string-mod str (+ (count1 str) 1))) (define (baseminus str) (if (<= (count1 str) 1) 0 (string-mod str (- (count1 str) 1)))) (define numberstring (add0 digitnum n)) (define basefor1 (baseminus numberstring)) (define basefor0 (baseplus numberstring)) (define have1 (count1 numberstring)) (define (solve str) (define (sub keta) (cond ((>= keta (string-length str)) 0) ((char=? (string-ref str keta) #\0) (let* ((afteroneloop (modulo (+ basefor0 (ruijo2 (- (string-length str) (+ keta 1)) (+ have1 1))) (+ have1 1))) (answer (+ 1 (loopcount afteroneloop)))) (begin (display answer) (newline) (sub (+ keta 1))))) (#t (if (= have1 1) (begin (display "0") (newline) (sub (+ keta 1))) (let* ((afteroneloop (modulo (+ (- have1 1) (- basefor1 (ruijo2 (- (string-length str) (+ keta 1)) (- have1 1)))) (- have1 1))) (answer (+ 1 (loopcount afteroneloop)))) (begin (display answer) (newline) (sub (+ keta 1)))))))) (sub 0)) (solve numberstring)
そして結果は
パフォーマンス:1228
レーティング:1238 → 1237 (-1)
でした。
9月あたりにガッツリ勉強の時間取れそうなので、青色目指してがんばっぺ