【AtCoder】泥臭くACをとるためには

こんにちは。nasuo_71です。

先日のAtCoder Beginner Contest416で、面白いことがあったので書き記します。
A問題、B問題を解くのに約30分費やしてしまった、はやくC問題を取って順位を上げないと...と焦っている時にでくわしたのがこの問題。

AtCoder Beginner Contest 416 C問題 Concat (X-th)

一度解いてから続きを読むことをお勧めします。

考察パート

私は問題文を読んで、どうやって解くのかさえ皆目見当がつきませんでした。

nPrの組み合わせを実装して解くのかなー?　→　実装で詰む
始めにsortすればいけるんじゃね!?　→ そんなわけない

...

私はUnratedで出ればよかったという後悔と共に、問題と40分間にらめっこをしました。

制約を凝視しました。問題を図式化しました。問題の本質を理解しようとする努力をたくさんしました。

そして...

ダメもとで全部書くか...

と思い実装したのが下のコード

sample.c

n,m,q=map(int,input().split())
l=[]
for i in range(n):
    l.append(input())
s=[]
if m==1:
    for i in range(n):
        s.append(l[i])
if m==2:
    for i in range(n):
        for k in range(n):
            s.append(l[i]+l[k])
if m==3:
    for i in range(n):
        for k in range(n):
            for j in range(n):
                s.append(l[i]+l[k]+l[j])
if m==4:
    for i in range(n):
        for k in range(n):
            for j in range(n):
                for g in range(n):
                    s.append(l[i]+l[k]+l[j]+l[g])
if m==5:
    for i in range(n):
        for k in range(n):
            for j in range(n):
                for g in range(n):
                    for d in range(n):
                        s.append(l[i]+l[k]+l[j]+l[g]+l[d])


s=sorted(s)
print(s[q-1])

はい、あまり綺麗ではないですね(失礼)。

何をしたかというと、制約が 1<=K<=5 だったことから、無理やり全通りを場合分けしました。

提出してみると...AC!

まとめ

模範解答は、DFSを使用するものでした。私の冗長なコードとは違い、とても簡潔にまとまっていました。

私が書いたコードは冗長で、お世辞にも美しいとは言えません。解説のコードの方が2^60倍綺麗です。しかし、問題の本質(組み合わせ方の全列挙)を捉えているという点から、このコードは解説コードと同等に優れているといえます。

教訓

アルゴリズムは、全列挙(全探索)が根底にある。
ということを思い知らされた、ABC416でした。
私はこの問題と、そして自分が書いたこのコードと少し、友達になれたような気がしました。