AtCoder Regular Contest 119に出ました

2日連続でRatedなコンテストに出ました。最近コンテスト多くて嬉しい。
出たのはAtCoder Regular Contest 119です。
atcoder.jp

A問題が300点、B、C問題が500点、という配点だったので、A問題をはやく解く＆BかCのうちどちらかが解ければ・・・という目標で挑みました。

結果としては、
・A問題→10分でAC(ペナルティなし)
・B問題→30分くらい考えたり実装してみるも途中で行き詰まり・・・
・C問題→113分でAC(ペナルティ2回=10分)
ということで、800点(123分)というスコアでした！目標達成です！！！！
よかったよかった。
というわけで、方針とコードです。解けた2問はどちらともschemeで解きました。

A問題

N=1,2,3,,,という小さいケースを試した後、a,b,cの中で一番計算結果に影響が大きいbを中心に考えればよさそう、ということで実装。
bを決め→そのbに対し最大となるaを決め→cを決める、でbを探索していきました。
小さいケースからテストケースまで正しい出力が出ることを確かめて提出→無事AC。

#lang racket
(define N (read))
(define (pow2 n)
  (if (= n 0) 1
      (* 2 (pow2 (- n 1)))))
(define (calc a b c) (+ (* a (pow2 b)) c))
(define (solve)
  (define (sub b ans)
    (let ((b2 (pow2 b)))
      (if (> b2 N) ans
          (sub (+ b 1) (min ans (+ (quotient N b2) b (modulo N b2)))))))
  (sub 0 100000000000))
(display (solve))
(newline)

C問題

一旦ビルの高さがマイナスになってしまうことも許容して、左から順に見ていくとします。
たとえば

3 5 1 8 10 2

という範囲を0にしてみようとするなら、左から、右隣のものも一緒に操作して、

0 2 1 8 10 2
0 0 -1 8 10 2
0 0 0 9 10 2
0 0 0 0 1 2
0 0 0 0 0 1

という感じですね。
そして、左隣の操作が終わったときの自分の値、という配列を考えます。これを"差配列"=salistと呼ぶことにします。
上記のところでいう、3、2、-1、9、1、1です。
※一番左の値は、もとの高さをそのまま使う
そして、テストケース1〜3や、自分で考えたケース(「2,4,2」など)を試していくと、
・salist[i] - salist[j] == 0 && (i % 2) == j % 2であるi、jのペア
・salist[i] + salist[j] == 0 && (i % 2) != j % 2であるi、jのペア
が答えになりそうだ、と気付きました(厳密な証明はナシ)。
そして実際にsalistで出てくる数字をhash管理し、実装→テストケースを試すと、全部合っている・・・！
ということで、下記のコードを提出してみました・・・がTLE。

#lang racket
(define (break) (display ""))
(define N (read))
(define (readN n)
  (if (= n 0) '()
      (let ((ele (read)))
        (cons ele (readN (- n 1))))))
(define INPUT (cons 0 (readN N)))
(define (make-salist lis)
  (define (sub prev-val numlis)
    (if (null? numlis) '()
        (let ((nowval (- (car numlis) prev-val)))
          (cons nowval (sub nowval (cdr numlis))))))
  (sub 0 lis))
(define Savec (list->vector (make-salist INPUT)))
(define Table (make-hash))
(define (update-table)
  (define (sub i)
    (if (> i N) (break)
        (let ((nowval (vector-ref Savec i)))
          (if (hash-has-key? Table nowval)
              (begin
                (hash-set! Table nowval (cons i (hash-ref Table nowval)))
                (sub (+ i 1)))
              (begin
                (hash-set! Table nowval (list i))
                (sub (+ i 1)))))))
  (sub 0))
(update-table)
(define (ans-count nownum numlist mod)
  (if (null? numlist) 0
      (+ (ans-count nownum (cdr numlist) mod) (let ((num (car numlist))) (if (and (< nownum num) (= (modulo (- num nownum) 2) mod)) 1 0)))))
(define (solve)
  (define (sub i ans)
    (if (> i N) ans
        (let* ((nowval (vector-ref Savec i))
               (minusval (- 0 nowval)))
          (sub (+ i 1) (+ ans (ans-count i (hash-ref Table nowval) 0) (if (hash-has-key? Table minusval) (ans-count i (hash-ref Table minusval) 1) 0))))))
  (sub 0 0))
;(display Table)
;(newline)
(display (solve))
(newline)

関数ans-countがダメなのか？と思い、そこの判定を少し高速化して提出するも、またTLE・・・
じゃあ大幅に改善してみよう、ということで数え上げを一切なくす&数え上げも愚直にやらず計算で出すように変更して・・・無事ACでした！！！！！

#lang racket
(define (break) (display ""))
(define N (read))
(define (readN n)
  (if (= n 0) '()
      (let ((ele (read)))
        (cons ele (readN (- n 1))))))
(define INPUT (cons 0 (readN N)))
(define (make-salist lis)
  (define (sub prev-val numlis)
    (if (null? numlis) '()
        (let ((nowval (- (car numlis) prev-val)))
          (cons nowval (sub nowval (cdr numlis))))))
  (sub 0 lis))
(define Savec (list->vector (make-salist INPUT)))
(define Table (make-hash))
(define (update-table)
  (define (sub i)
    (if (> i N) (break)
        (let ((nowval (vector-ref Savec i)))
          (if (hash-has-key? Table nowval)
              (begin
                (hash-set! Table nowval (cons i (hash-ref Table nowval)))
                (sub (+ i 1)))
              (begin
                (hash-set! Table nowval (list i))
                (sub (+ i 1)))))))
  (sub 0))
(update-table)
(define (ans-count nownum numlist mod)
  (if (or (null? numlist) (> nownum (car numlist))) 0
      (+ (ans-count nownum (cdr numlist) mod) (let ((num (car numlist))) (if (and (< nownum num) (= (modulo (- num nownum) 2) mod)) 1 0)))))
(define (mod-count list mod) (if (null? list) 0 (+ (if (= (modulo (car list) 2) mod) 1 0) (mod-count (cdr list) mod))))
(define (solve2)
  (define (sub i ans)
    (if (> i N) ans
        (let* ((nowval (vector-ref Savec i))
               (minusval (- 0 nowval)))
          (if (not (hash-has-key? Table nowval)) (sub (+ i 1) ans)
              (let* ((plusindexs (hash-ref Table nowval))
                     (plus1 (mod-count plusindexs 1))
                     (plus0 (mod-count plusindexs 0))
                     (minusindexs (if (hash-has-key? Table minusval) (hash-ref Table minusval) '()))
                     (minus1 (mod-count minusindexs 1))
                     (minus0 (mod-count minusindexs 0)))
                (begin
                  (hash-remove! Table nowval)
                  (if (hash-has-key? Table minusval) (hash-remove! Table minusval) (break))
                  (if (not (= nowval 0))
                      (sub (+ i 1) (+ ans (quotient (+ (* plus1 (- plus1 1)) (* plus0 (- plus0 1)) (* minus1 (- minus1 1)) (* minus0 (- minus0 1))) 2) (* plus1 minus0) (* plus0 minus1)))
                      (sub (+ i 1) (+ ans (quotient (+ (* plus1 (- plus1 1)) (* plus0 (- plus0 1)) (* plus1 minus0) (* plus0 minus1)) 2))))))))))
  (sub 0 0))

(display (solve2))
(newline)

ここで残り数分ということで、あえなく終了。
B問題は、符号の正負をうまく扱う(i-j区間の正負を逆転させる管理)が必要そうなのですが、思い至らないため断念しました。

というわけで、無事800点まで取れました。果たしてパフォーマンスはどうなるか・・・
青を目指している身としては、1600超えてると嬉しいです。