notepad

いろいろ書くメモ帳

ABC006を解いた

今回はAtCoder Beginner Contest 006を解きました. 公式解説はこちら

A 世界のFizzBuzz

自力完答
アホになるやつ.3で割りきれるか,3を含んでいるかを判定すれば良い. 文字列処理が簡単な言語だとすぐできる.

B トリボナッチ数列

自力完答
動的計画法を使えば簡単.DPテーブルに格納する数値を,10007で割った余りにしておくことがポイント. そうしないと計算途中で桁あふれが起こってしまう.

C スフィンクスのなぞなぞ

自力では解けず.解説見て100点
総当りで解こうとしたものの,WAがでて解けず.解説を読むと,どうやら鶴亀算の問題だったらしい. 老人2人 = 大人1人 + 子供1人であるため,老人が0人の場合と1人の場合のみ調べれば良い. これに気づくことができれば,後は連立方程式を解くだけ.C問題なのに難しくない?

D トランプ挿入ソート

自力では解けず.解説見て100点
馬鹿正直に挿入ソートを実装して入れ替え回数をカウントしてみたものの,もちろん通らず. 「最小の操作回数を求めよ」ってのが強敵だった. この問題は最長増加部分列(LIS)というアルゴリズムを使うことで解けるらしい. 名前は聞いたことがあったが,このアルゴリズムを使うという発想に至らなかった.

最長増加部分列のアルゴリズムについてはAOJのページを参考にした.
最長増加部分列 | 動的計画法 | Aizu Online Judge

まずは単純な動的計画法を使ったアルゴリズムで実装した.ただし,このアルゴリズムだと O(n^2)なので,実行速度が足りずに50点しかもらえない.

最大値を求めている部分がボトルネックになっているので,この部分を二分探索で求めるようにしたのがこちら. 二分探索を使ったので,計算量は O(n \log{n})になり,満点がもらえる.

整数値の二分探索については,こちらのページを参考にした.
整数二分探索 | アルゴリズムメモ

感想

C問題を解けなかったことが悔しいので,もっと勉強したいと思います.