naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Regular Contest 084

土曜21時のARCに出た(けど1完でレート微減)
AtCoder Regular Contest 084 - AtCoder

f:id:n4_t:20171105114655p:plain

C: Snuke Festival

上、中、下をそれぞれソートしておいて、
中それぞれが上に何個置けるかlower_bound()を使って調べ、累積和を計算しておいて、
下それぞれが上に置ける最後のパーツをlower_bound()で探してそこに記録した累積和を得て、その合計
AC

D: Small Multiple

(コンテスト中に考えてたやつ)

任意の数Aの10進数表現
$$ A = ... a_6 a_5 a_4 a_3 a_2 a_1 a_0 = \sum_{i=0}^{\infty} a_i 10^i $$
但し 0 ≦a_I≦9 ね
$$ A\ mod\ K = \sum_{i=0}^{\infty} a_i 10^i\ mod\ K = \sum_{i=0}^{\infty} (a_i (10^i\ mod\ K))\ mod\ K $$
これが0になるようなa_iの組み合わせで、Σa_iの最小値を求めたい。
(1 mod K), (10 mod K), (100 mod K), ..., (10^i mod K),... を(それぞれ0〜9個ずつ)組み合わせて x≡0 (mod K) なxを作る。

a_iが最大9個ではKの倍数が表現できないようなKがあるのでは?と一瞬思ったけど、
Kそのものだって10進表現できてる(K=Σb_i 10^i の形で表せてる)んだからそれはない。

0 のノードからスタートして、+(10^i mod K) な辺が各ノードから生える感じのグラフでK、というか0 (mod K) を目指す。
(※実際のところ Kを目指してしまっていて 2K, 3K, ... を考慮に入れず、あと (10^i mod K)=0 になる数を捨ててしまっていたので正しい答えの出ないコードになっていた)

■K=6の場合:
1 mod 6 = 1
10 mod 6 = 4
100 mod 6 = 4
...
(1を9回まで、4を無限回使える)
f:id:n4_t:20171105112439p:plain
■K=41の場合:
1 mod 41 = 1
10 mod 41 = 10
100 mod 41 = 18
1000 mod 41 = 16
10000 mod 41 = 37
100000 mod 41 = 1
...
({1,10,18,16,37} をそれぞれ無限回使える)
f:id:n4_t:20171105112517p:plain
■この方法の弱点
周期性があるので計算量が減るんだけど、
周期が K-1 になるケースではほぼ全結合だし、(例えばK=65537とか)グラフでの計算はきつい。
1とK-1が必ず使えるから答えは2になるのだけれど。

(解説にある方法に近づける)

10進法で何らかの数を書き下す時、左から1桁ずつ書いていくんだけど、このプロセスは
(1)「そこに a (0≦a≦9) を書く」=「それまでに書いた数にaを足す」
(2)「次の桁を書き始める」=「それまでに書いた数を10倍する」
の2つの動作に分解できる。(1),(2)の組み合わせでどんな整数でも(負号については定義していないのでまあ当然非負整数に限るが。スペースが許す限り)10進表現で書き下せる。

最初ゼロ(というか空白)から初めて、(1) (2) の組み合わせでKの倍数、即ち mod K = 0 となるような数を作りたい。

書いた数の合計は (1) で書いた a の合計で、(2) は何回やっても影響しない。
(1) はさらに、0〜9個までのインクリメントとして分解することも可能で、

(1') それまでに書いた数に+1(書いた数の合計も+1):x' = x+1
(2) それまでに書いた数を10倍(書いた数の合計は不動):x' = 10x

// 非負整数 x のラベルがついたノード(無限にある)の各々から矢印が2本ずつ(片方はコスト1、もう片方はコスト0)が生えたグラフのイメージ。

【追記】(1) を (1') に分解するにあたって、本来 (1') は連続最大9回までしか使えないのだけれどそのチェックをしなくていいのかという問題。(x+10) % K = (x/10+1)*10 % K で、繰り上がった先の数へは別ルートで「先に」到達済み(より浅い位置にある)なのでBFSが答えを出すまでの間に10回目を踏むことはない。具体的に言うと、例えば229(0→1→2→20→21→22→220→221→222→...→229、でコスト13)に1を足して得られる230へは、23経由のルート(0→2→23→230、でコスト5)の方が早く到達する。繰り上がるのは常に遠回りのルート。

この2つの組み合わせで mod K=0 となる数にたどり着く最短手を探せばよい。

(1') x' = (x+1) % K (コスト1)
(2) x' = (10x) % K (コスト0)

// K個のノード x : {0,...,K-1} があって、各ノードから矢印が2本ずつ(片方はコスト1、もう片方はコスト0)が生えたグラフになる。
f:id:n4_t:20171105112546p:plain

【追記】K個のノードだけでいい(% K だけ見てればいい)のは、K進法で見たとき下一桁の変化にだけ注目して、0になる最短経路を探ればいいのと同義。

x=0 (≡0 mod K) は解に含まないので、0手で0に到着、というのは除外したい。

x > 0 のとき、10進表現の最上位は必ず≧1である。ということは、必ず (1') のアクションから始まるので、(START)→(ノード1) にコスト1の矢印を引いて、(ノード0)をGOALにする事でSTART 〜 GOALの最短コスト経路を求める問題になる。
f:id:n4_t:20171105112629p:plain

とりあえずpriority_queueを使った解法でACできたけど、解説曰く(dequeを使った)01BFSならO(K)で解ける、とのこと。あとで書く。
書いてみた↓

01-BFS解法

01-BFSのチュートリアルがこどふぉにあったのを読んだ
0-1 BFS [Tutorial] - Codeforces

エッジの重みが0か1に限定されたグラフの場合、BFSの過程のある時点にキューに乗っているノードの最深と最浅の差が高々1であることを利用すると(priority_queueを使うまでもなく)dequeの両端の操作のみでこれが可能となる、という話。
常に、+0の操作をfront側、+1の操作をback側に行う。

例:
・スタート: [0]
・先頭の0を取って、0(=0+0)と1(=0+1)を追加: 0 + + 1 -> [01]
・先頭の0を取って[1]、0(=0+0)と1(=0+1)を追加: 0 + [1] + 1 -> [011]
・先頭の0を取って[11]、1(=0+1)を追加: [11] + 1 -> [111]
・先頭の1を取って[11]、1(=1+0)と2(=1+1)を追加: 1 + [11] + 2 -> [1112]

比較のために、priority_queueを使った実装とdequeを使った実装を以下に並べてみる。
■priority_queueを使った解法

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;

int solve(int K) {
    priority_queue<ii> pq;
    vector<int> vis(K, 0);

    pq.push(ii(-1, 1));
    while (!pq.empty()) {
        ii p = pq.top(); pq.pop();
        int cnt = -p.first, curr = p.second;
        if (curr == 0) return cnt;

        vis[curr] = 1;
        int next = (curr + 1)% K;
        if (vis[next] == 0)
            pq.push(ii(-(cnt+1), next));

        next = (curr * 10) % K;
        if (vis[next] == 0)
            pq.push(ii(-cnt, next));
    }
}

int main() {
    int K; cin >> K;
    cout << solve(K) << endl;
    return 0;
}

→AC (1169ms)

■01-BFSを用いた解法

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;

int solve(int K) {
    deque<ii> dq;
    vector<int> vis(K, 0);

    dq.push_front(ii(1, 1)); // num(%K), cost
    while (!dq.empty()) {
        ii p = dq.front(); dq.pop_front();
        int curr = p.first, cnt = p.second;
        if (curr == 0) return cnt;

        vis[curr] = 1;
        int next = (curr + 1)% K;
        if (vis[next] == 0)
            dq.push_back(ii(next, cnt+1));

        next = (curr * 10) % K;
        if (vis[next] == 0)
            dq.push_front(ii(next, cnt));
    }
}

int main() {
    int K; cin >> K;
    cout << solve(K) << endl;
    return 0;
}

AC (9ms)

■差分
dequeの場合(num,cost)の順番は関係ないしcostを負にしなくてもいいんだけど
敢えて差分が小さくなるように手を加えたもので比較すると

--- d_pq.cc	2017-11-05 13:46:51.000000000 +0900
+++ d_01bfs.cc	2017-11-05 13:50:27.000000000 +0900
@@ -3,23 +3,23 @@
 typedef pair<int,int> ii;
 
 int solve(int K) {
-    priority_queue<ii> q;
+    deque<ii> q;
     vector<int> vis(K, 0);
 
-    q.push(ii(-1, 1)); // -cost, num(%K)
+    q.push_front(ii(-1, 1));
     while (!q.empty()) {
-        ii p = q.top(); q.pop();
+        ii p = q.front(); q.pop_front();
         int cnt = -p.first, curr = p.second;
         if (curr == 0) return cnt;
 
         vis[curr] = 1;
         int next = (curr + 1)% K;
         if (vis[next] == 0)
-            q.push(ii(-(cnt+1), next));
+            q.push_back(ii(-(cnt+1), next));
 
         next = (curr * 10) % K;
         if (vis[next] == 0)
-            q.push(ii(-cnt, next));
+            q.push_front(ii(-cnt, next));
     }
 }

■余談
AtCoderさん、C++14で (GCC 5.4.1) と (Clang 3.8.0) が選べるのね(いま知った)