AtCoder Beginner Contest 137の復習（PHP7）

AtCoder Beginner Contest 137に参加したので復習します。

先週に続いて2回目の参加です。

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

結果

コンテスト成績証 – AtCoder

言語は今回もPHP7で、パフォーマンスは茶色でした。

今回はCのTLE突破に時間がかかってしまい、Dを解く時間の余裕がありませんでした。悔しい！

ABCD正解の人が前回の半分以下の1000人くらいしかいないのを見ると、Cで苦しんだ人が多かったのかもしれません。

提出したコード

ABCDのみです。

A – +-x


<?php
fscanf(STDIN, '%d %d', $a, $b);
 
echo max($a+$b, $a-$b, $a*$b).PHP_EOL;

提出 #6801939 – AtCoder Beginner Contest 137

およそ2分。

B – One Clue


<?php
fscanf(STDIN, '%d %d', $k, $x);
$start = $x - $k + 1;
$end = $x + $k - 1;
for ($i = $start; $i <= $end; $i++) {
    echo $i;
    if ($i === $end) echo PHP_EOL;
    else echo ' ';
}

提出 #6807564 – AtCoder Beginner Contest 137

制約から黒く塗られる石が端っこに来ることはないので、単純な足し引きで求まりました。

ここまでおよそ8分。

C – Green Bin


<?php
fscanf(STDIN, '%d', $n);
$cnt = 0;
$arr = [];
for ($i  = 0; $i < $n; $i++) {
    $s = str_split(trim(fgets(STDIN)));
    $j = $s;
    sort($s);
    $j = implode('', $s);
    if (is_null($arr[$j])) {
        $arr[$j] = 1;
    } else {
        $arr[$j]++;
        if ($arr[$j] === 2 ) {
            $cnt++;
        } elseif ($arr[$j] > 2) {
            $cnt += $arr[$j]*($arr[$j]-1)/2 - ($arr[$j]-1)*($arr[$j]-2)/2;
        }
    }
}
echo $cnt.PHP_EOL;

提出 #6829582 – AtCoder Beginner Contest 137

文字列をソートするところは、1文字ずつの配列に格納→配列をソート→結合して文字列に戻すというやり方でやってます。

アナグラム文字の出現回数を集計するために、ソートした文字列自身をキーとした連想配列に出現回数を保存していきました。

ただこのコードだと動くことは動きますしACにはなるのですが is_null($arr[$j]) のところで PHP Notice: Undefined index が出るので、array_key_exists でキーの存在を確かめる方が良かったですね。

あと出現回数の集計の部分がちょっと冗長な気がします。

ここのTLEがなかなか突破出来ず、やっとACになったのが約94分でした。

改善したコード


<?php
fscanf(STDIN, '%d', $n);
$cnt = 0;
$arr = [];
for ($i  = 0; $i < $n; $i++) {
    $s = str_split(trim(fgets(STDIN)));
    sort($s);
    $s = implode('', $s);
    if (array_key_exists($s, $arr)) {
        $arr[$s]++;
        $cnt += $arr[$s] - 1;
    } else {
        $arr[$s] = 1;
    }
}
echo $cnt.PHP_EOL;

提出 #6839836 – AtCoder Beginner Contest 137

だいぶスッキリしました！ PHP Notice も出なくなり、実行時間も速くなりました。

implode は引数を配列1つのみにすると間には何も入れずに結合してくれるようですが、第一引数に空文字列を入れておいた方が分かりやすいのでそのままにしてます。

D – Summer Vacation

Cに時間かけすぎて全く実装時間が足りず提出出来ませんでした。

残り1日から順に考えていって選べる最大報酬の仕事をこなしていけば報酬が最大になるんじゃないかというところまでは考えてただけに残念！

あとで提出したコード


<?php
fscanf(STDIN, '%d %d', $n, $m);
$s = array_fill(1, $m, NULL);
for ($i  = 0; $i < $n; $i++) {
    fscanf(STDIN, '%d %d', $a, $b);
    $s[$a][] = $b;
}
 
$cnt = 0;
$q = new SplPriorityQueue();
for ($i = 1; $i <= $m; $i++) {
    foreach ($s[$i] as $v) {
        $q->insert($v, $v);
    }
    if (!$q->isEmpty()) $cnt += $q->extract();
}
echo $cnt.PHP_EOL;

提出 #6834875 – AtCoder Beginner Contest 137

SplPriorityQueue クラス（優先度付待ち行列）を使うと、選べる仕事の中から報酬が最大のものを取り出す処理が簡単にかけました。