AtCoder Beginner Contest 029
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倍整数演算ライブラリがあれば通せてたかも。
brainfuckでABC全完が目標です。