東京海上日動 プログラミングコンテスト2020 に C# で参加した記録
東京海上日動 プログラミングコンテスト2020 – AtCoder
東京海上日動 プログラミングコンテスト2020 にC#で参加しました。普段のABCとは違い、ARC級といわれる中級者向けのコンテストです。
配点が 100,200,500,700,800,1000 となっており、500点問題が解ければよし、解けなければABの早解き勝負といった感じのコンテストでした。
結果はABCの3問ACで青パフォ、レートは1400手前くらいまで来ました。ここ最近青パフォがとれるようになってきました！
ということで振り返ります。
A – Nickname
あなたは同じ授業を受けている男性に名前を尋ねました。彼は S と名乗りました。S は英小文字からなる長 3 以上 20 以下の文字列です。 あなたは S から適当に連続する 3 文字を選んで、彼のあだ名とすることにしした。彼のあだ名として適切な文字列を 1 つ出力してください。
A問題は100点です。連続する3文字を自由に選べばよいので、先頭から3文字を選ぶことにします。
var S = sc.ReadStr();
var ans = S.Substring(0, 3);
Console.WriteLine(ans);B – Tag
2 人の子供が数直線上で鬼ごっこをしています。鬼役の子供は今座標 A にいて 1 秒あたり距離 V 移動することができます。 また鬼から逃げている子供は今座標 B にいて 1 秒あたり距離 W 移動することができます。
鬼役の子供は相手と同じ座標にいるとき、相手を捕まえることができます。 今から T 秒の間に（ちょうど T 秒後も含む）鬼役の子供がもう一方の子供を捕まえることができるかどうかを判定してください。 ただし、2 人の子供は最適に動くとします。
制約
- −109≦A,B≦109
- 1≦V,W≦109
- 1≦T≦109
- A≠B
- 入力で与えられる値はすべて整数である。
B問題は200点です。ABCのB問題よりはやや難しいですが、大きく難易度は変わりません。
制約より区間が広くなっているので、愚直な趣味レーションではTLEします。
ということで O(1) くらいで解くための考え方ですが、まず鬼であるAはBに向かって移動するのが最善であり、逆にBはAと反対方向に移動するのが最適です。
ということはAとBの距離は1秒ごとに V-W だけ近づきます。V-W が負の数の時は逆に遠ざかることになります。したがって、T秒間でAは T*(V-W) だけBに近づけるのでこれが初期位置におけるAとBの距離を超えていれば、どこかで捕まえることができると判定できます。
var A = sc.ReadLong();
var V = sc.ReadLong();
var B = sc.ReadLong();
var W = sc.ReadLong();
var T = sc.ReadLong();
if (Math.Abs(A - B) <= T * (V - W))
{
Console.WriteLine("YES");
}
else
{
Console.WriteLine("NO");
}T*(V-W) は32bit整数ではオーバーフローするので注意しましょう。今回はあらかじめ long でとっています。
また、AとBの大小関係(初期位置の関係)は決まってないので、距離を求めるのは絶対値にしましょう。勘違いしてWA食らいました。
C – Lamps
数直線上に電球が N 個並んでおり、電球には左から順に 1 から N までの番号がついています。 電球 i は座標 i にあります。
電球には光の強さを表す非負整数値が定まっており、 座標 x に光の強さ d の電球があるとき、その電球は座標 x−d−0.5 から座標 x+d+0.5 までの区間を照らします。 初めは電球 i の光の強さは Ai です。 そこで、以下の操作を K 回繰り返し行います。
- 1 以上 N 以下の各整数 i に対し、操作時に座標 i を照らしている電球の個数を Bi とする。そして、各電球 i の光の強さを Bi に変更する。
K 回の操作を行った後の各電球の光の強さを求めてください。
制約
- 1≦N≦2×105
- 1≦K≦2×105
- 0≦Ai≦N
C問題ですが500点問題であり、ABCだとE問題くらいの難易度設定となっています。
ところでこういう問題はシミュレーションしてみるのが一番なので、愚直に求めるコードを書いてみます。
// K回実行
for (int i = 0; i < K; i++)
{
// i回目の操作終了後の状態
var na = new int[N];
// すべてのランプについて
for (int j = 0; j < N; j++)
{
// j番目の電球が照らす範囲の更新
for (int k = Math.Max(0, j - A[j]); k <= j + A[j]; k++)
{
if (k == N) break;
na[k]++;
}
}
A = na;
}なにも考えないとこんな感じのコードになります。計算量は O(K*N^2) であり、とても間に合いません。なので高速化を考えます。
区間に対して値を加算している箇所のコードはimos法(累積和)を使えば、更新処理を O(1) にできます。
// K回実行
for (int i = 0; i < K; i++)
{
// i回目の操作終了後の状態
var na = new int[N];
// すべてのランプについてimos法
for (int j = 0; j < N; j++)
{
na[Math.Max(0, j - A[j])]++;
if (j + A[j] + 1 < N) na[j + A[j] + 1]--;
}
// 累積和を計算して次の状態にする
for (int j = 1; j < N; j++)
{
na[j] += na[j - 1];
}
A = na;
}これで計算量が O(K*N) まで改良できました。
次に、このシミュレーションの各操作後の状態を出力しながら考えてみることにします。
5 10
0 0 0 0 0上のような入力でどのような状態の変化が起きるか見てみます。
1 : 1 1 1 1 1
2 : 2 3 3 3 2
3 : 4 4 5 4 4
4 : 5 5 5 5 5
5 : 5 5 5 5 5
6 : 5 5 5 5 5
7 : 5 5 5 5 5
8 : 5 5 5 5 5
9 : 5 5 5 5 5
10 : 5 5 5 5 54回目の操作ですべて5になった後、状態の変化は当然起こらなくなります。したがって各操作後に、操作前の状態と比較して変化していなければ(つまりすべての要素がNであれば)処理を中断してよいです。
解説PDFによると、このすべてがNになるまでの操作回数は logN になります。これはシミュレーションしてみるとなんとなくわかります。
これがわかればあとは手を動かしてTLEしないことを確認すればACできます。
一番操作回数が多くなるのは初期状態がすべて0のときというのはなんとなくそうだと思います。なのでこのケースを試してTLEしなかったので提出してACしました。
ということでコードです。
var N = sc.ReadInt();
var K = sc.ReadInt();
var A = sc.ReadIntArray(N);
// テストデータ
// N = 200000;
// K = N;
// A = new int[N];
for (int i = 0; i < K; i++)
{
var na = new int[N];
for (int j = 0; j < N; j++)
{
na[Math.Max(0, j - A[j])]++;
if (j + A[j] + 1 < N) na[j + A[j] + 1]--;
}
for (int j = 1; j < N; j++)
{
na[j] += na[j - 1];
}
A = na;
if (A.All(a => a == N)) break;
}
Console.WriteLine(string.Join(" ", A));ということで実装したコードがこちらです。計算量は O(NlogN) です。
最大ケースを試してみるとTLEしないことが簡単に確認できます。
水diffの問題でした。
D – Knapsack Queries on a tree
D – Knapsack Queries on a tree
D問題解けませんでした。半分全列挙を使うらしいですが、難しかったです。
