こんばんは、しほみんです。
先週行われたABC146について解説と反省をします。今回も普通にミスってしまったので悲しい感じですね...今振り返ってももったいないです。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは600前後の茶色です。
＜Atcoderでのスタンス＞
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約20回参加、6か月。
・目標はD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。レートは緑を安定的にとる。
今回はABしか解けず、パフォーマンスも410と大幅に下がりました。
レーディングも580→563と下がりました。最近調子が悪いですね。下がるときは連続的に下がってしまうのでどこかでちゃんと解けるようになりたいですね....
今回はD問題さえまともに触れられていないのでABCの3題だけ解説します。
ただ、今回ABともに若干コードを書くのが面倒だったのでCまで解ければレートは十分高かったように思えます。
以下ネタバレです。
A問題
皆さん楽しみな日曜日があと何日で来るかを問う問題です。
入力が月から日まで与えられるので次の日曜日まではあと何日かはじき出します。
例えば、土曜日なら次の日曜日まであと1日なので1です。
日曜日なら次の日曜日まであと1週間なので7日で、7です。
ただ、解法は簡単で入力は7つしかないのでそれぞれの場合で分岐して答えを出すだけです。愚直にコードを書きますが時間かかるので注意です。
B問題
アルファベットの大文字のみで構成されるある文字列が与えられたときに、それぞれの文字をnだけアルファベット順で進めます。Zのときは1進めるとAに戻るとします。
例えば、ABCXYZを2つ進める場合、CDEZABとなります。
n進めるだけなので非常に単純です。ただし、アルファベットの進め方を知らないと解くのは難しいでしょう。
まずそれぞれの文字をchar型で読み込みます。
そのあと、char型をint型に変換します。このとき、文字に応じた固有の数に変換されます。
'A'は65に変換されます。'B'は66,'C'は67で...こんな感じで最後は、'Z'は90に変換されます。
つまりintでただnを足し合わせてそれをまたchar型に戻せばいいです。
さっきのAを2つ進めるを例にすると、
A→65→65+2→67→Cとなり、そのまま出力しちゃいましょう。
ただし91以降はまた別の文字が割り振られているので91以上の場合は26を引いてもとのAに戻るようにします。
C問題
整数屋さんにおいて有り金で買える一番大きい整数を求める問題です。
整数NはA×N+B×(Nの桁数)円で売られています。
A,B,有り金が与えられる場合、その最大のNを求めます。
A,Bともに正なので、Nが大きくなれば、かかる金額は増えます。
つまり、料金はNに対して単調増加なので、2分探索が使えます。
2分探索を使えば、答えが出ます。
二分探索も簡単で、判定条件がNのとき、このお金で買えるか？なので、どんどん答えを絞ることができます。
二分探索はありうる最大と最小の真ん中をとって、それが可能ならその数を最小に、無理なら最大にしてどんどん絞っていく方法です。単調増加の関係なら少なくともこれが一番アルゴリズム的に早いです。
アルゴリズムは自分のコードをご覧ください。
と僕も思ったのですがC問題で2分探索って出るのかな？とか考えてもっと簡単な方法はないのかな...って思ってしまいました。そこが泥沼の始まりで、そのせいでACまでたどり着きませんでした。
自分が考えたのはNの桁数は高々10なのでそれから満たす桁を探して、その中で最大の整数を探せばいいかなと思って実装したのですが、1つだけうまくいきませんでした。多分何か見落としていたんだろうなって感じです。
ということで今度からはこのアルゴリズムで解けるとわかったら素直にそれで解くことにします...ということで今回は非常にもったいないことをしたなって感じです。
考え込みすぎてしまって、D問題さえまともに手を付けられていません。もっと頑張らないと少なくともアルゴリズム力を示すのは難しいなあって...もっと時間が欲しいです。
きょうのところはここまでで。ではでは。
