AtCoder Beginner Contest 140の振り返りと復習（PHP7）

遅くなりましたが、9月7日（土）にABC140に参加したので、その振り返りと復習です。

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

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

結果

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

今回はDがAC出来ず。無念！

レーティングもそこまで伸びませんでした。

それでもCまで20分以内でAC出来ているのでその点は良かったですし、パフォーマンスも緑は維持出来ているのでまあ良しとしましょう。

コンテスト参加回数も7回になってちょっと慣れてきてCまでのAC時間もそれなりに短くなってきました。

提出したコード

今回もA〜Dのみ。

A – Password


<?php
fscanf(STDIN, '%d', $n);
$ans = $n ** 3;
echo $ans . PHP_EOL;

https://atcoder.jp/contests/abc140/submissions/7381926

Nを3乗して終わり。

B – Buffet


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

https://atcoder.jp/contests/abc140/submissions/7386394

ここまで約10分。

配列の添字に気を付けつつ、追加で得る満足度を足します。

C – Maximal Value


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

https://atcoder.jp/contests/abc140/submissions/7389865

ここまで20分弱。

Aiの最大値がBiとBi-1の小さい方であることに気付けば、あとは足していくだけです。

端っこ（iが0とn-1）の時用にNull合体演算子（??）を使ってますが、ちょっと可読性が低いような。

D – Face Produces Unhappiness

Lが連続するブロックとRが連続するブロックごとに分けて処理する方法で考えましたが、時間内にはAC出来ませんでした。

あとで提出したコード

解説を見てあとで提出し直したコードです。


<?php
fscanf(STDIN, '%d %d', $n, $k);
fscanf(STDIN, '%s', $s);
$i = $top = $cnt = $ans = 0;
$top_s = $s[$top];
while($top < $n) {
    $next_s = ($top_s === 'L') ? 'R' : 'L';
    $next_top = strpos($s, $next_s, $top);
    if ($next_top === false) $next_top = $n;
    $cnt_s = $next_top - $top;
    if ($i % 2 === 1) $cnt++;
    if ($cnt <= $k && $i !== 0) $ans += $cnt_s;
    else $ans += $cnt_s - 1;
    $i++;
    $top_s = $next_s;
    $top = $next_top;
}
echo $ans . PHP_EOL;

https://atcoder.jp/contests/abc140/submissions/7488258

Lが連続するブロックとRが連続するブロックごとに順番に幸せな人の数を集計していきます。

この時、奇数番目（0がスタート）のブロックについては、現れた回数がK回以下の場合は回転させたと考えて幸福な人の増加数を足していきます。

偶数番目のブロックについては、奇数番目のブロックが現れた回数がK回以下の場合は直前のブロックの向きと同じになるので幸福な人の増加数は人数と同じ、奇数番目のブロックが現れた回数がK回を超える場合は幸福な人の増加数は人数−1になります。（ただし左端（0番目）のブロックの幸福な人の増加数は人数−1）

あとで提出したコードその2

奇数番目のブロックの回転処理をして、増加する幸福な人の数は2（右端のブロックだった場合は1）で幸福な人の最大値はN-1なので、もっとシンプルに書くことも出来ます。


<?php
fscanf(STDIN, '%d %d', $n, $k);
fscanf(STDIN, '%s', $s);
$ans = 0;
for ($i = 0; $i < $n - 1; $i++) {
    if ($s[$i] === $s[$i + 1]) $ans++;
}
$ans = min($n - 1, $ans + $k * 2);
echo $ans . PHP_EOL;

https://atcoder.jp/contests/abc140/submissions/7488322

時間内にこの解法を思い付けるようになるイメージが湧かないですが、続けていたらいつか思い付けるようになるんだろうか。