はじめに
AtCoder Beginner Contest 283の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc283
問題A
A^Bは1にAをB回掛けたものなので、それを計算します。
public static void Solve()
{
var (A, B) = Scanner.Scan<long, long>();
long answer = 1;
while (B-- > 0)
{
answer *= A;
}
Console.WriteLine(answer);
}
問題B
クエリが1 k xの場合はA[k] = xで更新し、2 kの場合はA[k]を表示します。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var Q = Scanner.Scan<int>();
while (Q-- > 0)
{
var query = Scanner.ScanEnumerable<int>().ToArray();
if (query[0] == 1)
{
var (k, x) = (query[1] - 1, query[2]);
A[k] = x;
}
else
{
var k = query[1] - 1;
Console.WriteLine(A[k]);
}
}
}
問題C
0以外の場合はそのボタンを1回を押し、0が1以上連続する場合は0の数が偶数の場合はその半数の00ボタンを押し、0の数が奇数の場合は0を1回押して残りの半数を00で押せばいいことがわかります。
そのため、Sを順にみていき、0以外の場合は1回、0の場合はCeil(連続する0の数/2)回押すことで答えを求めることができます。
public static void Solve()
{
var S = Scanner.Scan<string>();
var N = S.Length;
var answer = 0;
var l = 0;
while (l < N)
{
if (S[l] == '0')
{
var r = l;
while (r < N && S[r] == '0') r++;
var c = r - l;
answer += (c + 1) / 2;
l = r;
}
else
{
answer++;
l++;
}
}
Console.WriteLine(answer);
}
問題D
Sを順にみるとき、(が出現したときにレベルを+1し、)が出現したときにレベルを-1すると、良い文字列のレベルごとに含まれる文字の集合を管理することができます。例えばa(b(c)d(e))のときは以下のようなレベルになります。
L2: (c) (e)
L1: (b d )
L0: a
このとき、)の操作は、そのレベルに含まれる文字の箱に入れたボールを箱から取り出すという操作になります。
そのため、Sを順にみていき、以下のような操作をすることで答えを求めることができます。
(の場合は、レベルを+1する。)の場合は、現在のレベルに含まれているボールを箱から取り出してレベルを-1する。- それ以外の場合は、
- ボールが箱にある場合は、
Noを出力する。 - ボールが箱にない場合は、ボールを箱に入れ、現在のレベルにボールを追加する。
- ボールが箱にある場合は、
- 全て完了できるならば
Yesを出力する。
public static void Solve()
{
var S = Scanner.Scan<string>();
var N = S.Length;
var balls = new bool[26];
var level = new Dictionary<int, List<int>>();
var curr = 0;
for (var i = 0; i < N; i++)
{
if (!level.ContainsKey(curr)) level[curr] = new List<int>();
if (S[i] == '(')
{
curr++;
}
else if (S[i] == ')')
{
foreach (var c in level[curr])
{
balls[c] = false;
}
level[curr].Clear();
curr--;
}
else
{
var c = S[i] - 'a';
if (balls[c])
{
Console.WriteLine("No");
return;
}
balls[c] = true;
level[curr].Add(c);
}
}
Console.WriteLine("Yes");
}
問題E
操作は、i行目を反転させること、つまりi行目の全ての列の値を0/1反転させることになります。
また、A[i][j]が孤立しない状態を作ることができるかは、A[i-1][j]、A[i+1][j]、A[i][j-1]、A[i][j+1]のいずれかが同じ値である必要があり、i行目の状態curr、i-1行目の状態prev、i+1行目の状態nextが分かれば、i行目の全ての列が孤立しない状態として成り立つか判断することができます。
そのため、curr、prev、nextがそれぞれ行が反転していない(0),反転している(1)の状態であるとき、
dp[i][curr][prev][next]:=i行目まで見たとき、それぞれcurr、prev、nextかつi行目が孤立していない状態の最小値
とした動的計画法を解くことで操作回数の最小値を求めることができます。
public static void Solve()
{
var (H, W) = Scanner.Scan<int, int>();
var A = new int[H][];
for (var i = 0; i < H; i++)
{
A[i] = Scanner.ScanEnumerable<int>().ToArray();
}
var dp = new int[H, 2, 2, 2];
const int inf = (int)1e9;
for (var i = 0; i < H; i++)
{
for (var curr = 0; curr < 2; curr++)
{
for (var next = 0; next < 2; next++)
{
for (var prev = 0; prev < 2; prev++)
{
dp[i, curr, next, prev] = inf;
}
}
}
}
for (var i = 0; i < H; i++)
{
for (var curr = 0; curr < 2; curr++)
{
for (var next = 0; next < 2; next++)
{
for (var prev = 0; prev < 2; prev++)
{
var okW = true;
for (var j = 0; j < W; j++)
{
var ok = false;
if (i - 1 >= 0) ok |= (A[i][j] ^ curr) == (A[i - 1][j] ^ prev);
if (i + 1 < H) ok |= (A[i][j] ^ curr) == (A[i + 1][j] ^ next);
if (j - 1 >= 0) ok |= (A[i][j] ^ curr) == (A[i][j - 1] ^ curr);
if (j + 1 < W) ok |= (A[i][j] ^ curr) == (A[i][j + 1] ^ curr);
okW &= ok;
}
if (!okW) continue;
var cost = curr;
if (i == 0)
{
dp[i, curr, next, prev] = Math.Min(dp[i, curr, next, prev], cost);
}
else
{
dp[i, curr, next, prev] = Math.Min(dp[i, curr, next, prev], dp[i - 1, prev, curr, 0] + cost);
dp[i, curr, next, prev] = Math.Min(dp[i, curr, next, prev], dp[i - 1, prev, curr, 1] + cost);
}
}
}
}
}
var answer = inf;
for (var curr = 0; curr < 2; curr++)
{
for (var next = 0; next < 2; next++)
{
for (var prev = 0; prev < 2; prev++)
{
answer = Math.Min(answer, dp[H - 1, curr, next, prev]);
}
}
}
if (answer == inf)
{
Console.WriteLine(-1);
}
else
{
answer = Math.Min(answer, H - answer);
Console.WriteLine(answer);
}
}