A – Similar String

問題に基づいて、二つの文字列を同時に一文字ずつ見ていくようなループを書く。一文字一文字見る中で、その文字について 3 つの条件のいずれかが成立していれば、そのままループを続けて、そうでなければ途中で抜けるようなコードを書ければ通る。

提出コード

<?php

fscanf(STDIN, '%d', $N);
$S = str_split(trim(fgets(STDIN)));
$T = str_split(trim(fgets(STDIN)));
$S = array_combine($S, $T);

$flag = true;
foreach ($S as $k => $v) {
    if (($k == $v)
        || ($k == '1' && $v == 'l' || $k == 'l' && $v == '1')
        || ($k == 'o' && $v == '0' || $k == '0' && $v == 'o')) {
        continue;
    } else {
        $flag = false;
        break;
    }
}
echo $flag ? 'Yes' : 'No', "\n";

B – Discord

https://atcoder.jp/contests/abc303/tasks/abc303_b

これは、集合写真で並んだそれぞれの人が、自分自身を除く全員の人とを関係を持っているかという風に言い換えることができる。逆に、持っていなければ、その人とは不仲であるということがいえる。関係を持っているかどうかは、人をノードと見立てて、それぞれの関係を無向グラフを使って表現すればよい。

ここで、a[i][j] と a[i][j+1] の人の関係は、N人 × N人分の大きさの隣接リストを使って表現することができる。制約的にはかなりゆるめなので、この解法は通る。

提出コード

<?php

[$N, $M] = sscanf(trim(fgets(STDIN)), "%d %d\n");
$a = [];
for ($i = 0; $i < $M; $i++)
    $a[] = explode(" ", trim(fgets(STDIN)));
$g = array_fill(0, $N, array_fill(0, $N, 0));

for ($i = 0; $i < $M; $i++) {
    for ($j = 0; $j < $N - 1; $j++) {
        [$u, $v] = [$a[$i][$j] - 1, $a[$i][$j + 1] - 1];
        [$g[$u][$v], $g[$v][$u]] = [1, 1];
    }
}

$ans = 0;
for ($i = 0; $i < $N; $i++) {
    for ($j = $i + 1; $j < $N; $j++) {
        if ($g[$i][$j] == 0) {
            $ans += 1;
        }
    }
}
echo $ans, "\n";

C – Dash

回復アイテムがもらえる座標の値を管理する方法が肝。解説にある通り、二次元配列を作れば、時間計算量はO(1) でルックアップできるが、この場合の空間計算量は O(N ^ 2) である。この問題では、最大で 2 x 10 ^ 5個のアイテムが存在しうるので、 仮に 2 次元配列を作った場合4 x 10 ^ 10 のサイズに膨らむことになる。この時、一つの数字を 8 byte で管理している場合、320 GB のRAMが必要になり、当然メモリには乗り切らないし、大部分は無駄になる。したがって、座標を管理するデータ構造は二値の座標データをキーに取ったハッシュテーブルを使って管理すればよい。

PHPでは、Pythonのような集合型を使用できないが、PHPの配列は、もともとハッシュテーブルであるため、キーは一意であり、ルックアップも定数時間で行える。したがって、これをうまく利用すればよい。二値の座標の値は、そのままスペース区切りの文字としてキーに保存し、その値にはその回復アイテムが使われたかどうかを管理するフラグを格納しておけばよい。

提出コード

<?php

[$N, $M, $H, $K] = sscanf(trim(fgets(STDIN)), "%d %d %d %d\n");
$S = str_split(trim(fgets(STDIN)));
$Q = [];
for ($i = 0; $i < $M; $i++) {
    $k = trim(fgets(STDIN));
    $Q[$k] = 1;
}

$c = [0, 0];
$ans = true;
foreach ($S as $i => $v) {
    if ($v == "R") {
        $c = [$c[0] + 1, $c[1]];
    } elseif ($v == "L") {
        $c = [$c[0] - 1, $c[1]];
    } elseif ($v == "U") {
        $c = [$c[0], $c[1] + 1];
    } else {
        $c = [$c[0], $c[1] - 1];
    }
    $H -= 1;
    $k = "$c[0] $c[1]";
    if ($H < 0) {
        $ans = false;
        break;
    } else {
        if (array_key_exists($k, $Q) && $H < $K && $Q[$k]) {
            $Q[$k] = 0;
            $H = $K;
        }
    }
    # echo "Now: ($k) / Health: $H\n";
}

echo (($ans) ? "Yes" : "No"), "\n";