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