おはようございます。しほみんです。
ABC171です。今回も普通にやらかしました....正直ちょっとなあって感じです。C問題でなんか詰まるのが悔しいですね....
https://atcoder.jp/contests/abc171
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは800程度になりました。緑を何とか維持。
・C#でクラスとかつかってアプリケーションは作れます。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学んでいる。第3回PAST70点で中級取得。
・基本的に本番でやっている。現在50回以上参加、2年目。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回はABD、40分でした。C問題でつまってしまい、E問題もよく考えれば解けたが...って感じで踏んだり蹴ったりでした。D問題はとにかく楽だったのでDを先に説くべきでした....。ただ、レーディングはなぜか前回よりも良くて、617ですが、レートは868→845で下がりました。
今回はE問題まで振り返ります。（もし間に合ったらF問題まで振り返ります）
長くなるので前半はC問題まで書きます。前回に引き続き考察をメインに書きます。
コードは別に上げます。
A問題
アルファベット1文字が与えられます。
これが大文字なら"A"、小文字なら"a"を出力してください。
まずは文字を読み込みます。
この文字をchar型で読みます。
そのあと、数字と比較すると勝手にint型になります。よって、そのときに数値比較をします。
char型からint型にかえるときは一意的に決まります。
'a'から'z'までは97から122です。
'A'から'Z'までは65から90です。
よって、入力した文字が90より大きければ小文字、小さければ大文字があることになります。
あとはそれに応じて、Aかaを出すだけです。
B問題
N種の果物売られており、それぞれの値段はpi円（i=1からN)です。
K種類の果物を買います。この時最低金額をこたえなさい。
B問題としてはかなり素直です。
KはNより小さいので、値段の小さい順からK番目までを選んで足せばよいです。
1.値段を配列に格納します。
2.ソートします。
3.for文でk回小さい順に取り出して、足します。
これで答えを出力します。
ソートして何かをすることはよくあるので、ソートをして、昇順か降順かに並べる発想自体は持っておきたいところです。
C問題
たくさんの犬がいます。
1番目から犬に名前を付けていきます。
1番目から26番目は"a"から"z"です。
27番目から702番目までは"aa"から”zz"です。
というふうに、最初は1文字でアルファベット順、次は2文字でアルファベット順って感じで並べます。
このとき、N番目の犬の名前を答えよ。
今回の難題です（自称）。まあずっと26で割って余りを見ていけばよいって思っていたのですが、一つ見落としててそのまま答えられなかったです。毎回1引くことを....
まあ一つずつ話します。
まず、基本方針ですが、2進法の求め方と同じです。
2進法だと、与えられた数を2で割ってその余りを記録しておきます。そして商を2でわって次のフェーズに行きます。
そして最後0になったとき、割った順から逆に出していくと答えが出ます。
例えば、4だと、4→2→1→0となり、このとき、3回2で割ります。
余りは、0,0,1です。よって100が2進数表記とわかります。
これと同じことを26進数として考えればよいわけです。
ただし、これではACできないです。今回は1つ罠があります。
それはN番目というのは、文字数がs文字のときのN番目を示してないからです。
要するに、上の手法が使えるのは文字数が1つしかないときに限られます。
例えば、2進数表記で以上の問題の4番目を考えます。
すると
0,1,00,01,10,11,....です。なので、4番目は01です。
ここでさっきとは違うとわかります。これは、なぜか？
1文字での表記は2通りです。このあとに、二文字での表記が入ります。
よって、2文字での表記では2番目のものをこたえないとなりません。
実際は番数の累積で表せるので矛盾します。
これを具体的に解決するには、1引けばよいのです。
例えば先ほどの4ですが
4-1で3にする、2で割って1あまり1
1-1で0にする、2で割って0あまり0
よって、01とちゃんと答えが出ます。
2進数でうまくいくなら26進数もそのままうまくいくので、置き換えるだけです。
では、1をあらかじめ引くことで、うまくいくのはなぜか？といわれるとちょっと怪しいですが、自分はこう考えています。
ここではもう26進数で考えます。
1回目はすんなり理解できます。1引くことで、あまりが0から25となり、つじつまが合うからです。
2回目以降なのですが、1引くことはすなわち、商を削ることなので、
今まで割った26の回乗だけのものが引かれているにすぎません。
つまり、2回目には26を引いていて、3回目には26の2乗を引いていて、4回目は26の3畳を引いています。
これってどこかで見覚えがないですか？そう、s文字表記でありうる組み合わせです。
これを引いてやることで、すでに決まっているs-1文字での組み合わせを全部省いて、それ以降のs文字において何番目の数を示すかにすることができます。
よってまとめると
while文でnが0になるまで続ける。以下繰り返し。
nをn-1にする。
n%26を記録。
nをn/26に切り替える
となります。このn-1に置き換える発想はかなり難しいと思います。特に直感で理解しにくいところもつらいですね。ぬーん。
最後に....
C問題なんかめっちゃ発想は面倒だなと思います。再帰関数をよく理解しないとちょっと厳しい感じです。ただ、再帰関数を感覚的に理解できているとそんな感じがするので、繰り返し読むしかないかなあって感じです。
D,Eの方が単純なので、もっと発想が単純なのであまり苦労しなかったかもしれません。
ではでは。
