ABC215 C問題ふりかえり～AtCoder Beginner Contest 参戦録 #6

はじめに

ある有名Web系会社のエンジニア採用担当者の方が競技プログラミングに挑戦し、採用候補のエンジニアはもちろん、社内のエンジニアとのコミュニケーションに活用している事例を読み、刺激を受けて始めた競技プログラミング。

採用の仕事からは離れたものの参加を継続している(使用言語はPython)。安定してA, B問題をクリアし、Cにチャレンジする時間を確保することを当面の目標としている。今回はAB完、CはTime Limit Exceededという結果に終わった。

ちなみにこの回の直前にAtCoder社の高橋社長がこんなTweetをされていた。

難化なんかしていないという反論も含めて様々な反応があったが、C問題が易しくなるといいなーという淡い期待を抱いて参加した。

ABC215 復習

問題

自分の誤答

# -*- coding: utf-8 -*-
import itertools

S,K = map(str, input().split(" "))
K = int(K)
N = len(S)
orderlist = []

letters = list(S)
letters.sort()

for i in itertools.permutations(letters, N):
    s = ''.join(i)
    if (s in orderlist) == False:
        orderlist.append(s)

print (orderlist[K-1])

学び・気づき

参加中に調べたこと

• 順列 ¹

敗因

• 唯一思いついたやり方が計算量の大きいものだった（このパターンに陥ることが多い）。
  • O(N)をO(1)に減らす必要があった

友人コードからの学び

• (公式回答にPythonが無かったため、メンター役を買って出てくれている友人が個別に解説してくれた。感謝）
• set型 ²を使う
  • 重複した要素を持てないことを利用でき、判定が不要となる

まとめ

ABC215の復習を実施。計算量の考え方がやっと少しわかってきた。

1. Pythonで階乗、順列・組み合わせを計算、生成 | note.nkmk.me ↩

2. Python, set型で集合演算（和集合、積集合や部分集合の判定など） | note.nkmk.me ↩