おはようございます。しほみんです。
先週行われたキーエンスのコンテストについて復習したいと思います。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは650前後の茶色です。まずは750目指します。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約30回参加、8か月。
・目標はABCのD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。レートは緑を安定的にとる。
一言でいえば、惨敗でした。結局A問題しか解けず、BもCも躓いてしまいました。B問題は凡ミスですし、C問題は気が付かなかったことでまあちょっと残念ですね....
パフォーマンスも495で、レートも658まで下がりました。ちょっと終息しつつあるので、ここらへんで大きく伸ばしたいですね
ただ、あとは以下の2つができれば、緑レートには到達できると思います。
・考えたことを間違いなくきちんと実装すること（今回のB問題）
。すぐ解ける感じの問題をきちんとこなしていくこと（今回のC問題）
ここはちょっと壁がある気がしますが、なんとなく毎週コンテスト参加していれば自然と身についていく感じはするのでめげずに頑張ります。
早速問題に移ります。今回はC問題まで行きます。
A問題
H行Ｗ列のマスがあります。
一度に一列か一行か塗り、これを一回とします。この時Nマス塗るのに最小の回数を求めよ。
多く塗れるのはHとWの大小で決まります。
よって、
Hが多ければ、行を塗り続け、Wが多ければ、列を塗ればいいです。
あとはN/H+1回が答えですが、割り切れる場合は回数が増えてしまうのでN/Hで対応します。
構成としては
if(H>W)
if(N%H == 0) N/H
else N/H+1
else
if(N%W == 0) N/W
else N/W+1
です。
B問題
ロボットがXiの位置で置かれています。腕がLiの長さそれぞれ持ちます。
それぞれの腕がぶつからないようにロボットを取り除きます。最大で残るロボットはいくつか求めよ
まずは計算量的にforループしか使えません。よって、手前のロボットの位置から順番に決めて取り除くかどうかを考えればよいです。（ロボットの位置は手前から順になっていないのでまずはソートします）
つまり、貪欲法です。比較するのは今置かれているロボットの腕の最大値と次置くはずのロボットの腕の最小の位置です。
これだけわかっていれば、あとは素直に実装するだけです。
構成としては
まず配列をソートします。
C#ではtaskでできます。詳しくはコードを見てください。
x[i]はロボットの位置、l[i]はアームの長さ、
compare1は追加ロボットの最小、comapre2は今までのロボットの最大
compare2 = x[0]+l[0]
for(i = 1;i < n;i++)
compare1 = x[i] - l[i]
if(compare1 > compare2)
remove++
if(compare2 > x[i] + l[i])
compare2 = x[i]+l[i]
else
compare2 = x[i]+l[i]
って感じです。
C問題
N,K,Sが与えられます。
N個の数列があって、以下の条件を考えます。
1<=l<=r<=Nで、lからr番目の和がSとなるのはK個ある。
これを満たす数列を求めます。
気が付いたらおしまいのタイプの問題です。
きちんと詰めてみましょう。
・lとrは同じでいいので、1つでSを実現できるかどうか
→条件的にSを代入できる。
・K<=Nなので、K個Sを並べることができる。
・それ以外はS+1にしてしまえば絶対ならない。（ただしSが10の9乗だとS+1はないので、1にする）
としたらもうやるのはこれだけです。
for(i = 0;i < N;i++)
if(S == 100000000)
if(i <K)
Write(S)
else
Write(1)
else
if(i <K)
Write(S)
else
Write(S+1)
最後に...
やっぱりこのB,C問題を詰められなかったのは悔しいですね。ただ、これが解ければいいってゴールも見えてきたのでそれを見据えて頑張れればいいなと思います。ではでは。
