A07 - Event Attendance

atcoder.jp

前日比を計算してから、前日比の累積和を計算。

var D = int.Parse(Console.ReadLine()!);
var N = int.Parse(Console.ReadLine()!);

// 前日比を計算
var B = new int[D + 2]; // 0 日目と D + 1 日目も含める
for (var i = 0; i < N; i++)
{
    var line = Console.ReadLine()!.Split(' ');
    var l = int.Parse(line[0]);
    var r = int.Parse(line[1]);
    B[l]++;
    B[r + 1]--;
}

// 累積和を計算しながら出力
var S = new int[D + 2];
for (var i = 1; i <= D; i++)
{
    S[i] = S[i - 1] + B[i];
    Console.WriteLine(S[i]);
}

B06 - Lottery

atcoder.jp

アタリとハズレの累積和をそれぞれ計算しておく。0 番目の累積和として 0 を追加しておくテクニックを使ってみた。

var N = int.Parse(Console.ReadLine()!);
var A = Console.ReadLine()!.Split(' ').Select(x => int.Parse(x)).ToList();
var Q = int.Parse(Console.ReadLine()!);
var L = new List<int>();
var R = new List<int>();
for (var i = 0; i < Q; i++)
{
    var lr = Console.ReadLine()!.Split(' ').Select(x => int.Parse(x)).ToList();
    L.Add(lr[0]);
    R.Add(lr[1]);
}

// 番兵(?)として 0 を登録しておく
var SW = new List<int>() { 0 };
var SL = new List<int>() { 0 };
for (var i = 0; i < N; i++)
{
    if (A[i] == 1)
    {
        SW.Add(SW[i] + 1);
        SL.Add(SL[i]);
    }
    else
    {
        SW.Add(SW[i]);
        SL.Add(SL[i] + 1);
    }
}

for (var i = 0; i < Q; i++)
{
    var win = SW[R[i]] - SW[L[i] - 1];
    var lose = SL[R[i]] - SL[L[i] - 1];
    if (win > lose)
    {
        Console.WriteLine("win");
    }
    else if (win == lose)
    {
        Console.WriteLine("draw");
    }
    else
    {
        Console.WriteLine("lose");
    }
}

A06 - How Many Guests?

atcoder.jp

(R日目までの累積来場者数) - (L - 1 日目までの累積来場者数)を愚直に実装してみた。

var NQ = Console.ReadLine()!
    .Split(' ')
    .Select(x => int.Parse(x))
    .ToList();
var N = NQ[0];
var Q = NQ[1];
var A = Console.ReadLine()!
    .Split(' ')
    .Select(x => int.Parse(x))
    .ToList();

// 質問を読み込む
var L = new List<int>();
var R = new List<int>();
for (var j = 0; j < Q; j++)
{
    var LR = Console.ReadLine()!
        .Split(' ')
        .Select(x => int.Parse(x))
        .ToList();
    L.Add(LR[0]);
    R.Add(LR[1]);
}

// 累積和を計算
var s = 0;
var S = new List<int>();
for (var i = 0; i < N; i++)
{
    s += A[i];
    S.Add(s);
}

for (var j = 0; j < Q; j++)
{
    var l = L[j];
    var r = R[j];
    var answer = S[r - 1];
    if (l - 1 - 1 >= 0)
    {
        answer -= S[l - 1 - 1];
    }
    Console.WriteLine(answer);
}

解答例の「0 日目の累積来場者数を登録しておく」手法は思いつかなかった。番兵みたいなものか。頭良いな。

B04 - Binary Representation 2

atcoder.jp

2進数を10進数に変換。

var N = Console.ReadLine()!;
var answer = 0;
for (var i = 0; i < N.Length; i++)
{
    var m = Math.Pow(2, N.Length - 1 - i);
    if (N[i] == '1')
    {
        answer += (int)m;
    }
}
Console.WriteLine(answer);

A05 - Three Cards

atcoder.jp

3重ループだと時間切れになるので、2重ループで。

var input = Console.ReadLine()!.Split(' ');
var N = int.Parse(input[0]);
var K = int.Parse(input[1]);
var answer = 0;
for (var r = 1; r <= N; r++)
{
    for (var b = 1; b <= N; b++)
    {
        var w = K - (r + b);
        if (w > 0 && w <= N)
        {
            answer++;
        }
    }
}
Console.WriteLine(answer);

A04 - Binary Representation 1

atcoder.jp

10桁目から計算開始し、桁を下げていく。

var N = int.Parse(Console.ReadLine()!);
var answer = "";
for (int i = 9; i >= 0; i--)
{
    var m = Math.Pow(2, i);
    answer += (int)(N / m);
    N = (int)(N % m);
}
Console.WriteLine(answer);

B03 - Supermarket 1

atcoder.jp

ただの 3 重ループだと商品が重複するので WA になる。商品が重複しない工夫が必要。

var N = int.Parse(Console.ReadLine()!);
var A = Console.ReadLine()!.Split(' ').Select(int.Parse).ToList();
var answer = false;

// 組み合わせなので、同じ商品を選ばない工夫が必要。
// 先頭から開始するので、組み合わせる商品は次以降から選ぶ。
for (var i = 0; i < N; i++)
{
    for (var j = i + 1; j < N; j++)
    {
        for (var k = j + 1; k < N; k++)
        {
            if (A[i] + A[j] + A[k] == 1000)
            {
                answer = true;
            }
        }
    }
}
if (answer)
{
    Console.WriteLine("Yes");
}
else
{
    Console.WriteLine("No");
}