ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC101

最近忙しいですがICPCも近いので少しでもプログラミングに触っていたいですね。


A - Eating Symbols Easy

提出コード
0からスタートして、+が出現したら1をたし、-が出現したら1を引いていきます。sの長さの指定をよく見ていなかったので、sの長さだけループを回しています。最後に出力して完了です。


B - Digit Sums

提出コード
これは後々D問題で使います。ある和Nをうけとったら、いったんNをコピーします(今回はmにコピーしました)。そして、mが0になるまで、 ・10で割ったときのあまり(つまりmの1の位)を、各桁の和を保存する変数に代入する ・mを10で割る ということをくりかえします。これにより、入力されたNの各桁の和がもとまります。 最後に、Nを先ほどの和で割ったときにあまりがでるかどうか、で割り切れるかどうかを判別します。


C - Minimization

提出コード
問題を見た時点で、全ての数字は最終的に1になることに気づいたので、1を中心に、ほかの数字をそろえていくことを考えていきます。 まず、1の右側、左側に分けて考えます。その時、K個の数字に対して操作を行うことができますが、1つは1が含まれていないといけないので、一度の操作で1に置き換えることのできる最大の個数はK-1となります。なので、1の右側、左側の個数をK-1で割ったときの商の和と、さらにそれぞれを割ったときにあまりがあれば+1をしたものが、答えになります。 ここまでで、解答の根幹の部分が完成しました(この状態で提出して1WAでした)。 しかし、左右どちらもK-1で割ったときのあまりが存在するとき、少し注意が必要です。 なぜなら、この問題における操作というのは、なにも1という数字が端っこにある必要がある、というものではないからです。1の左右を囲むように操作を行うこともできます。つまり、K=3とし、4 5 6 1 2 3という数列があるとしたときに、 1 2 3 5 6 1 という選びかただけでなく、 6 1 2 という選び方もできるのです。 この選び方は、先ほどの余りについて計算するときに、右側と左側のあまりがK-1を超えていなければ1手減らすことができるものになっています。 この考え方をプログラミングにおとしこみ、無事ACです。


D - Snuke Numbers

提出コード(時間外)
この問題は、解説をみてもピンとこなかったので、けんちょんさんのブログを参考にさせていただきました。リンクはこちらになります。 1ずつ数を増やしていったときに、ある桁が9→0になると、各桁の和は一気に減少します。なので、基本的に各桁は9であると条件を満たす数になりそうな気がします。また、2桁~3桁あたりを調べると、どうやら一番左側にある数字は9以外でも問題なさそうであることがわかります。なので、一番左側だけ任意の数字で、それ以外が9であるような数字を順に出力していきました。…このコードを提出した人はそこそこいるように思います。が、これには罠があり、最高位以外が9でない場合でも、この問題の条件を満たすパターンというものが存在します。ここで、すぬけ数の条件が10^{15}以下であるので、9の羅列でない部分の数字が、おおよそ150より小さいことになります。(けんちょんさんのブログで詳しく解説されているので、自分が説明するよりもこちらを見ていただいた方がわかりやすいかと思います。簡単に言うと、すぬけ数でなくなる条件、すなわち9以外の数字の部分をkとしたときに、k+1と比較して小さくなる条件を探します。)なので、9の羅列に、1~150までの数字を合体させたものを配列にいれ、ソートをした後2重ループを使ってすぬけ数を愚直に求めていけばあとは間に合います。


普段の難しい問題もそうですが、このような一見簡単そう(?)な問題に対しても、きちんと考察する力をつけていかなければと思いました。一歩ずつ着実に実力を伸ばしていければいいですね…