キーエンス プログラミング コンテスト 2020 に参加した記録

キーエンス プログラミング コンテスト 2020 に参加した記録

キーエンス プログラミング コンテスト 2020 – AtCoder

キーエンス プログラミング コンテスト 2020 に参加した記録を残します。

個のコンテストはARC相当のコンテストで、ABCよりも難易度の高いコンテストです。問題の配点は以下の通りでした。

• A: 100点
• B: 200点
• C: 400点
• D: 700点
• E: 900点
• F: 1100点

配点はコンテスト開始前にわかるのでこれを見て、3問解けそうだったので参加を決めました。AGCやARC相当のコンテストだと配点によっては1問しか解けないような場合もあるので、その場合は実力不足なので見送るようにしています。

点数の基準がABCと同等かどうかわからないのですが、一応目安にしています。

今回の結果は想定通り、ABCの3問ACでした。パフォーマンスも水色が出たので良かったです。そしてレートが1000を突破しました。

問題を振り返ります。

A – Painting

A – Painting

H 行 W 列の マス目があり、最初すべてのマスは白色です。

あなたは、このマス目に何回かペイント操作を施すことにしました。 1 回のペイント操作では、以下の 2 種類の作業のうちいずれか 1 つが行えます。

• 行をひとつ選び、その行に含まれるマスをすべて黒く塗る。
• 列をひとつ選び、その列に含まれるマスをすべて黒く塗る。

黒く塗られているマスの個数が N 個以上となるようにするためには、最小で何回のペイント操作が必要ですか。 なお、制約の項で記述される条件のもとで、何回かペイント操作を行うことで 黒く塗られているマスの個数が N 個以上となるようにできることが保証されます。

100点の問題です。ABCの100点より難しいですが簡単です。

行と列の大きいほうを優先して塗るのが最善です。

ぴったり塗りつぶせるときは　N/max(H, W) が答えになります。余りが出るとき(足りないとき)はもう1回だけ操作が必要になるので+1してやればよいです。

var ans = N / Math.Max(H, W);
if (N % Math.Max(H, W) > 0) ans++;
Console.WriteLine(ans);

B – Robot Arms

B – Robot Arms

ある工場では、 数直線上に N 個のロボットが設置されています。 ロボット i は座標 Xi に設置されており、数直線の正負の方向にそれぞれ長さ Li の腕を伸ばすことができます。

これらのロボットのうちいくつか (0 個以上) を取り除き、 残ったどの 2 つのロボットについても、腕が動く範囲が共通部分を持たないようにしたいと思います。 ただし、各 i (1≤i≤N) に対して、 ロボット i の腕が動く範囲とは 数直線上の座標が Xi−Li より大きく Xi+Li 未満の部分を指します。

取り除かずに残せるロボットの個数の最大値を求めてください。

制約

• 1≤N≤100,000
• 0≤Xi≤10⁹ (1≤i≤N)
• 1≤Li≤10⁹ (1≤i≤N)
• i≠j のとき、Xi≠Xj
• 入力値はすべて整数である。

いわゆる区間問題というやつですか。その中でも典型の区間スケジューリングの問題みたいです。初耳ですが。蟻本とかに似たような問題が載っていた気がします。

ロボットが手を広げた区間がほかのロボットと被らないようにしなければなりません。これは各区間の終端(Xi+Li)が小さいものから順番にかぶらないようにしていくやり方で、貪欲に解くことができます。

XL を Xi+Li でソートし、直前のロボットの区間のかぶるか判定し、かぶったロボットは取り除くというやり方で解けました。

var N = sc.ReadInt();
var XL = sc.ReadTupLongArray(N);

// 区間の終端昇順でソートする
XL = XL.OrderBy(xl => xl.Item1 + xl.Item2).ToArray();

// 直前のロボット
var prev = XL[0];
var ans = 1;

for (int i = 1; i < N; i++)
{
    var prevMin = prev.Item1 - prev.Item2;
    var prevMax = prev.Item1 + prev.Item2;
    var min = XL[i].Item1 - XL[i].Item2;
    var max = XL[i].Item1 + XL[i].Item2;

    // 直前のロボットと被っているかどうか
    if (min >= prevMax && max >= prevMin)
    {
        // かぶっていない場合カウント
        ans++;
        prev = XL[i];
    }
}
Console.WriteLine(ans);

かぶっているかどうかの判定が解説PDFと違うような気がしますが、ACしたのでOKです。

B問題は典型問題でした。たしかABCでも似たような問題が出ていたような気がしなくもないです。

区間の終端が小さいものから順番に見て行くことで貪欲に溶けるという問題でした。区間の開始が早い順番では解けません。

復習しておきます。

C – Subarray Sum

C – Subarray Sum

3 つの整数 N, K, S が与えられます。

1 以上 109 以下の整数からなる長さ N の数列 A1,A2,…,AN であって、 以下の条件を満たすものをひとつ求めてください。 なお、制約の項で記述される条件のもとで、このような数列は必ず存在することが証明できます。

• 1≤l≤r≤N を満たす整数の組 (l,r) であって、 Al+Al+1+⋯+Ar=S を満たすものはちょうど K 個ある。

制約

• 1≤N≤10⁵
• 0≤K≤N
• 1≤S≤10⁹
• 入力値はすべて整数である。

C問題は驚くほど簡単でした。

入力例1の内容が 4 2 3 で、出力例1の内容が 1 2 3 4 でした。コメントで丁寧に「問題文の条件を満たす (l,r) は (1,2) と (3,3) の 2 あります。」とあります。l=r のとき、簡単に Al+Al+1+⋯+Ar=S を満たすものが作れます。そして数えるのも簡単です。

つまりややこしい数列を作らなくても S を必要な数だけ並べていればよいのではということです。そしてそれでACしました。

Sが3個並べば条件を満たす(l, r)の組はちょうど3個作れます。l != r の場合のSは、必ずSよりも大きくなります。したがってちょうどの数だけが作れることになります。

したがって単純にK個だけSを並べ、その後ろにS以外の数を並べて、N個の数からなる数列を作ればよいです。これが答えになります。

var N = sc.ReadInt();
var K = sc.ReadInt();
var S = sc.ReadInt();
var a = new int[N];

for (int i = 0; i < N; i++)
{
    if (i < K)
    {
        // K個Sを並べる
        a[i] = S;
    }
    else
    {
        // S以外の数(1以上10⁹以下)であればなんでもいい
        if (S == 1) a[i] = S + 1;
        else a[i] = S - 1;
    }
}

for (int i = 0; i < N; i++)
{
    if (i > 0) Console.WriteLine(" ");
    Console.Write(list[i]);
}
Console.WriteLine();

今回のC問題は400点の問題としては簡単だったと思います。提出者数も回答者数も多いです。というかBよりCのほうが解いてる人が多い時点で簡単でしたね。

まあ解けたので良かったです。

ちなみに解説PDFが超絶簡素でした。

以下のような数列が条件をを満たします。

• S < 10⁹ のとき、S, S, . . . , S, S + 1, S + 1, . . . , S + 1
• S = 10⁹ のとき、S, S, . . . , S, 1, 1, . . . , 1
  ただし S は K 個並べます。

あってますね。

D問題(700点)は解けませんでした。ここで難易度が跳ね上がってる印象です。まだまだ勉強不足ですね。精進します。

以上。