AtCoder Beginner Contest 136参加メモ

結果

A,B,C,Dの四完。Eは半自力(と言い張る)でAC。

A - Transfer

容器1の残量はA-B。 これをCから引けばいいだけだけど残量は0が最低値なので注意。

B - Uneven Numbers

一見してあれ？これBのわりに難しくない？と思ったけどなので総当たりすればいいですね。
偶数桁で割って0、奇数桁で割って0でなければカウント ( if (i / 1000 == 0 && i / 100 != 0) )、みたいにしたけど単純に1-9,100-999,10000- 99999ならカウントとする方が楽ですね。

解説にある方法(文字列にして文字列長を求める)が一番楽だと思いますが。文字列にできればなーとは思ったけど文字列に変換する方法がぱっと出てこなかった…。

C - Build Stairs

• 単調非減少ということは右のマスは左のマス以上であればよい。
• マスの高さを低くする操作を各マスについて1度ずつ行える。

右から見れば左は低ければ低いほど良いです(2以上低くても意味はないですが)。つまり左から見ていって単調非減少という条件を壊さないなら操作をするというのが最善手になります。これで条件を満たせなければNo。

D - Gathering Children

「回」を見てしばしフリーズしました。がまあこの数字自体がヒントみたいなものですね。

• 文字列の長さは以下
• 移動は回

なので途中経過は考えなくて良いとなります。 ということはRLとなっているところだけ考えればよい(ここで右行って左行ってを繰り返す)。 また偶数回の場合のみ考えればよいです( は偶数)。

まずRについて考えます。左から走査。 RLのLから1,3,5,…と奇数個離れたRは偶数回の移動でLの隣に集まり、Lから2,4,6,…と偶数個離れたRは偶数回の移動でRに集まります。Lについても同様です。右から走査。

図を描くとわかりやすいです。

私は左からRをカウントしてLに差し掛かったら境界のRとLに振り分ける、右からLをカウントしてRに差し掛かったら(ryとしました。

if (Si[i] == 'R')
{ ++pre; }
else if (Si[i - 1] == 'R' && Si[i] == 'L')
{
    Hi[i - 1] = (pre + 1) / 2;
    Hi[i] = pre / 2;
    pre = 0;
}
pre = 0;
for (var i = Si.Length - 1; 0 <= i; --i)
{
    if (Si[i] == 'L')
    { ++pre; }
    else if (Si[i + 1] == 'L' && Si[i] == 'R')
    {
        Hi[i + 1] += (pre + 1) / 2;
        Hi[i] += pre / 2;
        pre = 0;
    }
}
WriteLine(string.Join(" ", Hi));

左/右から走査してR/Lなら二つ飛ばすというやり方もあるようです。そっちの方が簡単そうですね。

E - Max GCD

無制限に操作できるなら一つに全部集めればそれが最大・・・など入力例をコネコネしているうちに、の累計の約数が解の候補になることに気づきました。(操作しても総数は変わらないのでですしね。)
じゃあ候補が解であるか判定するにはどうすればよいか？というところでコンテスト終了。

どうすればよいかなーと時間無制限で考えているうちに、結局となるように操作、すなわちだけ+1するかだけ-1するかしかないということに気づきます(xは解の候補)。 となるとで小さい奴を-1して大きい方を+1する操作してそれぞれが0(大きい方がx、小さい方が0)になるかつ操作回数がK以下であればそれが解である、と。

static void Solve()
{
    //入力取得処理
    var NK = Sarray();
    var N = NK[0];
    var K = NK[1];
    var Ai = Slist();

    var sum = Ai.Sum();
    var max = Ai.Max();
    if (0 == max)
    {
        WriteLine(0);
        return;
    }
    var dc = yaku(sum).OrderByDescending(e => e.Key);//約数求めてる。解候補
    foreach (var pk in dc)
    {
        Ai.Sort((l, r) => (int)(r % pk.Key - l % pk.Key));//modとって降順にソート
        var b = 0;
        var e = (int)N - 1;
        var ln = Ai[b] % pk.Key;
        var rn = Ai[e] % pk.Key;
        var ope = 0L;
        while (b < e)
        {
            if (K < ope)
                break;
            if (pk.Key == ln + rn)//・・・①
            {
                ope += rn;
                ln = Ai[++b] % pk.Key;
                rn = Ai[--e] % pk.Key; ;
                if (e <= b)
                {
                    if (ope <= K)
                    {
                        WriteLine(pk.Key);
                        return;
                    }
                }
            }
            else if (pk.Key < ln + rn)
            {
                ope += pk.Key - ln;
                rn = ln + rn - pk.Key;
                ln = Ai[++b] % pk.Key;
            }
            else
            {
                ope += rn;
                ln += rn;
                rn = Ai[--e] % pk.Key;
            }
        }
    }
    WriteLine(1);
}

半自力、としたのは解が1の場合うまくいかない(ので最後にWritelLine(1)が必要)ことに他の人の提出コード見るまで気づかなかったためです…。

なお①の部分をif (0 == (ln + rn)%pk.Key)にすればWritelLine(1)は不要になります。

F

にゃーん

所感

Dまで割と早めに解けた(俺調べ)！水色パフォでた！お祝いに転職先くれ！フシャー！(威嚇