第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; }