ブログが続かない人のブログ

技術ネタについて書いていきたいです。

ABC101に参加しました

AtCoder Beginner Contest 101 - AtCoder

ABC101に参加しました。

いままで過去問はいくつか解いてきましたが、リアルタイムで参加したのは初めてでした。

(初めてレーティングがついて、灰コーダーになりましたww)

結果は......AとBはAC、CとDはWAで終わってしまいました....

問題ごと簡単に振り返ってみようと思います。

A - Eating Symbols Easy

高橋君は,いつも頭の中に整数を 1 つ思い浮かべています.

はじめ,高橋君が思い浮かべている整数は 0 です. これから,高橋君は + または - の記号を,あわせて 4 つ食べようとしています. 高橋君が + を食べると,思い浮かべている整数は 1 大きくなります. 一方,高橋君が - を食べると,思い浮かべている整数は 1 小さくなります.

高橋君が食べようとしている記号は,文字列 S で与えられます. S の i 文字目は,高橋君が i 番目に食べる記号です.

すべての記号を食べ終わった後,高橋君が思い浮かべている整数を求めてください.

高橋くん...なんてものを食べているんだ...

AtCoderはいかに高橋くんの奇行にまどわされないかが大事ですね(笑)

問題としては簡単で、入力の文字列の中の + の数と、-の数を数えて、差を出せば終わりでした。

Submission #2718304 - AtCoder Beginner Contest 101

解説放送ではSが4文字という制限を使って、先頭から1文字ずつifで見ていってましたw

Sが4文字の条件完全に見落としてたので、ちゃんと問題読もうと思いました。

B - Digit Sums

整数 n に対して, n を十進法で表したときの各桁の和を S ( n ) で表すことにします. たとえば, S(101)=1 + 0 + 1= 2 です.

整数 N が与えられたとき, N が S ( N ) で割り切れるかどうかを判定してください.

これは単純に計算するだけでACできました。あとからわかりましたが、これD問題にでてくる「すぬけ数」の布石だったんですね...

回答の中で変数思いつかなくて $hoge とか使ってしまっているのがはずかしい...よく考えたらわざわざfor文で回さなくても List::Utilの sum 使えばできましたね。

Submission #2719378 - AtCoder Beginner Contest 101

C - Minimization

長さ N の数列 A1 , A 2 , . . . , A N があります.最初,この数列の要素は 1 , 2 , . . . , N を並び替えたものになっています.

スヌケ君は,この数列に対して次の操作を行うことができます.

・数列のうち,連続した K 個の要素を選ぶ.その後,選んだ要素それぞれの値を,選んだ要素の中の最小値で置き換える.

スヌケ君は,上の操作を何回か繰り返すことで,この数列の要素をすべて等しくしたいです. 必要な操作の回数の最小値を求めてください. この問題の制約の下,このようなことは必ず可能であることが証明できます.

この問題を見た時、 n/(k-1) で出せるのではないかと考えました。 例えば

4 3

2 3 1 4

の場合はまず最初の3つを選んで最小値が1なので 1 1 1 4 にしますが、このとき変わっているのは 2 3 の二つのみです。なので、要素数のうちのk-1個のグループの数が最小値なのではと考えました。

しかし、そんな甘くはなく、

3 2

2 3 1

のような場合、最小値は2回ですが、自分の考えた方法だと3回になってしまいます。

もちろん提出しても通るはずもなくWA..... Submission #2720408 - AtCoder Beginner Contest 101

その後エッジケースを条件分岐で継ぎ足すもACにはなりませんでした。

終了後に解説を見ると (n-1)/(k-1) と書いてあるではないですか!!惜しい〜〜〜〜〜〜

全体に伝播させる要素の分を最初から抜いておき、抜いた中でのk-1個のグループの数を考えればよかったようです。自分の考えに固執してしまうとダメですね...

ただこれは少数の場合に四捨五入する必要があるのでそこだけ注意が必要だと思いました。

D - Snuke Numbers

整数 n に対して, n を十進法で表したときの各桁の和を S ( n ) で表すことにします. たとえば, S ( 123 )= 1 + 2 + 3= 6 です.

正の整数 n であって, m> n であるような任意の正の整数 m に対して n / S ( n ) ≤ m / S ( m ) が成り立つようなものを,すぬけ数 と呼ぶことにします.

整数 K が与えられたとき,すぬけ数 を小さいほうから K 個列挙してください.

出力のサンプルから、 1 2 3 4 5 6 7 8 9 19 となっていて怪しいなと思い、実際に計算してみると、すぬけ数はnが10のときに10、11の時に5.5、...19のときに1.9と、単調減少していることに気づきました。そのあとnが20になると10になりまた大きくなります。

ここまで気づいたので、「これは19、29、39、...と続いていくのでは...!」と安直な予想を立てて提出してみましたが、玉砕しました..

Submission #2731783 - AtCoder Beginner Contest 101

解説や解説動画を見ると、方針的にはそこまで悪くなかったように思いますが、ツメが甘かったようです。

自分的に解説は数式が多く理解しにくかったので、他の方の実装を参考にしながら理解しました。以下のコードがとてもわかりやすかったです。

Submission #2731138 - AtCoder Beginner Contest 101

最上位の数字を追っていって、0でないときにはそのまま出力。桁数が変わった時にはいままで追っていた桁数の場所が0になるので、そうなったらそこに9を入れて次の桁を追うようにするという流れです。

なぜ9にしていいかは解説動画でもありましたが、n/S(n)を最小にするためです。

こういう問題をサクッと解けるようになりたいw

感想

惜しいところまでわかっていたものの、最後のツメが甘く、ACならずでした。

とりあえず理解はしましたが、まだ自分で書いてみてないので、復習がてらもう一度挑戦したいです!