こないだ登録したAOJについてです。プログラミング入門者ですので簡単なやつばかりですけども100問ほど解いてみました。
Pythonのリストや辞書の操作は面白いですが何回やっても理解が怪しく、毎回ググってしまいます;-o-)一度自分でまとめてみるのもいいかもしれません。
というわけで印象に残った問題をいくつか紹介してみます。解法も記していますがコードは恥ずかしくて出せません_ _)
ALDS1_1_D: Maximum Profit
問題はこちら。
最大の利益 | アルゴリズムとデータ構造 | Aizu Online Judge
刻々と変動する価格のデータRt (t=0,1,2,,,n−1)が示されます。その中で1回だけ買って必ずその後に売るということを（事後評価として）考えた場合に、最大利益はどう求められるかという問題です。
Ri<Rjという条件で2重ループして差の最大値を求めれば答えは簡単に求まるのですがそこが罠でして、題意どおり時間切れになります;-o-)
そこでループは1回とし、「現在の価格（ループで取得した価格）」と「そこまでの最低価格」を比較して最大利益を更新していくことにより最終的に正解が得られます。
要点が理解できれば10行も必要ないのですが、わからないうちは「価格が下がる一方で終わる場合の処理」（実は対応不要）などいろいろ考えてしまいますし、値の更新順序なども間違いやすく一苦労。
1173: The Balance of the World
文中の2種類のカッコ ( ) と [ ] の使い方が正しいかどうかチェックするという問題です。
The Balance of the World | Aizu Online Judge
ついついカッコの数を数えて差し引きして…とやりたくなりますが2種のカッコの咬み合いをチェックするのが難しく、わけがわからなくなります。
答えとしては ( と [ をスタックに加え ) や ] が現れたら除いていくというのが簡単です。) に対応するのが [ だったり ] に対応するのが ( だったらその場でOUT、スタックが余ったり不足してもOUT、それらがなければOKとなります。
スタックの有用な例としてとてもわかりやすいです。
ALDS1_3_D: Areas on the Cross-Section Diagram
地形の断面図から、そこにたまる水の断面積の最大値を求めるという問題です。
模式断面図の面積 | アルゴリズムとデータ構造 | Aizu Online Judge
いくら考えてもわかりません;-o-)
そこでググりましたところ、つまり＼のX座標をスタックに加えていき、その後／が見つかったらスタック末尾のX座標との差を求める（＼のX座標はスタックから除く）、ということを続けていけば断面積は求まるということが判明。／に対してスタックが空であればその／は水たまりになり得ないことを意味しており、＿の存在や「高さ」を考慮する必要も全くない…なるほどわかれば驚異的に簡単ですが、やはり知らなければ一生思いつかない気がします。
なお問題としては全体の断面積だけでなく個々の水たまりの面積を回答する必要があり、そっちの方が厄介です（自分は各水たまりの左端の座標と面積を記録するリストを作り管理しました）。
0067: The Number of Island
マップ上に島（上下左右につながっている点の集まり）がいくつあるかという問題です。
素人目でライフゲーム的な解法があるのではないかと思ってしまったのですが、環礁のような場合を考えると無理っぽいことが判明。そもそもそんなやり方では明らかに時間が足りません。
結局ググりましたところ、これはどうやら探索と呼ばれる分野に属していて、深さ優先探索というのをやればよいとのこと。そんなん思いつくわけありませんね;-o-)
というわけで再帰処理というものから調べなければなりませんでしたが、これがどうも苦手で目が回ります。階乗の例で一応納得して、あとは細かいことを考えず探索の関数を作成。配列上に記録したマップを2重ループでチェックして島（点）を発見したらそこから探索開始するとともに見つかった点は消していくものとし、最終的に関数の呼び出し回数を数えればそれが答えになります。先達の皆様のコードを参考にしながら自分が理解できる形でなんとか正解できました。
ところで探索というのはロマンがありますね。応用が広そうですし、何と申しましょうか俺のナノマシンが世界を覆いつくすぜ的な厨気分に浸れるのがいいです。
ここまでとこれから
まずPythonというものに慣れる必要がありますので無勉で解けるような問題を優先して解いている段階です。
もう少し慣れたらより本格的なアルゴリズムの学習を…と言いたいところですが、地味なソートとか木とか、覚えるべき基本がゴロゴロありますので当面はその辺りに注力したいと思います。
