ツバサの備忘録

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

ABC106

なんだかんだまだARC出たことないので出てみたいですね

A - Garden

提出コード
(a-1)*(b-1)をすればよいです。
道の部分を無視して畑をくっつけると、実際に上の式のように、a-1とb-1の辺の長方形になります。

B - 105

提出コード
1からnまでの数字について、与えられた条件を満たすかどうかそれぞれ調べていきます。
約数のカウントも、1から順番に、素直にカウントすればOKです。
<=と<のミスをしてまた1WAもらいました!

C - To Infinity

提出コード
基本的に1番前にある数字がK番目の数字になります。気を付けるべき場所は、文字列の先頭にたくさん1がならんでいるときのみです。
ならんでいる1の個数がK以下だったら答えは1、そうでなければ1を除いた文字列の中で1番先頭にある数字が答えになります。

D - AtCoder Express 2

提出コード
久々に時間内に解くことができました。
二次元配列を用意し、
memo[i][j]=都市iから都市jまでに完全に含まれる区間の数
とします。つまり、クエリを受け取ったとき、それに対応する配列の中を見るだけで答えが求まるようにします。
少し考察をします。
今、lからrまでを走る列車について考えます。
1からlの間の任意の数iを、rからnの間の任意の数jをとったときに、この列車の区間は完全に含まれることになります。
毎回全ての配列の要素に1を足すと時間がかかるので、1からlの間をiでループさせてmemo[i][r]にだけ1を加えておき、全ての入力が終わってから、全てのmemo[i][j]について、jを増やしていきmemo[i][1]からmemo[i][j]までの累積和を取っていくと、うまく時間内に処理を行うことができます。

というわけで久々の全完でした。
D問題は解けそうな人はすぐとけそうだなぁという難易度の問題でしたが、結構時間がかかったので次はもっとスパッと解きたいです。