AtCoder Beginner Contest 037 参加しました

アルゴリズムの勉強ということで、5/7 21:00 から行われた AtCoder Beginner Contest 037 に参加してみました。

Welcome to AtCoder Beginner Contest 037 - AtCoder Beginner Contest 037 | AtCoder

スキルについて

  • 1年ほど前にpaizaに登録してAランク取得
  • プログラミングコンテストチャレンジブックの初級編の半分ぐらい読んだ
  • AtCoder Beginner Contest の過去問を2ぐらい解いてみた

主な武器はプログラミングコンテストチャレンジブックで学んだDP(Dynamic Programming) の知識

結果

A, B問題は特に問題なく解けた。

C

シンプルにとくとO(KN)で100億の計算量になってしまうので、O(N)で解くやり方で提出したが後半の幾つかのケースでWrong Answerとなってしまった。(なぜWAになってしまったかは未解決)

D

唯一の武器のDPでO(HW)で解いたが Time Limit Exceed になってしまった。

生放送解説をみて

Cは3つほど解き方が紹介されていたので、WAをクリアにするために累積和の方法で解いてみた。

累積和で解けると思うまでの手順(想定)

  • 愚直のとくと計算量が多くてダメそう(O(NK)のような...)

  • 前もって数列の形式を変えることによって計算量を減らせそう(O(N)) 今回のケースだと、和を累積しておくことで、部分列の和が簡単に解ることに気づく。

Dはほど解説通りに実装できていたが、Rubyでは厳しそう? C++導入を考える?

C++ 導入に向けて

  • 開発環境を準備
  • 標準乳入力、出力方法
  • 配列,ハッシュの基本的な使い方
  • 数学に関する関数の基本的な使い方
  • 大きな数の扱いについて(longlong型で64bit intが扱えるらしい)