AtCoder Beginner Contest 141の復習（PHP7）

9月15日（日）にABC141に参加したのでその復習です。

今回もPHP7での参加で通算8回目のコンテスト参加でした。

結果
提出したコード
最後に

結果

https://atcoder.jp/users/hideyuk1/history/share/abc141

Dまで30分以内にAC出来てかなり僕としては良い結果でした！

パフォーマンスも緑の中でも上位で、AGCを除けば過去最高パフォーマンスでした。

レーティングも緑まであと19！

来週のABCとAGCに参加すれば届きそうなので忘れずに参加したいところです。

提出したコード

今回もA〜Dのみです。

A – Weather Prediction


<?php
fscanf(STDIN, '%s', $s);
if ($s === 'Sunny') $ans = 'Cloudy';
elseif ($s === 'Cloudy') $ans = 'Rainy';
elseif ($s === 'Rainy') $ans = 'Sunny';
echo $ans . PHP_EOL;

https://atcoder.jp/contests/abc141/submissions/7517001

switch文を使った方が良いかもしれません。

B – Tap Dance


<?php
fscanf(STDIN, '%s', $s);
$n = strlen($s);
$ans = 'Yes';
for ($i = 0; $i < $n; $i++) {
    if (($i % 2 === 0 && $s[$i] === 'L') || ($i % 2 === 1 && $s[$i] === 'R')) {
        $ans = 'No';
        break;
    }
}
echo $ans . PHP_EOL;

https://atcoder.jp/contests/abc141/tasks/abc141_b

‘U’, ‘D’ についてはどこにあっても「踏みやすい」文字列になるため、「踏みにくい」文字列になる条件は奇数文字目が ‘L’ または偶数文字目が ‘R’ の場合だと分かります。

コードでは0文字目からスタートしているので奇数と偶数が問題文と反対になっています。

ここまで約9分でした。

C – Attack Survival


<?php
fscanf(STDIN, '%d %d %d', $n, $k, $q);
$arr = array_fill(0, $n, 0);
for ($i  = 0; $i < $q; $i++) {
    fscanf(STDIN, '%d', $a);
    $arr[$a - 1]++;
}
for ($i = 0; $i < $n; $i++) {
    if ($k - $q + $arr[$i] > 0) echo 'Yes' . PHP_EOL;
    else echo 'No' . PHP_EOL;
}

https://atcoder.jp/contests/abc141/submissions/7525858

つど N – 1 人のポイントを −1 するのは面倒ですし計算量も大きくなってしまうので、まずは $arr に各参加者の正解数だけを集計していきました。

最終的な参加者のポイントは、

最終的な参加者のポイント = 初期ポイント – クイズ数 + その参加者の正解数

となるのであとは参加者ごとに0超えるかどうか判定して判定結果を出力して終わりです。

ここまで約17分でした。

D – Powerful Discount Tickets


<?php
fscanf(STDIN, '%d %d', $n, $m);
$a = array_map('intval', explode(' ', trim(fgets(STDIN))));
$q = new SplPriorityQueue;
for ($i = 0; $i < $n; $i++) {
    $q->insert($a[$i], $a[$i]);
}
$i = 0;
while ($i < $m) {
    $x = $q->extract();
    $x = $x / 2;
    $q->insert($x, $x);
    $i++;
}
$ans = 0;
while ($q->count() > 0) {
    $ans += (int)floor($q->extract());
}
echo $ans . PHP_EOL;

https://atcoder.jp/contests/abc141/submissions/7529757

商品の中から最も値段が高いものに割引券を1枚使い、割引券を使った商品の値段を割引後の値段に更新

を割引券がなくなるまで繰り返せば最も安く全商品を買えそうだと分かります。

そして最大値（または最小値）を取り出すという処理は優先度付待行列（PHPの場合は SplPriorityQueue）を使うと楽に実装できます。

PHP: SplPriorityQueue – Manual

過去問をやっていても思いますが、優先度付待行列は使う機会が結構多いですね。

ここまで約29分でした。