AGC001の参加日記

AGC第一回。参加者1200人超でめでたい。2完で318位でした。
Editorial：https://agc001.contest.atcoder.jp/data/agc/001/editorial.pdf

A: BBQ Easy - AtCoder Grand Contest 001 | AtCoder

バーベキュー用の串が2N本ある。1つの串焼きに2本の串を使う。1つの串焼きに使える具材は、短いほうの串の長さに等しい。最大でいくつの具材を串焼きにできるか。

串をソートしてペアを作り、それぞれの短いほうの和を求めればよい。標準入出力の凡ミスで二回もWAを出してしまった。

public static int Solve(int[] l)
{
    var ret = 0;
    l = l.OrderByDescending(v => v).ToArray();
    for (int i = 0; i < l.Length - 1; i+=2)
        ret += Math.Min(l[i], l[i + 1]);
    return ret;
}

B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder

1辺の長さがNの鏡3つを、反射面を内側に向けて正三角形状に組み合わせる。三角形の頂点をa,b,cとする。
辺abのある点x(aからの距離X)から、辺bcと水平に光を発射する。この光は、鏡に当たると反射するが、さらに光の軌跡に当たっても反射する不思議な性質がある。この光は、必ず元の点に戻ってくることが証明できる。光の軌跡の長さを求めよ。
2<=N<=10^12、1<=X<=N-1、NとXは整数

dfs(a,b)を、現在地（上図）からの、残りの距離を返す関数と定義して再帰的に解いた。
なおNの最大値が大きいので、Intだとオーバーフローする。

public static UInt64 Solve(UInt64 n, UInt64 x)
{
    var ret = x + (n - x);
    ret += dfs(x, n - x);
    return ret;
}
 
public static UInt64 dfs(UInt64 a, UInt64 b)
{
    if (a == 0 || b == 0) return 0;
    if (b % a == 0)
    {
        return a * 2 * (b / a - 1) + a;
    }
 
    var ret = (2 * a) * (b / a);
    if (a % (b % a) == 0) return ret + ((b % a) * 2) * (a / (b % a)) - b % a;
 
    ret += ((b % a) * 2) * (a / (b % a));
    return ret + dfs(a % (b % a), b % a);
}

良く分からないが、なんと3*GCD()で一発で解くこともできるらしい。

C: Shorten Diameter - AtCoder Grand Contest 001 | AtCoder

N頂点の木がある。直径をK以下にするためには、最少でいくつの頂点を削除する必要があるか。

各頂点（Kが奇数なら辺）で、距離K/2を超える頂点の数をもとめ、その最小値が解答になる。

public class Solver
{
    static int maxDist;
    static List<List<int>> edges;

    public static int Solve(int n, int k, List<List<int>> e)
    {
        maxDist = k / 2;
        edges = e;

        var ret = Int32.MaxValue;
        for (int i = 0; i < n; i++ )
        {
            if (k % 2 == 0)
                ret = Math.Min(ret, Dfs(i, -1, 0));
            else
                foreach(var j in e[i]) 
                    ret = Math.Min(ret, Dfs(i, j, 0) + Dfs(j, i, 0));
        }
        return ret;
    }

    static int Dfs(int cur, int prev, int dist)
    {
        var ret = dist > maxDist ? 1 : 0;
        foreach (var next in edges[cur])
        {
            if (next == prev) continue;
            ret += Dfs(next, cur, dist + 1);
        }
        return ret;
    }
}

本番では、①木の直径を求め②Kを超えていたらに端を削除、を繰り返してTLEだった。
部分点がない問題なので、TLEになりそうな時点で、実装せず別解法を考えるべきだった。

D: Arrays and Palindrome - AtCoder Grand Contest 001 | AtCoder

長さMの数列Aが与えられる。Aの総和はNである。このとき、以下を満たす数列Bを解答せよ。
次の条件を満たす長さNの文字列が、すべて同じ文字になる
　先頭のa1文字、続くa2文字、さらに続くa3文字...はすべて回文
　先頭のb1文字、続くb2文字、さらに続くb3文字...はすべて回文

Aの中央にある奇数長の回文が3個以上なら、Bを作ることは不可能。
それ以外なら、まず奇数を左右の端に移動したのち、どちらかの端から１つずつずらして取ったものが解答になる。

// return value: a, b.length, b
public static Tuple<List<int>, int, List<int>> Solve(int n, int m, List<int> a)
{
    if (a.Count(v => v % 2 == 1) > 2) return null;

    if (m == 1)
    {
        List<int> ret;
        if (a[0] > 2) ret = new List<int>() { a[0] - 1, 1 };
        else ret = a.ToList();
        return new Tuple<List<int>, int, List<int>>(a, ret.Count(), ret);
    }

    //move odd items to first and last
    if (a.Count(v => v % 2 == 1) > 0)
    {
        var fst = a.First(v => v % 2 == 1);
        a.Remove(fst);
        a.Insert(0, fst);
        var lst = a.Last(v => v % 2 == 1);
        var lstIdx = a.LastIndexOf(lst);
        a.RemoveAt(lstIdx);
        a.Add(lst);
    }

    var b = new List<int>() { a.Last() + 1 };
    for (int i = a.Count - 2; i > 0; i--)
    {
        b.Add(a[i]);
    }
    if (a[0] > 1) b.Add(a[0] - 1);
    b.Reverse();

    return new Tuple<List<int>, int, List<int>>(a, b.Count(), b);
}

こういう問題だとLINQがとても便利。