brainfuck回。3完。

A - 複数形

末尾にsを付ける、つまりecho `cat`sとかsed s/$/s/とかする問題。

+[
    ,
    ----------[++++++++++.>+<[-]]>[<+>-]<
]
++++++++[>++++++++++++++<-]>+++.
<++++++++++.

B - カキ

rを含む行数を数える問題。grep r | wc -l。ただし入力の行数は12で固定なのでbrainfuckerに易しい。

++++++++++++ [> repeat 12
    > total
    [-] > current
    +[- until newline
        ,
        ---------- 10 [
            >++++++++[<------------->-]< not r flag
            >+< [>-<[-]] >[<<+>>-]< unless incr
            >+< not newline flag
        [-]]
        >[<+>-]<
    ]
    < [<+>[-]] if current incr total
    <
<-]
>>++++++++++ 10
<[>>+>+<<<-]>>>[<<<+>>>-]<>+<[[-]>-<<[>>+<<-]>+>>>>>+[<<<<[->+>+<<]>[-<+>]>[-<<<<<-[>]>>>>>>>-<<<<<<[<]>>>>]>+>]<<<<<<<[>]>[>[-<<<+>>>]>>>-<<<<<]>->[-]>>>>>[-]<<[<<<<<+>>>>>-]<<<<<>]>[-<<[-]>>]<< /mod
[>++++++[<++++++++>-]<.[-]] <
>++++++[<++++++++>-]<.[-] <
++++++++++.

C - Brute-force Attack

a,b,cからなる$n$文字の組み合わせを辞書順に列挙する問題。itertools.combinations_with_replacement("abc", n)とかreplicateM n "abc"で可能。

>>>>>
, >++++++[<-------->-]< read n
[[>>>>] +++ <<<< [<<<<] >>>> -] >>>> put 4 0 0 0 n times
[>>>>] + >>>+> + <<<< put 1 0 0 1 and 1 0 0 0 as a guard
[ while the first one exists
    print
    <<<< [>>++++++++++[<++++++++++>-]<< [>->+<<-]>>[<<+>>-]<< >.[-]< <<<<]
    ++++++++++.[-]
    >>>> [>>>>] <<<< <<<<
    update
    [<<<<] > + [ -
        >>> - decr
        [>+>+<<-] >[<+>-] + >[<->[-]] << not
        >[
            >+<
            <+++>
            >>>>>>[<<<-<<->>>>>-]<<<<<<
        -] >[<+>-]<
    ] < [>>>>] >>>> [>>>> >>>>] <<<< <<<< <<<<
]

D - 1

本番通せず。

$1$から$N$までの整を10進表記した際に現われる数字1の数を数える。つまりseq `cat` | tr -cd 1 | wc -cなのだけど、$N \le 10^9$なのでこれでは部分点。 まず見る桁を固定して、その桁に1が現れる回数を考える、とすると分かりやすい。

$10$での割り算掛け算ばかりなので、桁毎の演算を頑張って書けば通りそうなので頑張ってた。でも途中で面倒になってpythonに逃げた。

#!/usr/bin/env python3
n = int(input())
y = 0
xs = list(reversed(str(n)))
for i in range(len(xs)):
    e = 10 ** i
    y += (n + 9*e) // (10 * e) * e
    if xs[i] == '1':
        y -= e
        y += n % e + 1
print(y)

高速な任意精度/4倍整数演算ライブラリがあれば通せてたかも。


AtCoder Beginner Contest 029

brainfuckでABC全完が目標です。