ARC 041 AとB

この前のACM-ICPC国内予選で（主にコーディング面で）全然貢献できなかったという悔しい思い出を機に競プロモチベが若干上がっている昨今。CFの問題をSolver順に解いたりRoundに参加したりしてますが、久しぶりにARCに真面目に参加しました（WORKING'!!一挙放送を見ながらではありましたが）。

A問題 コインの反転

表向きのコイン（ 枚）と裏向きのコイン（ 枚）を複数枚渡されて、「ちょうど 枚ひっくり返せ」と言われた時にどれだけたくさんのコインを表向きにできるか。

• のとき：裏向きのコインを 枚ひっくり返せばいい→表向きのコインは 枚になる
• のとき：とりあえず裏向きの 枚は全部ひっくり返す・表向きのコインのうち被害を受けるのは 枚→表向きのコインは 枚

公式解説スライドは絶対値を使って に依らない想定解を出してたけどたぶん場合分けして展開したらこうなるんだと思います（適当）。実際2つ目式の括弧の中の符号を反転すれば1つ目の式になるっぽい。雑魚だからコンテスト中に絶対値の中の正負がとか考えてる余裕はない。

import std.stdio;
import std.string;
import std.algorithm;
import std.conv;
import std.range;
import std.math;

void main() {
    int x, y;
    readf("%d %d\n", &x, &y);
    int k = readln.chomp.to!int;

    if (k <= y) {
        writeln(x + k);
    } else {
        writeln(x + 2 * y - k);
    }
}

B問題

「わっ！」ってやると四方に分裂するアメーバがいる。「わっ！」って言った後の盤面が与えられるので、「わっ！」って言う前の盤面を出力する。

「あるセルの上下左右全てにアメーバがいたらそのセルにはアメーバがいた」と考えられる。左上から右下に向かって順番に「上下左右のアメーバのうち一番少ない数（ とする）をそのセルにいたアメーバの数にし、上下左右から を引く」操作を続けると矛盾なく解ける。

import std.stdio;
import std.string;
import std.algorithm;
import std.conv;
import std.range;
import std.math;

void main() {
    int n, m;
    readf("%d %d\n", &n, &m);
    int[][] b;
    for (int i = 0; i < n; i++) {
        b ~= readln.chomp.split("").map!(to!int).array;
    }

    int[][] a = new int[][](n, m);
    for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < m - 1; j++) {
            int up = b[i][j - 1];
            int down = b[i][j + 1];
            int right = b[i + 1][j];
            int left = b[i - 1][j];

            if (up > 0 && down > 0 && right > 0 && left > 0) {
                int min_am = min(up, down, right, left);
                a[i][j] = min_am;
                b[i][j - 1] -= min_am; b[i][j + 1] -= min_am;
                b[i + 1][j] -= min_am; b[i - 1][j] -= min_am;
            }
        }
    }

    foreach (e; a) {
        e.map!(to!string).join("").writeln;
    }
}

C

RRR....LLLL的なセグメントに分けるところまでは思い付いたけど「常に多い方を少ない方に寄せればいい」という簡潔な最適解まで思いつけなかった。

D

読んでない。