エンジニアとして、アルゴリズムの習得は避けて通れません。大量のデータを効率よく処理するためには、適切なアルゴリズムを使用する必要があります。
「今どきアルゴリズムわからんくても動くもの作れるし」とか言ってるそこのあなた！そして私も！今すぐ反省してください。
今回は、そんな自分を戒めるために、競技プログラミングにチャレンジしてみました。
競プロ入門
競技プログラミングとは？
競技プログラミングとは、読んで字のごとく、プログラミングの技術を競う競技です。
与えられた問題を、いかに素早く、効率よく解けるかを競います。たいていは力業では解けず、アルゴリズムを適切に使用する技術が問われます。
AtCoderでは、競技プログラミングのコンテストを毎週オンラインで行っています。2022/01/22に開催されたコンテストの問題を解いてみましょう。
問題にチャレンジ
AtCoder Regular Contest 133 A- Erase by Valueより引用
問題文
長さ N の整数列 A=(A 1,A 2,⋯,A N) が与えられます． すぬけくんは今から， A の中から一つ値を選びます． ここで選んだ値を x とします． そして，A の要素のうち，x でないものを元の順番を保ったまま並べ，整数列 a を作ります． a としてありうる数列のうち，辞書順最小のものを求めてください．
制約
1≤N≤200000 1≤A i≤N 入力される値はすべて整数である- 1≤N≤200000
- 1≤A i≤N
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N
A1 A2 ⋯ AN
出力
辞書順最小の a の要素を空白区切りで出力せよ．
ゴリ押し作戦
全パターンを試して、最小のものを出力します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
//Python 3.8.2 //入力を受け取る N = int(input()) A = list(map(int, input().split())) //結果を格納する result = [] //全件走査 for n in set(A): tmp = [x for x in A if x != n] result.append(tmp) //辞書順に並べる result = sorted(result) //整形して出力 print(" ".join(map(str, result[0]))) |
データが少ないうちはいいですが、入力の最大数が200000なので、計算量が莫大になってしまいます。
実行時間制限でアウト！
シンプル イズ ザ ベスト
ややこしいことは考えず、シンプルに行きます。
辞書順最小ということは、数列の前のほうから調べて、小さい値が前に移動するように取り除けばよさそうです。場合分けして考えてみましょう。
例1： 1 2 3 4
この場合は、最後の4を取り除くと[1 2 3]となり辞書順最小です。
例2： 1 2 2 4
この場合も、最後の4を取り除くと[1 2 2]となり辞書順最小です。
例3： 1 3 2 4
この場合は、3を取り除くと[1 2 4]となり辞書順最小です。4を取り除くと[1 3 2]となり、辞書順では、3の場合に負けます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//Python 3.8.2 //入力を受け取る N = int(input()) A = list(map(int, input().split())) //仮の選択数値 x = A[-1] //前から調べて、次の要素より大きいものを選択 for i in range(N - 1): if A[i] > A[i + 1]: //見つかったら終了 x = A[i] break //選択した数値を取り除く result = [a for a in A if a != x] //整形して出力 print(" ".join(map(str, result))) |
以上の方法でクリアできました。
ちょっとした工夫で、計算時間を大幅に短縮できました。
まとめ
世の問題を効率よく解決するために、さまざまなアルゴリズムが考え出されています。先人が編み出したアルゴリズムに学ばない手はありません。
闇雲に答えを探すのではなく、問題の本質を見極めて最適な処理を行えるかが腕の見せ所でしょう。
基本からしっかり身に着けて、良いプログラムが書けるよう精進します！みなさんもぜひ、競技プログラミングにチャレンジしてみてください。
Company運用会社
株式会社トランソニックソフトウェア
名古屋市でシステム開発・WEB制作を中心に事業を展開しています。システムに関すること、なんでもお気軽にご相談ください！
Search記事検索
Popular人気記事
