幼なじみと許嫁が修羅場らしいが、それなら両方手に入れればいいじゃない
ということで、5回目です(`･ω･´)
いつもだと・・・
問題を読む -> 仕様通りに書く -> サンプル通りの出力になるか確認する ->
いったんサイトで実行してみる -> 途中で落ちる -> リファクタリングしてみる ->
小手先の修正では通らない -> 奇抜な方法を試す -> サンプルの出力すら出なくなる ->
煮詰まって悩む -> いったん寝る -> ヒントになりそうなアルゴリズムを探す ->
いまいちいいのがない -> でも調べるうちになんとなく見える ->
書き直してみる -> あれ、もうちょっとで通るやん？ -> 直す -> ∠( ﾟдﾟ)／
・・・というプロセスを経由してクリアしております(´･ω･`)
なので、過去の記事においては、
「どう試行錯誤したか？」をまとめているわけです
しかし、今回はですね・・・
問題を読む -> 仕様通りに書く-> 先回りして罠を回避する ->
サンプル通りの出力になるか確認する -> いったんサイトで実行してみる -> 通ったΣ(ﾟДﾟ)ｶﾞｰﾝ
・・・ということで、一発で通ってしまいまして(； д ) ﾟ ﾟ
なので、そもそも今回の問題が（いつもに比べて）簡単という可能性もあります
実際、もっと高難易度な問題は別に用意されてますし
とはいえ、過去の問題の傾向から、
ここを押さえればいけるというポイントがわかっていたのも事実で、
今回は「何を考えたか？」を中心にいろいろ書いてみます...φ(･ω･｀)
なお、私の回答は「おまけ」にて
1問目
見た瞬間解けないと・・・とまでは言いませんが、最近のWeb企業を受ける場合、
このような問題を面接で出される可能性はある*1ため、
できれば5分、最低でも15分くらいで解き方を思いつかないと(ﾟдﾟ)ﾏｽﾞｰです
なお、問題文では「ODD」といってますが、
たいていの言語において、配列は0-originなので、
実際のコードでは「EVEN」というのが罠と言えば罠でしょうか
2問目
「周期性のあるものは割った余りを見ろ」ってミルカさん*2が言ってたΣ(・ω・ノ)ノ
この問題は実際の業務でもありそうな話であり、
効率の良いコードとまではいかなくても、全く書けないというのは問題です
3問目：レナルート
先に解いたのはアイドルの許嫁でしたが、
ぶっちゃけ話をきちっと読んでなかったので、
先に目に入った方を解いたという・・・Σ(ﾟДﾟ)ｶﾞｰﾝ
Excelのような表にあらかじめ値が入っており、
あとから複数指定される領域を結合した領域に含まれる値の合計、
といった問題でございます
ポイントはもちろん「領域には重複があること」であり、
素直に解くならば、まず「領域がどんな形になるか？」を組み立て、
元の表をparseして領域に含まれるかを判定して足す・・・という感じでしょうか
でも、これだと「領域を組み立てる」ので一度parseし、
「合計を算出する」段階でもう一度parseするわけで、
過去の問題だとこのやり方で100点は無理です(´･ω･`)
「読み込み（gets）しながら問題を解く」というのが理想であり、
「最初の表を読み込む」のは仕方ないにしても、
「領域の読み込みと計算」は同時に進めたいところです
要は、「再度読み込まれても値が加算されない」なら良いわけで、
しかも求められているのは「合計」だけです
なので、「一度読んだ領域を0で上書き」すれば、何度読んでもOKです(`･ω･´)
ついでに、素直にデータ構造を組むとHashとか使いたくなりますが、
これも過去の経験から「Arrayのindexアクセスが速い」とわかっていたので、
データをただの配列で保持し、x/y座標からindexを算出する方法を取っています
あと、きっちり問題を読むと、
表領域に対し指定領域のindexが異様に大きいような気がしたので、
一応足切りを入れていますが、どの程度効果があったかは不明です(´-ω-)
＜結果＞
3問目：ミナミルート
レナルートは業務寄りの問題なので、実行効率はともかく、
全く書けないってことはないと思うのですが、
ミナミルートは「まんま書く」をやろうとして詰む可能性はあります(lllﾟДﾟ)
いわゆる「落ちものパズル」の話で、
火のついた爆弾が消えると、上にあった爆弾が「落下する」という条件で、
最終的にどんな盤面になるかを出力せよ、という問題です
状態が「空＝0」「普通の爆弾＝1」「火のついた爆弾＝2」と3つあり、
しかも「落下する」ということは「下に何があるか？」を考えなければならず、
普通に解こうとすると結構悩ましい問題です(´-ω-)
しかし、冷静に「出力結果」を見ていただきたいのです
出力するのは「0か1」であり、「火のついた爆弾＝2」はどうせ消えるので、
考えなくていいわけです
しかも、「落下する」と考えるから混乱するわけで、
「落下したあとどうなっているか？」を考えると、
「各列ごとに爆弾がいくつ残るか？」がわかればいいわけです(`･ω･´)
つまり、最初の盤面をparseしながら、「各列ごとに1の数をカウント」し、
出力する時にその値に応じた行を出力していけばいいわけです
結果的に、ミナミルートの方が圧倒的に簡単なコードになります
強いていえば、出力時は「盤面の上から」であり、
「下から積み上げ」ではないので、1か0かの判定が多少混乱しますが、
サンプル出力になるように適当にいじればどうにか・・・Σ(・ω・ノ)ノ
（なお、この問題ではカウンターにHashを使っていて、
「そこはArrayじゃないのか？щ(ﾟДﾟщ)」と突っ込みを受けそうですが、
ええやん、それでも100点だし、直すのめんどいし
そもそも、普段の業務なら迷わずHash.new(0)にしているのもあって・・・）
＜結果＞
まとめ
過去の問題で学んだチューニングポイントがこちら(´･ω･)っ
- parseやループ回数をとにかく減らす
- 細かなチューニングよりも圧倒的に重要
- 盤面を保持するデータ構造はできるだけ簡潔に
- 複雑な構造を使おうとしている時点で、解き方がおかしいと考える
- 簡単に足切りできそうなら切る
- 結果さえあっていればいいので、過程はどうでもいい
- 結果から逆算して、求められている計算手法を予測する
この辺がわかっていたので、今回は一発でしたが、
やはり本命はSP問題の方でしょう
・・・時間がないのでやりませんがΣ(・ω・ノ)ノ
