SRM 500 Dev2 Level 1.
問題はこちらです。
要するに
- 複数の数が与えられる。
- 与えられた数の中から任意に１つ選ぶ。
- 選ばれた数と、その数±1 の数を消す。
- 数がなくなったら終了。
というゲームにおいて最長手数を出力するプログラムを書く問題です。
まず、
(a)この場合の与えられた数は3つに分類にできる。
(b)分類に応じた取り扱いをしないといけない
と考えました。
この考えは大袈裟に言えば発想で、最初に直観的にそう感じ、あとから下記に述べるような考えで直観を確認していきました。
(a)の３つの分類とはすなわち① 前後の数がないもの、②前後どちらかの数があるもの、③前後両方の数があるもの、です。
(b)の分類に応じた取り扱いとは
①の分類になる数をまず選択していき、①がつきたら②を、②が尽きたら③を選択するという取り扱いです。
なぜなら、最長手数を求める以上は選択回数が多くなければなりません。
選択による数の消失数が少ない順に選択を行えば、選択肢を次により多く残すことができるので選択回数も増えます。
たとえば[99,100,101,]と数が与えられたとき、99 を選び、その後に 101を選ぶと2回選択ができます。しかし、最初に 100 を選ぶと1 回目の選択でゲームが終了してしまい、手数が減ってしまいます。これは③の分類である100を、②の分類である99 や101 より先に選択したためです。
さて分類自体は与えられた数の中に、±1 の数があるか、あるなら何個あるのか、を調べ、分類に応じてまとめておけばよいです。これは簡単だと思いました。
分類し終わったあとはどうするべきでしょうか？
①の分類にあたるものは、単純にその分類を構成する要素の数が手数になります。
しかし②と③に分類されている数は選択すると他の数が消失するため、要素数＝手数とはなりません。
例えば[99,100]という分類の個数は2個ですが、99 を選択すると 100 も消えるので手数としては 1 回になります。
なので、②と③については何等かの処理が必要になります。
最初に思いついた処理は深く考えず、
- 分類から1つ数を選ぶ。
- その数はそのまま残して、前後の数を探して前後の数が見つかったら分類から消す。
という処理をすることです。前後の数を消した後に残る要素数はその分類を処理するための手数と一致するはずです。
実は、もうちょっと他のやり方はないだろうか？というのも一応検討しました。
そうしたところ、"②前後どちらかの数があるもの"に分類される数には同じ分類中に必ず対になるものがあり、②に分類される要素数を 1/2 にすれば手数になるのではないかとも考えました。
つまり
- 99が②に分類されるのであれば、98 か100もまた②に分類されている。
- そして、98-99 または99-100という組み合わせは1回の手数でなくなるので、要素数 / 2 = 手数
という思考です。
この後から検討した考えを有望視したため、実際の回答過程ではこれを採用しました。
あとから気付くのですが、"必ず対になるものがある”という認識は間違えでした。
例えば、[97,98,99]という組み合わせでは 99 は②に分類されますが、98 は97と99 があるため、"③前後両方の数があるもの"になります。
なので、僕の"必ず対になるものがある”という認識は間違いでした。
もっとも"分類 ②の要素数 / 2 = 分類②の手数" という手法自体は実際には正しかった(結果は正しいが、なぜ正しいかの理由付けが僕の考えとは違った)ようです。
さて実際に書いたコードを張ります。
gistbe30f7a676283c9af114bbee3201cd6b
13行目までが分類。
14行目で分類②と分類③で重複したものがないように、重複分を分類②から削除しています。
15行目から19行目で分類③に対して処理を行います。
20行目は処理後の各要素を足して手数を求めています。
こちらで模範解答を確かめてみようとしたのですが、pythonの回答はなかったです。
ただ、他の言語の模範解答ページにあるtest Arguments をいくつか試したところ、Expected Results と一致したのでおそらくあっているかな？と思います。(勿論、”いくつか”あっているだけでは正解と言い切れないのですが...)
まあ、おそらくあっているだろうということで、今回はOKとしたいと思います。
PS.いつも回答を検証するときに、Test Argumets をコピペして実行、コピペして実行とやっているのですがとても面倒です。
何かいい方法はないものでしょうか。
はじめに
あいさつ
このブログをご覧いただきありがとうございます。
まず最初にこのブログの趣旨を説明いたします。
このブログは筆者であるt2ubasaが興味のある分野について学んだことや学んでいる過程記述するブログです。
このブログで書かれる分野について筆者は学び初めて間がなく、その分野については素人同然です。
この素人であるという宣言は予防線ではなく、読んでいただく方に誤解がないように趣旨を明かにするための宣言です。
つまり、このブログでは既にある程度専門的な知識を持っている人間がある分野について書くのではなく、その分野の素人がどう学んでいったか、どこに躓きどう乗り越えたかという過程を記述していく予定です。
既に専門的な知識を身に着けている方にとっては退屈なものになるでしょう。
その一方で私と同じくある分野に興味を持ったがどこから手をつければいいのかわからない、という人の一助になれば望外の喜びです。
取扱い分野について
上記のように私が興味のある分野であれば何でも取扱うかと思いますが、
現時点では下記を取扱う予定です。
