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
まずは単純な動的計画法を使ったアルゴリズムで実装した.ただし,このアルゴリズムだとなので,実行速度が足りずに50点しかもらえない.
最大値を求めている部分がボトルネックになっているので,この部分を二分探索で求めるようにしたのがこちら. 二分探索を使ったので,計算量はになり,満点がもらえる.
整数値の二分探索については,こちらのページを参考にした.
整数二分探索 | アルゴリズムメモ
感想
C問題を解けなかったことが悔しいので,もっと勉強したいと思います.