AtCoder Beginner Contest 138の復習（PHP7）

8月18日（日）にABC138に参加したので、その振り返りと復習です。

なんか最近はAtCoderの記事ばっかり書いてるなーw

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

結果

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

ABCを開始約12分でACしてDも開始約45分（1回TLEだったのでペナルティー入れると約50分）でAC出来たので、自分としてはかなり上出来・満足な結果でした。

残りの時間はEに挑戦してみましたが、時間内にACは出来ませんでした。

Eも時間内にAC出来るようになりたいですね。

提出したコード

A – Red or Not


<?php
fscanf(STDIN, '%d', $a);
fscanf(STDIN, '%s', $s);
if ($a >= 3200) $ans = $s;
else $ans = 'red';
echo $ans . PHP_EOL;

https://atcoder.jp/contests/abc138/submissions/6981822

三項演算子使った方がシンプルで良かったかも。

B – Resistors in Parallel


<?php
fscanf(STDIN, '%d', $n);
$a = array_map('intval', explode(' ', trim(fgets(STDIN))));
 
$ans = 0;
for($i = 0; $i < $n; $i++) {
    $ans += 1 / $a[$i];
}
$ans = 1 / $ans;
echo $ans . PHP_EOL;

https://atcoder.jp/contests/abc138/submissions/6984651

素直に実装してます。

C – Alchemist


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

https://atcoder.jp/contests/abc138/submissions/6990475

問題文が長くて理解するのに少し時間がかかりました。

価値を最大化するためには、毎回小さなものから二つを選べば良さそうと気付けば、あとは小さいものから二つ取り出す方法を考えるだけです。

生成した具材も再び選べるということで、最近覚えたばかりの優先度付き待ち行列を使って実装しました。

ここまでで開始約12分でAC。

D – Ki


<?php
fscanf(STDIN, '%d %d', $n, $q);
for ($i  = 0; $i < $n - 1; $i++) {
    fscanf(STDIN, '%d %d', $a, $b);
    $a--;
    $b--;
    $g[$a][] = $b;
}
$r = array_fill(0, $n, 0);
for ($i  = 0; $i < $q; $i++) {
    fscanf(STDIN, '%d %d', $p, $x);
    $r[$p - 1] += $x;
}
$point = array_fill(0, $n, 0);
dfs($g, 0, 0, $r, $point);
$ans = implode(' ', $point);
echo $ans . PHP_EOL;

function dfs($g, $v = 0, $x = 0, $r, &$point) {
    if (isset($r[$v])) $x += $r[$v];
    $point[$v] += $x;

    if (!isset($g[$v])) return;
    foreach ($g[$v] as $next_v) {
        dfs($g, $next_v, $x, $r, $point);
    }
}

https://atcoder.jp/contests/abc138/submissions/7000087

アルゴリズムを勉強する過程でライブラリー化しておいたDFS（深さ優先探索）を使って実装しました。

ライブラリー化したものが何か使えそうと思ってからDFSに到るまで時間がかかったので、まだまだ慣れが必要ですね。

今回の問題のおかげで部分木→DFSという連想が出来るようになったと思うので良かったです。

ただ今回は親よりも子の頂点の番号が必ず大きいという制約が付いていたため順番に処理するだけでも良かった模様。

入力例2で、Q回の操作の中には同じ根が複数回選ばれる場合もあると教えてくれなかったら、多分WA出してただろうなーという問題でした。

ここまでで開始約45分。