数学超苦手な文系エンジニアがAtCoder Beginner Contest 269に参加してみました

こんにちは、AWS事業本部コンサルティング部に所属している今泉（@bun76235104）です。

皆さんはアルゴリズムと数学に強くなりたいですか？

私はなりたいです。

私は以前よりAtCoderという競技プログラミングのサービスでコンテストに出て学習をしています。（前回のコンテストの出場の際に書いた記事はこちらです）

今回も 9/17に開催されたUNICORNプログラミングコンテスト2022（AtCoder Beginner Contest 269）に参加させていただきましたので、学んだことをアウトプットさせていただきます。

前置き・事前知識

こちらの記事の前置き・事前知識をご参照ください。（見ていただきたい内容が増えたらこちらを更新させていただきます）

想定される読者の方について

こちらも、この記事の段階から変わっておりませんのでご参照ください。 （競プロ中級者以上の方であれば、特に学べることも刺激を受けられることも無いかもしれませんのでご了承ください）

コンテスト参加結果

私は毎回の目標を以下のように2段階設定しています。

• 最低限の目標： A・B問題の2問を解く
• チャレンジ目標： C問題（もしくはD問題）を解く

今回はチャレンジ目標としているC問題を解くことができましたが、他の参加者の方も解けている人数が多いため、相対的にレートの上がり幅は今一歩というところでした。

A・B問題しか解けなかった前回よりもレートの上がり幅が少ないというのが、相対評価の面白いポイントですね。

A問題 Anyway Takahashi

整数 a,b,c,d が与えられるので、以下の指示に従って 2 行出力してください。

1 行目は (a+b)×(c−d) の計算結果を整数として出力してください。

2 行目は入力にかかわらず Takahashi と出力してください。

2行目に出力するTakahashiが不思議な魅力を醸し出しています。

こちらに関しては、素直に a b c d の整数をint型で受け取って素直に計算するだけで良さそうです。

私が実際に提出したコードはこちらです。（１分４秒ほどで提出）

a, b, c, d = list(map(int, input().split()))
print((a + b) * (c - d))
print("Takahashi")

こちらについては基本的な四則演算ができれば特に困ることもないかと思います。

B問題 Rectangle Detection

一瞬何を言いたいのかよくわからなくなってしまった問題です。

サンプルを見ることでわかりやすくなりました。

以下ような形で10行、10列の入力が与えられるので、それぞれA,B,C,Dに該当する数値を出力するという問題になります。

..........
..........
..........
..........
...######. ←#が初めて現れる行番号がA(5)
...######.
...######.
...######. ←#が終了する行番号がB(8)
..........
..........
   ↑ #が初めて現れる列番号がC(4)
        ↑ #が終了する列番号がD(9)

今回は10行・10列しか入力がありませんので、すべてのマスを探索して行ってもたかだか100しかありません。

よって普通に二重ループでA,B,C,Dの位置をみていけば良さそうです。

私がコンテスト中に提出したコードはこちらになります。（A問題提出から6分40秒程で提出）

S = [list(input()) for _ in range(10)]
A = 11
B = 11
C = 11
D = 11

for i in range(10):
    s = S[i]
    if s.count("#") > 0:
        A = min(A, i + 1)
        B = max(A, i + 1)
        for j in range(10):
            if s[j] == "#":
                C = min(C, j + 1)
                D = max(C, j + 1)
print(A, B)
print(C, D)

コンテスト中で慌ていたので、ちょっとまとまりがないコードになっています。お恥ずかしい限りです。

以下のように書き直した方がシンプルになると思います。

S = [list(input()) for _ in range(10)]
A = 11
B = -1
C = 11
D = -1

for i in range(10):
    for j in range(10):
        s = S[i][j]
        if s == "#":
            A = min(A, i + 1)
            B = max(B, i + 1)
            C = min(C, j + 1)
            D = max(D, j + 1)
print(A, B)
print(C, D)

今回のように、初めて出現する位置 最後に出現する位置 のような問題では min max の関数を利用することで、if分岐や、初めて出現したフラグ管理などをする必要がなくシンプルになるため良いですね。

C問題 Submask

非負整数 N が与えられるので、以下の条件を満たす非負整数 x を昇順に全て出力してください。

x を 2 進数として表記した時に 1 となる位の集合が、 N を 2 進数として表記した時に 1 となる位の集合の部分集合となる。

思わず「ん？」となりましたが、こちらもサンプルを見ることで意味がわかりました。

一番簡単なのは0からNまで1つずつ数値をみていき、条件を満たすかか確認することです。

Nが最大で2の60乗と非常に大きいため、制限時間の2秒以内には終了しません。(参考： EX21 - 計算量の見積もり)

計算量という考えはC問題では毎回のように考える必要があり、競技プログラミングの楽しいところでもあります。

以下に私がC問題回答に至ったまでの考え方のステップを書いていきます。

C問題回答までの思考 ステップ1 条件の対偶を考えてみる

すなわち、全ての非負整数kについて、「xの2のk乗 の位が1ならば、Nの2のk乗 の位は1」が成り立つ。

とわざわざ書いてくださっていますが、与えられている整数はNであるため、Nを主体として考えたいなと思いました。

Nが○○ならば、xは△△ という条件をみたいということですね。

そこで対偶を考えてみると以下の考えが浮かびました。

Nの2のk乗の位が1ではないならば、xの2のk乗の位が1ではない

2進数だと1か0しかないので、以下のように言い換えられそうだと考えました。

Nの2のk乗の位が0ならば、xの2のk乗の位が0

ここからNを2進数にした時に、0となる桁は必ず0で一致しておく必要があるが、1となる桁は1でも0でもどっちでも良い ということかと考えました。

Nを2進数にした時に1となっている桁が分かれば、その桁を0または1に変えたものがxとなり、小さい順に出力すれば良いだけではという結論に至りました。

C問題回答までの思考 ステップ2 bit全探索

「Nを2進数にした時に1となっている桁が分かれば、その桁を0または1に変えたものがxとなり、小さい順に出力すれば良いだけでは」というアイデアを実装に移す必要があります。

ここでbit全探索という実装方法が利用できると思いました。

『bit全探索』という名前が難しそうで、イメージがつきづらいのがとっつきづらい原因だと思っています。実際にやっていることは『使う・使わないを全探索』『選ぶ・選ばないを全探索』程度のことです。

今回の例では、以下のようにNを2進数とした時に1となっている桁について、0と1に変えることができるので有り得るすべての数字を列挙すればよいということになります。

bit全探索の実装方法としては、以下記事のようにオーソドックスな実装がまず考えられます。

ですがPythonは標準ライブラリの itertools.product 関数を利用して、簡単な記述でbit全探索を実装できます。

なお、bit全探索は2のa乗と非常に大きな計算量となります。

今回は最大でNが2の60乗ですが、制約により「1となる位は15個以下」とあります。

2の20乗くらいまでの計算ならPythonでも2秒の制限時間内に終了した経験があるので、実装できそうだと考えました。

ということで、私がコンテスト中に実装したコードは以下のとおりです。

S = input()
N = int(S)

# Nを2進数にして1となっている桁番号をlistに格納
B = format(N, "b")
keta_list = []
for i in range(len(B)):
    if B[i] == "1":
        keta_list.append(i)

# bit全探索で1となっていた桁から、全てのパターンを調べる
ans_list = []
for combi in product([True, False], repeat=len(keta_list)):
    tmp = list(B)
    for i, bo in enumerate(combi):
        n = keta_list[i]
        if bo is True:
            tmp[n] = "1"
        else:
            tmp[n] = "0"
    ans_list.append(int("".join(tmp), 2))

for ans in sorted(ans_list):
    print(ans)

無駄な記述もありますが、おおむね想定どおりの実装ができました。

なお、公式解説や他のみなさんはもっと短くてシンプルな解答をされているので、ぜひ一度他の方のコードも検索してみてください！

まとめ

• C問題は実装までのアイデア考えて、実装手段を考えるのが楽しい
  • これで問題解けた時の楽しさが忘れられない
• bit全探索は結構頻繁に出題されるので考え方を覚えておきたい
• 個人的に次が茶色になれるかどうかの瀬戸際なのでゆるく頑張ります