AtCoder Regular Contest 108 参加ログ・感想

今回もBが解けるところまでを目標にした。

内容
結果
どう考えたか + α
- A - Sum and Product
- B - Abbreviate Fox
  - TLE
  - AC
おわりに
参考になる書籍

内容

Python3でやっている。
参加ログ。
所感。
コンテスト中に何を考えたか。
コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
問題の詳細で細かく書こうと思うものは別記事とする。

結果

A完。Bは普通にfoxがなくなるまでreplaceってしたらTLEで、頭から消しながらやる実装がよくわからなくなったけど、終了するくらいにあーそうかという感じでできた。

どう考えたか + α

問題

A - Sum and Product

問題タイプ：２次方程式の解

$n + m = s$ , $n \times m = p$ から $n = s - m$ , $n = \frac{p}{m}$ なので、 ${\displaystyle\frac{p}{m} = s - m}$ つまり、 $m^2 -s \times m +p = 0$ を $m$ について解いたときに $n, m$ が正の整数であればいい。なので、 $\sqrt{b^2 - 4ac}$ が整数でかつ $-b -\sqrt{b^2 - 4ac}$ が0以上であればいいとした。ただ、解答見たら、 $p = m \times s - m$ になるようなmが存在するかをfor文で探せばいいだけだった。。。

s, p = map(int, input().split())
b2_4ac = float(s**2 - 4*p) ** (1/2)
if b2_4ac.is_integer() and s - b2_4ac > 0:
    print('Yes')
else:
    print('No')

B - Abbreviate Fox

問題タイプ：文字列操作

最初、findとreplace使えばいいじゃんと思ったら1例でTLEでOrz
TLE

n = int(input())
s = input()
while s.find('fox') >= 0:
        s = s.replace('fox', '')
print(len(s))

ちょっとたって、別リストを持って $s$ の単語を一つずつ突っ込んで、別リストのお尻3つがfoxとなればその3つを消すっていう作業を繰り返す。
AC

n = int(input())
s = input()
t = list()
for i in range(n):
    t.append(s[i])
    if len(t) >= 3 and t[-3:] == ['f', 'o', 'x']:
        for _ in range(3):
            t.pop()
print(len(t))

おわりに

Aは、いちいち２次方程式の解にせずとも範囲を決めて全探索にふればよかった。
Bは、関数使ったら強大なtestはクリアできず、 $O(n)$ に持っていけなかった。関数にこだわりすぎた。

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。