Todoistで見積時間から完了予定時刻を計算するChrome拡張機能

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

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

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

結果

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

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

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

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

最後に

Cはまだ力不足が否めませんでしたが、ABについてはもっと短時間で解くことも出来たなぁという印象でした。

ABについては以下の2点が原因で時間がかかってしまったので、次回以降注意しようと思います。

  1. ceil()、floor()、round()の返り値はfloat型になる
  2. あまりを求めよ系の問題の計算途中でのあまりの求め方

2についてはこちらの記事が詳しかったです。

「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜 – Qiita

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA