こんばんは、しほみんです。
昨日は初めて二か月がたったのでその話をしました。なので、今日は昨日しようと思っていた競技プログラミングについて話していこうかなって思います。
昨日ABC147があったのですが、その前に、先週行った競技プログラミングの結果をお話しします。今週末にまたABC147について話せればなあと思います（というか思ったより難しくて何か言えるか怪しい）。
先週は企業コンペですが、レベルはABC相当でした。なので比較的に挑みやすかったのかなと思います。しかも今回は数学パズルチックな感じがして面白い気がしました。
自分の競技プログラミングへのスタンスです。（ちょっと追記しました）
＜自分のプログラミング力＞
・レートは600前後の茶色です。まずは700目指します。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約25回参加、7か月。
・目標はD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。レートは緑を安定的にとる。
今回はABC問題を30分程度で解けたので、レーディングは653とぼちぼちでした。スコアも563→573と若干上昇しています。
多分ここがいまの自分の実力な気がしているので、もうちょっとアルゴリズム覚えたいですね....D問題もちゃんと気が付けば解けたので、惜しいです。1時間ぐらいただずっと無理じゃね?って頭抱えていました。気が付いたのが10分前で手遅れって感じです。
今回もD問題まで話せたらと思います。やっぱり最近時間がなさ過ぎてEまで手が回らないのがあまりにも悔しいですが....
以下、ネタバレです。
A問題
2019年M1月D1日と、その次の日の2019年M2月D2日が与えられるので、2019年M1月D1日が月末かどうか判定する問題です。
やり方はたくさんありますが、自分はM1とM2が違えば、2019年M1月D1日が月末なのでそれで判別する方法を選びました。
ほかには....
・D2が1日であれば、2019年M1月D1日は月末です。
・M1月D1日が素直に月末かみます。ただ、月ごとにD1が変わるので一番コードとしては面倒になります。
B問題
これも複数やり方がありますが、自分はこうときました。
とりあえず、Nを1.08円で割ります。この時、切り上げで出します。
この金額をxとして、xを1.08倍したとき、xとNが同じならxが答えです。
それ以外はあり得ないので答えは：（となります。
これ今見直したら、解説にない方法ですね....多分解法2の方に近いです。
消費税は性質の都合上切り捨てなので、1.08倍して切り捨てなら、1.08倍で割れば切り上げかなって感じで出しました。もうちょっと計算式で考えると...
切り上げ金額をαとすると、x = N/1.08 - αです。（0≦α<1）
よって 1.08x = N + 1.08αです。ここで、1=<1.08αだと、切り捨て計算でN+1円になってしまうので、実現できません。逆に1.08α<1だと切り捨てでN円になるので一致します。これを使っています。
C問題
100,101,102,103,104,105円のものが事実上無限にあるとしたとき、x円が与えられます。それが実際に可能かどうか見ます。
まあ全部100円以上なので、100円の個数と0,1,2,3,4,5円の個数が同じということを考えると、まず値段で買える個数が決まります。あとは0-5円の間でその個数が実現できるか考えればいいです。
例えば、206円のとき、2個買えて、あとは3+3円で組み合わせであったらよいので変えます。逆に211円だと、2個では実現できないので無理です。
実は買える個数をN個とすると、N*5円以下の端数のものはすべて組み合わせ的に買えます。端数は99円以下なので、Nが20個すなわち、2000円以上であれば事実上買えます。
あとは、1999円以下のときですが、結局N*5円より大きければ買えないのでそこで区別をします。
まとめると
1. x/100円の切り捨てで、買える個数Nを決める。
2. x-N*100円と5*Nを比較して、5*Nより小さければ買えます。（N>=20なら事実上これで買えます）
D問題
N桁の数が与えられます。ここから3個の数を取り出して、3桁の暗証番号を出します。あり得る暗証番号の数を求めます。
まあ、いろいろ考えていたのですが結局、暗証番号って1000個しかなく、Nも高々30000なので、おとなしく1000個の暗証番号があり得るかどうかを検討したらいいです。
というかDPとかでも結局解けなくはないっぽいですが自分じゃ複雑すぎて無理でした。こういう発想の転換の全探索は大事です。
また、あり得るかどうかも貪欲法で解けます。
まず、一桁目があるかを見つけます。
あるなら、二けた目をそれでの次の数字から探します。ないなら、あり得ないので次の暗証番号に移ります。
二桁目も同様にあるか見つけて、あるなら次の数字から三桁目も探します。ないなら次の暗証番号に移ります。
探索時間もo(1000N)なので余裕があります。
こんな感じで、最近はアルゴリズムの奥深さを少しは理解して解いているような気がします。解法通りのことができるのは進歩の証拠だと思います。
今日はここまで。ではでは。
