引き続きAtcoder ProblemsのTrainingのEasyにあるC問題埋めです。このあたりから全然解法が思いつかないというものが出てきました。
目次
1.ABC087
問題:C-Candies
2×Nマスのマス目があり、それぞれのマスにキャンディーが置かれている。移動は右に1マスか下に1マスしかできないとき、スタートからゴールまで行く道中に取得できるキャンディーの最大数を答えよ、という問題です。
Nが100程度なので、全ての道をたどってあげて、その中で一番最大の個数を出力すれば良さそうです。
書いたコードは以下の通り。
範囲の和はnumericとか使えばきれいに書けた気がする。
2.ABC135
N+1個の街があり、それぞれある数のモンスターに襲われています。また、N人の勇者がいて、それぞれの勇者はi番目とi+1番目の街のモンスターを合計でB体倒せます。最大で何体のモンスターを倒せるかと出力せよ、という問題です。
最初sortしてバーってやればええやん！って思いましたが、これは順番そのままじゃないといけないので、それはダメです。
ただ、前から処理していけば良さそうだというのはわかります。
また、モンスターをできる限り倒すので、2つの街のモンスターの合計が勇者の倒せるモンスターの数より少ないという場合は、その差だけ勇者のパワーが無駄になります。そのため、前の勇者は次の勇者の担当分のモンスターをできる限り残しつつ、自分の倒せるモンスターを最大化するようにしてあげれば良さそうです。
つまり、i番目の勇者はi番目の街のモンスターを全て倒し、i+1番目のモンスターはその残りの数倒すようにすれば、倒すモンスターの数は最大化できそうです。
書いたコードは以下の通り。
if(b[i] >= a[i]) a[i + 1] -= b[i] - a[i];
このとき、if文を付けていないと、後ろの式の値がマイナスになって次のモンスターの数が増えるバグが出るので注意です。私はやらかしました。
3.ABC106
操作を1回すると、1は1のまま、2は2倍ずつ増殖、3は3倍ずつ増殖する・・・ような数列を考えます。この操作を(考える必要のないぐらい)無限回行ったとき、K文字目の数字はなにかという問題です。
5000兆回操作を繰り返しますが、2~9は5000兆回繰り返したあとは、Kの最大値10^18の個数を超える個数ができあがります。
そのため、1とそれ以外に分けて考える必要があることがわかります。
基本的に、最初が1なら次の数字を出力すればいいですし、最初が1以外ならばその数字を出力すれば良さそうです。
要するに、K番目まで1ならば1を出力するしかなく、K番目までに1でない数字があるのならば、初めて1でない数字が現れた数字を出力しなければなりません。
私はその事に気が付かずに、めちゃくちゃif文で条件分岐させて書きました。
書いたコードは以下の通り。
ちなみに解説では、"K番目までで初めて1でない数字が出た数字を出力する"方針で説明していました。そっちのほうがシンプルに実装できます。
4.ABC136
Nマスが並んでいて、マスの高さを1低くするか何もしないかという操作をそれぞれのマスに行うことで、マスの高さを右に行くに従って高く(高さが同じでも良い)できるかどうか判定する問題。
前から自分とその次を見て、自分より高ければ問答無用で高さを1下げて、同じなら何もしない、低ければ無理と判断という操作を繰り返せば良さそうです。
しかし、ここで問題になるのは一番最初のマスです。上の方針は次のマスの高さをとりあえず下げとけという考えなので、自分のマスに関しては操作されたあとであるとしています。しかし、一番最初のマスに関しては一回も操作がされないまま次のマスの操作をしているので、42…みたいな入力例が与えられた場合、そのまま通っていまいます。
そのため、最初のマスに関しては問答無用で高さを-1する操作をループ前にしています。これで最初のマスに操作がされないというのは解決しました。
書いたコードは以下の通り。
5.ABC144
問題:C-Walk on Multiplication Table
解説読んでも理解できなくて、人の実装見て理解した問題です。
10^6 × 10^6の九九の表があり、(1,1)から縦横に移動して整数Nの書かれた場所まで移動する。その移動回数の最小値を求めよという問題です。
まず、(a,b)まで移動する移動回数はa+b-2回です。
さらに、九九は対称性があるので、a≦bとしてもいいです。
さて、探索の仕方ですが全探索です。どこまで探索するかといえば、a≦√Nまでです。
そうして、縦(もしくは横)にa進み、Nがaで割り切れるようならば横(もしくは縦)にb進みます。
書いたコードは以下の通り。
参考にしたコード:提出 #13615648
6.おわりに
このあたりから頭が回ってない感じがありました。