AtCoder Regular Contest 118 に出ました

久々にRatedなコンテストに出ました！しかもレギュラーコンテストです。
atcoder.jp

得点がA-300、B-400、C-500ということで、
・WAやTLEなしでBまでをなるべく早く解く
・できればCも解きたい
・D以降は高得点問題だが、時間内は粘りたい
という方針でした。

結果としては、無事にA〜Cの3問をミスなくACでき、それぞれ開始から
A問題-15分後
B問題-45分後
C問題-85分後
にACとなりました。
B問題が、考え違いでのやり直し＆実装＆ミスないかチェックに時間がかかりました・・・
全体を通して問題の中に出てくるのは数列くらいとかのシンプルな問題文が多く、苦手である「なんか知らんデータ構造を使うんやろな・・」みたいな問題がなくて新鮮でした。とはいえC問題を解いたあとに取り組んだDもFもさっぱり糸口が見えませんでしたが・・・

では、A〜C問題の解答の方針とコードをまとめていきます。
全てracket(scheme)で解きました。
本当にどうでもいいことですが、全問題を通して、racketで提出したのは僕一人でした。嬉しい。

A問題

消費税t%でA円の税込み価格は floor ((100+t) * A / 100)となります。
自明なこととして、
0円のとき→0円
100円のとき→(100+t)円
200円のとき→(100+t) * 2 円
・・・
となります。
よって、
・商品が0円〜99円のときの場合を計算して、出てこない金額を求める
・それ以降はそれに(100+t)*n円を足したものが続いていく
となります。

#lang racket
(define t (read))
(define N (read))
(define (generate-value)
  (define (sub i)
    (if (>= i 100) '()
        (cons (inexact->exact (floor (/ (* (+ 100 t) i) 100))) (sub (+ i 1)))))
  (sub 0))
(define (generate-nums)
  (define (sub i)
    (if (>= i (+ 100 t)) '()
        (cons i (sub (+ i 1)))))
  (sub 0))
(define NoNum (sort (set->list (set-symmetric-difference (list->set (generate-value)) (list->set (generate-nums)))) <))
(define (list-pick lis i) (if (<= i 1) (car lis) (list-pick (cdr lis) (- i 1))))
 
(let*
    ((listlen (length NoNum))
     (loop (quotient (- N 1) listlen))
     (mod (+ 1 (modulo (- N 1) listlen))))
  (display (+ (* (+ 100 t) loop)  (list-pick NoNum mod))))
(newline)

B問題

問題文がややこしいですが、割とそのまま実装しました。
・まず、各段位の人数を M/N倍したもののfloorを暫定の回答とする
・そうすると、合計人数がM人から少し足りない
・最小化したいスコア(絶対値のやつ)が大きい順に、不足している人数分の段位について暫定回答に1人足していく
という方針です。
ぐちゃぐちゃしたコードですが、最後に行う2回のソートを高階関数を使ってキレイに書けたのは嬉しかったです。

Copy
#lang racket
(define K (read))
(define N (read))
(define M (read))
(define (readN n)
  (define (sub i)
    (if (> i n) '()
        (let ((ele (read)))
          (cons (list i ele) (sub (+ i 1))))))
  (sub 1))
(define (trans pair)
  (let* ((ind (car pair))
         (val (car (cdr pair)))
         (secondval (if (= (modulo (* val M) N) 0) (quotient (* val M) N)
                  (/ (* val M) N)))
         (seisu (floor secondval))
         (sa (abs (- (/ seisu M) (/ val N)))))
    (list ind seisu sa)))
;(display (map (lambda (x) (trans x)) (readN K)))
(define (pick lis i) (if (<= i 1) (car lis) (pick (cdr lis) (- i 1))))
(define (ith-comp? comp i) (lambda (a b) (comp (pick a i) (pick b i))))
;(display (sort (map (lambda (x) (trans x)) (readN K)) (ith-comp? >= 3)))
(define (to-upper i lislis)
  (if (= i 0) lislis
      (let* ((nowlist (car lislis))
             (newlist (list (pick nowlist 1) (+ 1 (pick nowlist 2)) (pick nowlist 3))))
        (cons newlist (to-upper (- i 1) (cdr lislis))))))
(define (sum-i i lislis) (if (null? lislis) 0 (+ (pick (car lislis) i) (sum-i i (cdr lislis)))))
(define (display-i i lislis)
  (if (null? lislis) (display "")
      (begin
        (display " ")
        (display (pick (car lislis) i))
        (display-i i (cdr lislis)))))
(let*
    ((sorted (sort (map (lambda (x) (trans x)) (readN K)) (ith-comp? >= 3)))
     (ans-list (sort (to-upper (- M (sum-i 2 sorted)) sorted) (ith-comp? <= 1))))
  (display (pick (car ans-list) 2))
  (display-i 2 (cdr ans-list)))
(newline)

C問題

答えの各数字を全て10000以下にしなきゃいけないのにN<=2500!?と最初ビビりました。
条件を満たすような集合を構成する方法を色々考え、最終的に次のような構成方法に至りました。
・まず、先頭は6、10、15(この3つの数の最大公約数は1、そしてそれぞれ共通する素数(2or3or5)を因数として持つ)
・そのあとは、6、10、15の倍数を何でもいいから付けていく(重複ないよう注意！)
という構成方法です。
これにより、2600個ちょいくらいまでは構成することができ、かつ条件を満たします。
重複を除くのを(set->list (list->set numlist))で簡単に書けたりと、schemeのおかげで実装は簡単でした。
皆もschemeを使おう！！！

#lang racket
(define N (read))
(define (generateN n)
  (define (sub i)
    (if (> i n) '()
        (cons i (sub (+ i 1)))))
  (sub 2))
(define (delete ele lis)
  (if (null? lis) '()
      (if (= (modulo (car lis) ele) 0) (delete ele (cdr lis))
          (cons (car lis) (delete ele (cdr lis))))))
(define (erat n)
  (define (sub numlist)
    (if (null? numlist) '()
        (cons (car numlist) (sub (delete (car numlist) numlist)))))
  (sub (generateN n)))
(define seed (list 6 10 15))
(define (extend ele)
  (define (sub index)
    (if (> (* ele index) 10000) '() (cons (* ele index) (sub (+ index 1)))))
  (sub 2))
(define (pick-n lis n)
  (if (= n 0) '()
      (cons (car lis) (pick-n (cdr lis) (- n 1)))))
(define Ans (pick-n (append seed (set->list (list->set (append (extend 6) (extend 10) (extend 15))))) N))
(define (display-list lis)
  (if (null? lis) (display "")
      (begin
        (display " ")
        (display (car lis))
        (display-list (cdr lis)))))
(display (car Ans))
(display-list (cdr Ans))
(newline)

D問題

1〜P-1のそれぞれの整数をノードとし、条件の等式が成り立つ数字間にエッジを張って・・・とグラフにしてみたものの、ハミルトン閉路があるかどうかは簡単にできないやつじゃん・・・と調べてションボリして終わり。
素数の性質を使うのか？
30分ほど向き合った問題なので、解説見て実装したい。

というわけで

競プロ典型90問に取り組んでいるからか、問題に向き合う集中力や実装力が上がっているように感じます。
自分のレベルに合った&自分の弱点克服にぴったりの企画なんで、引き続き進めていきたいです。

書いてる間に結果が出ました

パフォーマンス:1755(青パフォ！)
レーティング:1284 → 1343 (+59) Highest更新！
ということで、目標である青のパフォーマンスに届く結果となりました！嬉しい！
続けていくぞ！！！オラオラ！！！！！！！！！！！！！！！！！！！！！！！