プログラミングを上達させたい

情報学専攻の大学院→放送局でCMの営業など@大阪→舞台俳優&IT営業@東京

AtCoder Beginner Contest 183 に出ました

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で書く方が楽だと感じます。

A問題

指示通りに書きました。

(define n (read))
(display
 (if (>= n 0) n 0))
(newline)

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)でした・・・以前より厳しくないですか(近い順位に緑の人がたくさんいた)?頑張ろう。