AGC003の参加日記

2完で416位/700人くらい。AtCoderのコンテストは問題文が分かりやすくて良い(日本語だからというだけじゃなく)。


A - Wanna go back home

二次元平面上のある点から、1ターンずつ東西南北いずれかに正の距離移動する。ターンごとの方角が与えられたとき、元の位置に戻ることができるか。

東西と南北それぞれについて、たとえば東だけなどある方向に行きっぱなしになっていなければ、元の位置に戻ることができる。

if (((str.Count(c => c == 'E') == 0 && str.Count(c => c == 'W') == 0) || (str.Count(c => c == 'E') > 0 && str.Count(c => c == 'W') > 0)) &&
    ((str.Count(c => c == 'N') == 0 && str.Count(c => c == 'S') == 0) || (str.Count(c => c == 'N') > 0 && str.Count(c => c == 'S') > 0)) )
{
    Console.WriteLine("Yes");
}
else
{
    Console.WriteLine("No");
}


B - Simplified mahjong

1からNまでの整数が書かれたカードが、それぞれAi枚ある。2枚のカードについて、整数の差の絶対値が1以下ならペアを作ることができる。作ることのできるペアの最大数を求めよ。

連続したカードごとのグループを作り、グループ内のカード枚数/2を合計すればよい。

Int64 ret = 0;
Int64 sum = 0;
for (int i = 0; i < a.Count(); i++)
{
    if (a[i] == 0)
    {
        ret += sum / 2;
        sum = 0;
    }
    else sum += a[i];
}
ret += sum / 2;
Console.WriteLine(ret);


C - BBuBBBlesort!

長さNの数列Aに以下の操作を行い、昇順にソートする。
・操作1:連続する2つの要素の順番を反転
・操作2:連続する3つの要素の順番を反転
最少の操作1の回数を答えよ。
1 <= N <= 10^5
0 <= Ai <= 10^0 (整数のみ)

操作2は何回行ってもも構わないので、奇数位置にある値はコストなしで動かすことができる。よって、偶数位置にあるものを、奇数位置へ動かす回数が答えとなる。
(同じ回数だけ、奇数位置から偶数位置に動かすものがある)

var n = Int32.Parse(Console.ReadLine());
var a = new List<Int64>();
var dictIdx = new Dictionary<Int64, int>();
for (int i = 0; i < n; i++)
{
    a.Add(Int64.Parse(Console.ReadLine()));
    dictIdx.Add(a[i], i);
}

var wk = a.OrderBy(v => v).ToList();
var indices = new Int64[n];
for (int i = 0; i < wk.Count; i++)
{
    indices[dictIdx[wk[i]]] = i;
}

Int64 ret = 0;
for (int i = 0; i < a.Count(); i++)
{
    if (i % 2 == 0 && indices[i] % 2 == 1) ret++;
}
Console.WriteLine(ret);