競プロの記録 - Hajimeteの日記

予定していた読書記録ではありませんが、いくつか面白い問題を解いたので精進のため記録します。
全体を通して得られる教訓は「探索の基本は全探索」ということでしょうか。
解説や提出コードを含みますのでネタバレ注意になります。

ABC114 C問題 755

整数N( $1<=N<=10^9$ )より小さい整数のうち、数字の7、5、3を1度以上ずつ使った数字の個数を数える。
という問題です。
自分の考えていた内容としては

条件を満たしつつM桁の整数を作るとき、その整数が $M!*_{3(M-3)}C_{M-3}$ であるので
※実は証明してません、間違いの場合はコメントにてご指摘いただけると幸いです。
2019/02/17追記上記の式間違ってます。
あとはM+1桁の場合で全通り試そうと考えていました。
しかし、桁上がりを考えていると結構面倒で結局時間切れとなりました。

回答を見るとその方針としては、7、5、3を組み合わせた整数を作成して後から条件を満たすかどうか検査するという方法でした。
次のコードは解説コードの丸写しになりますが、かなりかっこいいと思っています。

N = int(input())
 
def dfs(s):
    if int(s) > N:
        return 0
    ret = 1 if all(s.count(c) > 0 for c in '753') else 0
    for c in '753':
        ret += dfs(s + c)
    return ret
 
print(dfs('0'))

これですと計算量が整数の桁数に依るため制限時間内に実行可能になります。
最初から条件を満たすものを考えるのではなく、大まかに数え上げた後に条件を満たさないものだけを切り取っていく方針です。

ARC060 D 桁和 / Digit Sum

整数N( $1<=N<=10^11$ )をb進数で表現した時、各桁を合計した値が整数Sになるかどうかを探索する問題です。
存在する場合には最小のbを出力し、存在しない場合には-1を出力します。
詳しい算出方法は問題にありますが今回は割愛します。

この問題に関しては全くいい方法が思いつきませんでした。
以下は解説を見て自分なりに理解している内容の整理になります。

ひとまず、特殊な場合を先に片付けると

$N = S$ : b=N+1
$N \lt S$ : bは存在しない

ということになります。

次にこれ以外の場合について考えると、bが $\sqrt{N}$ で場合分けできることがわかります。これは $b>\sqrt{N}$ の場合にはNが2桁のb進数で表現できるということに端をなします。Nが2桁になると何がうれしいか言うと、bが一意に求まるようになるからです。
$N=pb+q , p+q=S$
$b=(N-S)/p+1$
これでpを定めることでbが一意に定まりますし、探索範囲を絞ることができたので制限時間内に実行可能になります。

from math import floor
from math import sqrt
 
def f(bb,nn):
    if(nn<bb): return nn
    else: return f(bb,floor(nn/bb))+(nn%bb)
        
 
n=int(input())
s=int(input())
 
if n==s:
    print(n+1)
    exit()
elif n<s:
    print(-1)
    exit()
 # <sqrt(N)まで探索
for i in range(2,int(sqrt(n))+2):
    if s==f(i,n):
        print(i)
        exit()
 
#pが大きいほどbの値は小さくなるので逆順ループで最初に見つかったものが最小
for i in reversed(range(1,int(sqrt(n))+2)):
    if (n-s)%i == 0:
        tmpb=(n-s)//i+1
        if tmpb >= sqrt(n) and f(tmpb,n)==s: 
            print(tmpb)
            exit()
print(-1)

このように割り算で条件を探索するときに、境界条件になりがちな $\sqrt{N}$ は別の問題でもちょっと考えたほうがいいと思います。

まとめ

最初に示した通り「探索の基本は全探索」です。
ここから様々な工夫をもとに計算量の削減を行っていくので、これを最初に考えなかったのがWAの原因かなと反省しております。