第一回日本最強プログラマー学生選手権-予選-の復習（PHP7）

8月24日（土）にAtCoderの「第一回日本最強プログラマー学生選手権-予選-」が開催されていました。

学生じゃないから僕には関係ないなと思ってたんですが、予選については学生じゃなくても参加可能かつRatedとのことで、ならば！とすぐに参加登録しました。

学生選手権予選、今日午後９時からだよー！学生以外も予選は出れるしRatedだから出てねー！！！https://t.co/7GhUaCgUB9
— chokudai(高橋直大)🍆🍡🌸 (@chokudai) August 24, 2019

結果
提出コード
最後に

結果

https://atcoder.jp/users/hideyuk1/history/share/jsc2019-qual

ABのみAC出来て、パフォーマンスは842（緑色）でした。

ABで結構時間をかけてしまい、Bに至っては途中の計算であまりの求め方を誤りWAを6回も出してしまいました。

何とか水色パフォーマンスを出せるところまでは成長したいですが、そう簡単にはいきませんね。

提出コード

Cまでの問題のみです。（Cは時間内にAC出来ていません）

A – Takahashi Calendar


<?php
fscanf(STDIN, '%d %d', $m, $d);
$ans = 0;
for ($i = 1; $i <= $m; $i++) {
    for ($j = 1; $j <= $d; $j++) {
        $d1 = $j % 10;
        $d10 = floor($j / 10);
        if ($d1 >= 2 && $d10 >= 2 && (int)($d1 * $d10) === $i) $ans++;
    }
}
echo $ans . PHP_EOL;

https://atcoder.jp/contests/jsc2019-qual/submissions/7110465

配点は200点なのでABCのB相当。

(int)($d1 * $d10) === $i で左辺をint型にキャストしているのは $d10 がfloorの結果float型になっているため、キャストしないと厳密な比較では常に型違いでfalseになってしまうから。

最初はキャストするのを忘れていて、気付いてAC出来るまで14分ほどかかってしまった。

B – Kleene Inversion


<?php
define('MOD', 10 ** 9 + 7);

fscanf(STDIN, '%d %d', $n, $k);
$a = array_map('intval', explode(' ', trim(fgets(STDIN))));

$cnt1 = $cnt2 = 0;
for ($i = 0; $i < $n; $i++) {
    for ($j = 0; $j < $n; $j++) {
        if ($i === $j) continue;

        if ($i < $j && $a[$i] > $a[$j]) $cnt1++;
        elseif ($i > $j && $a[$i] > $a[$j]) $cnt2++;
    }
}

$x1 = (1 + $k) * $k / 2 % MOD;
$x2 = (1 + $k - 1) * ($k - 1) / 2 % MOD;
$ans = (($cnt1 * $x1) % MOD + ($cnt2 * $x2) % MOD) % MOD;
echo $ans . PHP_EOL;

https://atcoder.jp/contests/jsc2019-qual/submissions/7117767

配点は300点なのでABCのC相当。

まずはK回の繰り返しは考えずにAの各数字について「自分より後ろで自分より小さいもの」と「自分より前で自分より小さいもの」をそれぞれカウント。

次にK回の繰り返しを考えて「自分より後ろで自分より小さいもの」「自分より前で自分より小さいもの」1個につきそれぞれ何個の転倒数か求めて、最終的な答えを計算した。

最初は$x2（「自分より前で自分より小さいもの」1個あたりの転倒数）を $x2 = $x1 – $k; として求めていたため、余りをとる関係でWAを連発してしまった。

AC出来たのは開始後約78分。

C – Cell Inversion

配点は500点なのでABCのE相当。

左端と右端は必ずB、その他はBのところは奇数回、Wのところは偶数回反転させる必要ありというところまで考えて、これをどうやって実装するか考えている間に時間切れでした。

あとで提出したコード


<?php
define('MOD', 10 ** 9 + 7);

fscanf(STDIN, '%d', $n);
fscanf(STDIN, '%s', $s);

if ($s[0] === 'W' || $s[2 * $n - 1] === 'W') {
    echo (0) . PHP_EOL;
    exit();
}

$lr[0] = 'L';
$l_cnt_sum[0] = 0;
$l_cnt_sum[1] = 1;
$l_cnt = 1;
$r_cnt = 0;
$x = 1;
for ($i = 1; $i < 2 * $n; $i++) {
    if ($s[$i] !== $s[$i - 1]) {
        if ($lr[$i - 1] === 'L') $lr[$i] = 'L';
        else $lr[$i] = 'R';
    } else {
        if ($lr[$i - 1] === 'L') $lr[$i] = 'R';
        else $lr[$i] = 'L';
    }
    if ($lr[$i] === 'L') {
        $l_cnt_sum[$i + 1] = $l_cnt_sum[$i] + 1;
        $l_cnt++;
    } else {
        $x = $x * ($l_cnt_sum[$i] - $r_cnt) % MOD;
        $l_cnt_sum[$i + 1] = $l_cnt_sum[$i];
        $r_cnt++;
    }
}

if ($l_cnt !== $r_cnt) {
    echo (0) . PHP_EOL;
    exit();
}

$ans = $x * kaijou($n) % MOD;
echo $ans . PHP_EOL;

function kaijou($n) {
    return $n > 1 ? $n * kaijou($n - 1) % MOD : 1;
}

https://atcoder.jp/contests/jsc2019-qual/submissions/7128920

ゆっくり考えてみても分からなかったので解説を参考に実装。

理解は出来ましたが、将来的にこのレベルの解法を時間内に自分で思い付けるかと考えると自信ないですね。

もっと慣れてくると変わってくるんだろうか。