ことさら−古都プログラマーの更級日記

京都でお寺を回りながら御朱印集めをしていたエンジニアのブログ。おもに技術的なはなしとか日常的なはなし

PHPでAtCoder Beginner Contest #029

はじめに

abc029.contest.atcoder.jp

AtCoder Beginner Contest ではレートは変化せず、問題も優しめなので、最近勉強したPHPを使うことにしました。

標準入出力ラッパークラス

とりあえ標準入出力のラッパークラス Scanner を作りました。

<?php
class Scanner {
    private $arr = [];
    private $count = 0;
    private $pointer = 0;

    public function next() {
        if($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(' ', $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        $this->pointer++;
        return $result;
    }

    public function nextInt() {
        return (int)$this->next();
    }

    public function nextDouble() {
        return (double)$this->next();
    }
}

next で半角スペースまで読んでキャストする、普通のScannerです。 そして次は標準出力

<?php
class out {
    public static function println($str) {
        echo $str . PHP_EOL;
    }
}

out::println(...) で一行出力します。とりあえずこれらを使って解いてみることにしました。

結果

  • 全問正解
  • WA1回
  • 66位

f:id:yoshiki_utakata:20150919224204p:plain

今まで育ててきたライブラリが必要な問題もなく、全部PHPで解けました。

f:id:yoshiki_utakata:20150919224200p:plain

解法

A,B

やるだけ

C

DFS

D

説明しづらいのですが

  • 各桁を見る
  • その桁が1になる数字の数を求める: O(1)
    • 入力されたNの各桁について、その桁の数字が 「0」,「1」, 「2以上」 の3パターンで場合分けして計算する。
  • 合計する

といった感じで頑張りました。

<?php

$sc = new Scanner();
$n = $sc->nextInt();
$ans = 0;

for($i = 9; $i >= 0; $i--) {
    $mod = pow(10, $i);
    $m = (int)($n / $mod) % 10;
    $down = ($n % $mod);
    $up = (int)($n / ($mod * 10));
    if($m === 0) {
        $cnt = $up * $mod;
        $ans += $cnt;
    } else if ($m === 1) {
        $cnt =  $up * $mod + $down + 1;
        $ans += $cnt;
    } else {
        $cnt = ($up + 1) * $mod;
        $ans += $cnt;
    }
}

out::println($ans);

終わりに

D問題、なんとなくな方針は合っていたのですが、バグ取りに時間がかかりました。

Scannerクラスがちゃんと動いてよかったです!!!