第2回 ドワンゴからの挑戦状 本選: A - 通勤

https://beta.atcoder.jp/contests/dwango2016-honsen/tasks/dwango2016final_a

問題概要

ニコ数を「10進法で表記したとき各桁が2, 5のみからなり、かつどの隣り合う2桁の数字も相異なる数」と定義する。初め L=1, X=0 である。以下の2種類の操作を自由な順番で好きなだけ行ってXをNに一致させるとき、操作1を行う回数として最小のものを求めよ。

• 操作1: Lに任意のニコ数を掛ける
• 操作2: XにLを加算する。

N <= 10^{18}

解法

例えばN=123で、最初Lに5を掛ける場合を考える。いきなりLに5を掛けると、当然以降の加算は5の倍数刻みでしか行えなくなるため、X=123には永遠にたどりつけない。であるから、Lに5を掛ける前には、5で処理できない端数(123 % 5 = 3)をL=1の段階であらかじめ処理しておく必要がある。よってL=1を3回足してからLに5を掛けると、Nは残り120でL=5となる。実はこのとき両方をLで割って「Nは残り24でL=1」とみなしてしまって問題ない。このようにすると常にLが1に固定されてNがどんどんニコ数で割られていくという再帰的構造が現れるので、あとはメモ化再帰で解くことができる。Nが必ず2以上の数で割られるため状態数はそこまで増えない。

感想

再帰の構造を見出す部分がむじかった

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip, std.regex;

void main() {
    immutable long INF = 10L^18+10;
    auto N = readln.chomp.to!long;

    long[] nico;
    for (long a = 2; a <= N; a = (a % 10 == 2) ? a * 10 + 5 : a * 10 + 2) nico ~= a;
    for (long a = 5; a <= N; a = (a % 10 == 2) ? a * 10 + 5 : a * 10 + 2) nico ~= a;
    auto M = nico.length.to!int;

    long[long] mem;

    long dfs(long n) {
        if (n in mem) return mem[n];
        if (n == 1) return 1;
        if (n == 0) return 0;
        long ret = INF;
        foreach (x; nico) ret = min(ret, dfs(n/x) + n%x);
        mem[n] = ret;
        return mem[n];
    }

    dfs(N).writeln;
}