競プロをしながら、節約と株式投資でセミリタイアを目指す東大卒のブログ

東大卒でメーカー勤務の私がセミリタイアするために投資や競プロを頑張っていこうという趣旨で始めたブログです。独身男性です。火木土日に更新予定です。お金について考えています。

競技プログラミング~ABC171前半~

おはようございます。しほみんです。

 

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の方が単純なので、もっと発想が単純なのであまり苦労しなかったかもしれません。

 

ではでは。