2ヶ月ちょいぶりに、リアルタイムでコンテストに出ました。出ました達郎
atcoder.jp
前回、E問題(500点)、F問題(600点)が解けたので、今回もE以降を解くぞと意気込んだものの、結果としてはA〜D問題の4完(48分)でした。E問題、解けそうと思いながらも解けず・・・・Dはなんだかんだで(時間はかかったものの)一発ACだったので、D問題の速度をアップさせるのとE問題が解ける確率をあげるように進めていきたいです(AtCoder ProblemsのTrainingモードというのを知ったので、それ進めようと思います)。
それでは、解法とコードを書いていきます。A,C,DはSchemeで、BはJavaで解きました。最近は、文法の縛りが少ないSchemeで書く方が楽だと感じます。
B問題
数学的に、比を使って解きました。この書き方だと、S_xとG_xのどちらが大きいかに関係なくちゃんと答えが出ます。doubleとか使う時少しドキドキします。
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 sx = sc.nextInt(); int sy = sc.nextInt(); int gx = sc.nextInt(); int gy = sc.nextInt(); double susumu = (double)sy / (double) (sy+gy); double ans = (double)sx + (double)(gx-sx) * susumu; 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); } } }
C問題
全探索で解きました。順列を生成する関数を使って書いています("permutation-list"というやつ)。
(define N (read)) (define K (read)) (define (readN n) (if (= n 0) '() (let* ((ele (read))) (cons ele (readN (- n 1)))))) (define distvec (list->vector (readN (* N N)))) (define (permutations-list ls) (define (fold-right fn a ls . args) (if (null? args) (letrec ((recr (lambda (a ls) (if (null? ls) a (fn (car ls) (recr a (cdr ls))))))) (recr a ls)) (letrec ((recr (lambda (a xs) (if (member? '() xs) a (apply fn (append (map car xs) (list (recr a (map cdr xs))))))))) (recr a (cons ls args))))) (define (remove func list) (cond ((null? list) list) ((func (car list)) (remove func (cdr list))) (#t (cons (car list) (remove func (cdr list)))))) (define (remove-item x ls) (remove (lambda (a) (equal? a x)) ls)) (define (perm ls a b) (if (null? ls) (cons (reverse a) b) (fold-right (lambda (x y) (perm (remove-item x ls) (cons x a) y)) b ls))) (perm ls '() '())) (define (dist a b) (vector-ref distvec (+ (* a N) b))) ;aとbには0〜(n-1)が入る想定 (define (generate-list n) (if (= n 0) '() (cons n (generate-list (- n 1))))) ;1~nまで作る (define all-route (permutations-list (generate-list (- N 1)))) (define (add0-first list) (cons 0 list)) (define (add0-last list) (if (null? list) '(0) (cons (car list) (add0-last (cdr list))))) (define (calc list) (if (null? (cdr (cdr list))) 0 (+ (dist (car list) (car (cdr list))) (calc (cdr list))))) (define (calc-dist list) (calc (add0-first (add0-last (add0-last list))))) (define (solve route-list) (if (null? route-list) 0 (+ (if (= (calc-dist (car route-list)) K) 1 0) (solve (cdr route-list))))) (display (solve all-route)) (newline)
D問題
累積和を使って解きました。Schemeでベクトル(=配列)を使うことがないので、関数を調べたり動作を確認したりで少し時間がかかりました。
(define N (read)) (define W (read)) (define (first list) (car list)) (define (second list) (car (cdr list))) (define (third list) (car (cdr (cdr list)))) (define (read-N3 n) (if (= n 0) '() (let* ((e1 (read)) (e2 (read)) (e3 (read))) (cons (cons e1 (cons e2 (cons e3 '()))) (read-N3 (- n 1)))))) (define diff-vec (make-vector 200005 0)) (define (diff-check list) (if (null? list) 0 (let* ((ele (car list)) (s (first ele)) (t (second ele)) (p (third ele)) (s-val (vector-ref diff-vec s)) (t-val (vector-ref diff-vec t))) (begin (vector-set! diff-vec s (+ s-val p)) (vector-set! diff-vec t (- t-val p)) (diff-check (cdr list)))))) (diff-check (read-N3 N)) (define tatami-vec (make-vector 200006 0)) (vector-set! tatami-vec 0 0) (define (tatami index);index = 1から (if (>= index 200006) 0 (begin (vector-set! tatami-vec index (+ (vector-ref tatami-vec (- index 1)) (vector-ref diff-vec (- index 1)))) (tatami (+ index 1))))) (tatami 1) (define (over-check) (define (sub i) (if (>= i 200006) #t (and (<= (vector-ref tatami-vec i) W) (sub (+ i 1))))) (sub 1)) ;(display tatami-vec) ;(newline) (display (if (over-check) "Yes" "No")) (newline)
以上の4問が制限時間内に解けたものです。
E問題は一応実装し終えたのですが、計算が合わず・・・考える時間を確保するためにも、もう少し早くD問題まで解けていたら結果が違ったかもしれません。
日常的に解く量を増やしながら、青色目指して実力を伸ばしていきます。
あまりレーティング下がりませんように・・・
P.S. パフォーマンス982、新レーティングは1284(-31)でした・・・以前より厳しくないですか(近い順位に緑の人がたくさんいた)?頑張ろう。