ABC114 C問題感想を述べるだけ

どうもーーーーーー

皆様におかれましてはこの乾燥の季節、肌も鼻もカサカサのことと存じ上げます。

鼻がマジで死んでます。

おそらく次ぐらいでAtCoderの問題で、鼻に石を詰める問題が出てくる予感がします。

そんなことはさておき、とりあえず解いた問題の感想を書きたいと思います。

今回のターゲットはABC114
atcoder.jp

A:
単純に実装

B:
こちらも制限が非常に狭い値なので、普通に見ていけば良いと思いました。
以下解答です。
（ちなみに上のテンプレ部分は初めてコンテストが終わった後、入力とかみんなどうやっとんー、って思って
pythonで一番強そうな人のを拝借して以降、毎回使わせていただいてます。。）

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    S = input()

    # 10文字までしかないので、一個ずつ見ていっても良いのでは
    result = 10**10
    for i in range(0, len(S) - 2):
        result = min(abs(753 - int(S[i:i+3])), result)

    print(result)


main()

この回のCはちょっと難しかったですねー。
普通にリアルタイムでやってたら時間足りなかっただろうなー。
怖いこわい。

まず値がでかい。
Nが10**10まである。
試しに実直にやろうと思って、
[i for i in range(10**10)]
とかやると全然無理で、10**7ぐらいでようやく処理できるレベルでした（たしか

というわけで、一筋縄ではいかないと思い、別の策を考えました。

重複組合せがー、とか、一旦7にしてみよう？とか、さまよったあげく、
結果、桁数に着目しようと思いました。
10桁の場合に、各桁で3 or 5 or 7を選んで入れて、3 and 5 and 7が入っていなければそれを引くというイメージでした。
場合の数としては3**10なので、60000程度。
全然大丈夫そうです。

問題はどうやって全桁分回すか。

こういうのはループでは意外に思ったように回せず。

そこで初めて競プロらしいことをできました。

蟻本で最初に出てくるdfs。

再帰本当に嫌いなのですが、なんとか自力でdfsを作ることができ、見事解答することができました。

こちらは何回かやってきれいにした解答

def main():
    global result, S
    S = int(input())
    result = 0
    bfs(0, '')
    print(result)


def bfs(i, s):
    global result, S
    if s != '' and int(s) <= S and len(set(s)) == 3:
        result += 1
    if i == len(str(S)):
        return
    i += 1
    bfs(i, s + '3')
    bfs(i, s + '5')
    bfs(i, s + '7')


if __name__ == '__main__':
    main()