AtCoder Regular Contest 106 参加ログ・感想

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

---

内容

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

---

結果

A完。BはUnion-Findでつながっているindexをだしてそれらのの和との和の一致していればOKと思って実装したがTLEで計算量を見積もれず狩猟。

---

どう考えたか + α

A - 106

問題タイプ：全探索

3の38乗、5の26乗が超えるところだから、全探索で行けると判断。

n = int(input())
for i in range(1, 39):
    diff = n - 3**i
    for j in range(1, 27):
        if diff - 5**j == 0:
            print(i, j)
            exit()
print('-1')

---

B - Values

問題タイプ：グラフ・Union-Find

• 連結している部分を見つける。
• その連結しているindexのの和と の和が全て一緒かを確認する。

これでいいはず。 自分の実装ではTLEでうまくいかなかった。 もうちょっとでできそうなので、別記事にする。

---

おわりに

Aは制約が大きいから厳しいと思ったが、累乗だからになる系だなと思えてそのまま実装できた。 BはUnion-Findでやるんだろうなと思って実装したが連結成分の和を計算する過程でTLEが続いてしまった。

---

参考になる書籍

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

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

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

書籍は読み終わったので、Pythonで章末問題をこなしていっている。

blacktanktop.hatenablog.com