2週間連続でRatedなコンテストに出ました。本日はBeginnerの方です。
atcoder.jp
先週はスパッと500点問題が解けたので本日も5完するぞと意気込むも・・・残念ながら4完で終わりました。しかもペナルティ2回。そのうち1回はとてもしょうもないミス。悔しい・・・
3問目まではScheme、4問目のみJavaで解きました。
A問題
実際に昇順に並び替えて、等差になっているか確かめました。(third list)便利ですね。
#lang racket (define (readN n) (if (= n 0) '() (let ((ele (read))) (cons ele (readN (- n 1)))))) (define Seq (sort (readN 3) <)) (display (if (= (- (third Seq) (second Seq)) (- (second Seq) (first Seq))) "Yes" "No")) (newline)
B問題
自分で比較関数を作って並び替え。
最初、山の名前を受け取るところを
(name (symbol->string (read))
を書いて提出してしまいました。これは山の名前が全て数字だった場合にREに・・・。
ということで、ここで1ペナルティでした。
#lang racket (define N (read)) (define (readN n) (if (= n 0) '() (let ((name (read)) (ele (read))) (cons (list name ele) (readN (- n 1)))))) (define (tall>? x y) (> (second x) (second y))) (display (first (second (sort (readN N) tall>?)))) (newline)
C問題
得意のpermutationsで全候補生成してチェック。
各数字についてチェックする関数(check ~~)がうまく書けました。
#lang racket (define Str (symbol->string (read))) (define (have? nums ele) (if (null? nums) #f (or (= (car nums) ele) (have? (cdr nums) ele)))) (define (check nums) (define (sub i) (if (>= i 10) #t (let ((nowch (string-ref Str i))) (cond ((char=? nowch #\o) (and (have? nums i) (sub (+ i 1)))) ((char=? nowch #\x) (and (not (have? nums i)) (sub (+ i 1)))) (#t (sub (+ i 1))))))) (sub 0)) (define (solve numslist) (define (sub nlist ans) (if (null? nlist) ans (sub (cdr nlist) (+ ans (if (check (car nlist)) 1 0))))) (sub numslist 0)) (define (p-generate count list) (define (e-l ele lislis) (if (null? lislis) '() (cons (cons ele (car lislis)) (e-l ele (cdr lislis))))) (define (multi-list listA listB) (if (null? listA) '() (append (e-l (car listA) listB) (multi-list (cdr listA) listB)))) (define (p-list count base ans) (if (= count 0) ans (p-list (- count 1) base (multi-list base ans)))) (p-list count list '(()))) (display (solve (p-generate 4 '(0 1 2 3 4 5 6 7 8 9)))) (newline)
D問題
配列配列した問題なのでこれだけJavaで。
入力のときの符号を逆転させることで先手と後手を統一的に扱えると思い、ScoreFieldを更新していくときのmaxとminの場合分けをしていなかったため、WAになってしまいました・・・
ほんで、それを忘れていた場合にもサンプルは全て合うようになっているという・・・悔しい・・・
ということで、ここでさらに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; import java.util.TreeSet; public class Main { public static void main(String[] args) { InputReader sc = new InputReader(System.in); int h = sc.nextInt(); int w = sc.nextInt(); int[][] GameField = new int[h][w]; for(int row = 0; row < h; row++){ String nowField = sc.nextStr(); for(int col = 0; col < w; col++){ char ch = nowField.charAt(col); if(ch == '+'){ GameField[row][col] = 1; }else{ GameField[row][col] = -1; } if((row + col) % 2 == 0){ GameField[row][col] = GameField[row][col] * -1; } } } int[][] ScoreField = new int[h][w]; for(int row = 0; row < h; row++){ for(int col = 0; col < w; col++){ ScoreField[row][col] = -1000000000; } } ScoreField[h-1][w-1] = 0; for(int step = h + w; step >= 0; step--){ for(int row = 0; row < h; row++){ int col = step - row; if(row < 0 || row >= h || col < 0 || col >= w || (row == h - 1 && col == w - 1)){ continue; }else{ if(row == h - 1){ ScoreField[row][col] = ScoreField[row][col+1] + GameField[row][col+1]; }else if(col == w - 1){ ScoreField[row][col] = ScoreField[row+1][col] + GameField[row+1][col]; }else{ if((row + col) % 2 == 0){ ScoreField[row][col] = Math.max(ScoreField[row][col+1] + GameField[row][col+1], ScoreField[row+1][col] + GameField[row+1][col]); }else{ ScoreField[row][col] = Math.min(ScoreField[row][col+1] + GameField[row][col+1], ScoreField[row+1][col] + GameField[row+1][col]); } } } } } // for(int i = 0; i < h; i++){ // for(int j = 0; j < w; j++){ // System.out.print(GameField[i][j]); // System.out.print(" "); // } // System.out.println(""); // } // for(int i = 0; i < h; i++){ // for(int j = 0; j < w; j++){ // System.out.print(ScoreField[i][j]); // System.out.print(" "); // } // System.out.println(""); // } if(ScoreField[0][0] > 0){ System.out.println("Takahashi"); }else if(ScoreField[0][0] == 0){ System.out.println("Draw"); }else{ System.out.println("Aoki"); } } //ここからテンプレ 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完 = 1000点、タイムは82分09秒(72分09秒＋ペナルティ2回)でした。
一応D問題解き終わってから30分弱残っていたのですが、E問題の木の問題は手も足もでず・・・
xorの結合則とかを利用するのかな、とか思っても、木やグラフの典型手法がまだまだ分からないです。ACが足りてない。
ということで、引き続き競プロ典型90問を解いていきます。
明日のRegularContestも都合が合えば出たいな。やはりタイムリミットの緊張感の中で解くのはとてもいいことだと思うので。
