水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

ABC040に参加しました

abc040.contest.atcoder.jp



久々に。3完の2XX位くらいでした。書きたい記事が溜まっているのですが、平日なかなか時間が取れないので厳しいです。


それとコンテストで出したコードがとてもひどかったので一部修正して掲載しております。


A問題

abc040.contest.atcoder.jp

全体の長さと青のブロックが与えられるので、青のブロックをどっちの端に持っていけば近いのかという問題。

先頭への長さを図るとき、渡されている数値は1番目からスタートなので、1を引かないといけないというのが注意ですかねえ(0番目スタートじゃないってことです)


特に理由はないですがawkでときました。

function min(x, y) {
    return x < y ? x : y
}
 
{
    print min($1 - $2, $2 - 1)
}

Submission #774209 - AtCoder Beginner Contest 040 | AtCoder

B問題

abc040.contest.atcoder.jp

個人的に題意の読み取りが非常に難しかったように思います。


長方形の(縦から横を引いた値の絶対値) + (長方形を作った時に余ったタイルの数)の最小値を求めます。ちょっと適当なのですが、入力値Nについて M^2 <= N < (M+1)^2 を満たす数値をとりあえずの最小値として、ループを回します。1からN-1の範囲について長方形を作っていくと、縦がi, 横がint(N / i)になるので、コレを使って絶対値の差、余ったパネルの数を求めて最小値を更新していきます。


で、最近PHPを練習中なのでPHPでときました。ちょっと型がふわふわしていて(python以上な気がする…)扱いにくいですが、少しずつモノにしたいと思います。

<?php
    $N = trim(fgets(STDIN));
    $ans = $N - (int)pow((int)sqrt($N), 2);
    for($i = 1; $i < $N; $i++) {
        $s = abs((int)($N / $i) - $i); // 縦横の絶対値の差
        $t = $N - (int)($N / $i) * $i; // 余ったパネルの数
        $ans = min($ans,  $s + $t);
    }
    echo $ans, "\n";

Submission #774219 - AtCoder Beginner Contest 040 | AtCoder

C問題

abc040.contest.atcoder.jp


パット見でDPですね…。1つ前から飛んだほうが良いのか、2つ前から飛んだほうが良いのかを計算していき、DPの最後を見ればよいです。正直それ以外はあんまりいうことが無いです。DPがわかってるかどうかなんですかねえ。ただ、単純なDPとは言え、しっかりと得点できたのは良かったと思います(DPが非常に苦手)。


この問題もPHPでときました。PHPで配列を扱う場合、$dp[]=$hoge;のようにすると配列の最後に自動的に追加されるっていうのはなかなかおもしろい仕様ですね。使いこなしたいです。

<?php
    $n = trim(fgets(STDIN));
    $arr = explode(" ", trim(fgets(STDIN)));
    $dp = array(0, abs($arr[1] - $arr[0]));
    for($i = 2; $i < $n; $i++) {
        $dp[] = min(
            $dp[$i-2] + abs($arr[$i] - $arr[$i-2]),
            $dp[$i-1] + abs($arr[$i] - $arr[$i-1]));
    }
    echo $dp[$n-1], "\n";


Submission #774226 - AtCoder Beginner Contest 040 | AtCoder


D問題、部分点は幅優先探索っぽいかなあと思いました。どう解けばよいのかさっぱりだったのですが、union-find的な考え方が使えるらしく、その発想に至らなかったことは反省ですね…。


ABCはKeyワンドロと時間がもろかぶりなので、今後参加回数が経ると思います。その代わりARCではしっかりと3完狙ってレーティング入りを目指したいですね。