—2025/04/13
今日、Atcoder045回目を挑戦しました。
C問題、たくさんの数式問題について、面白みを感じました。
一連数値の中に、いくつかの場所に + を入れることができます。 一つも入れなくてもかまいません。 ただし、+ が連続してはいけません。
このようにして出来る全ての文字列を数式とみなし、和を計算することができます。
ありうる全ての数式の値を計算し、その合計を求めること。
例えば、125のような数値、考えられる数式は、 125、1+25、12+5、1+2+5 の 4 通りがあります。それぞれの数式を計算すると、
- 125
- 1+25=26
- 12+5=17
- 1+2+5=8
となり、これらの総和は 125+26+17+8=176 となります。
+を入れられる場所をよく見ると、一桁以降から最後の桁前まですべて対象になるので、
典型的な全探索算法。
数値列の長さはNとして、+の入れる場所はN-1と考えられる、全探索可能性は2^N-1になります。
Nは10より小さいので、全探索可能になります。
このように、全探索の実装法を用いて、AC結果が得られました。
全探索に関するのスキルをもっとアップしたいと思います。
crossorigin="anonymous">