1. はじめに
2. AtCoder で出た問題
3. 実務で出た問題
4. 競技プログラミングとシステム開発の共通点
はじめに
AtCoderという競技プログラミングをやって４ヶ月ほど経ちました。業務とは一切関係がなく、趣味や暇潰しの感覚で続けています。
競技プログラミングでは複雑なアルゴリズムを考案して構築しますが、私が普段業務で行っている Web システム開発では複雑なアルゴリズムを組む必要はありません。しかし、競技プログラミングで得たスキルがシステム開発でも使える場面があったので、今回はそれを共有しようと思います。
AtCoder で出た問題
その前にまず、AtCoderでは以下のような問題が出題されます。
問題の内容を簡単に書くと...↓↓↓
リングを両手で持ち、与えられた命令通りに手を動かして、最終的に最短で何回動かす必要があるか求めてください。命令では左右どちらかの手と、移動先の番号を指定されます。ただし、片方の手はもう片方の手を越すことができないという制約があります。
指定された手を指定された場所まで移動させるという１回の試行の中で、例えば以下の事で悩むと思います。
- 時計回りと反時計回りのどちらが最短だろうか
- その道中にもう片方の手はあるのだろうか
- N から 1 に移動するときの処理はどうしようか
一見するとたくさんの条件分岐があり、if 文を重ねないといけないように感じます。
しかしよく考えてみると、たとえ時計回りだろうが反時計回りだろうが、最短であろうがなかろうが、結局もう片方の手がないルートを通るしかないことに気づきます。
そう考えるとこの問題はシンプルになります。
まず初めにルートを決め、その道中にもう片方の手があれば反対側に回るようにします。このとき、N から 1 に移動しない方を選ぶとよりシンプルになります。
例えば、N = 6 で...
（移動前、移動後）=（2,4）の場合、「2 → 3 → 4」
（移動前、移動後）=（6,1）の場合、「6 → 5 → 4 → 3 → 2 → 1」
のルートを選択するようにします。
このとき必要なのは手の移動回数です。シンプルなルート決めをしたので、移動回数は移動前、移動後の差で求められ、反対側に行く場合はその差を N から引くことで求められます。
例えば、N = 6 で...
（移動前、移動後）=（2,4）の場合、（時計回り、反時計回り）=（2回, 4回）
（移動前、移動後）=（6,1）の場合、（時計回り、反時計回り）=（1回, 5回）
のように移動回数を求められます。
ここまでをコードに起こしてみます。
１回の施行の中で...
- 移動する手と移動後の場所が与えられる
- ルートを決め、その時の移動回数（dist）を求める
- 決めたルートの中に逆の手があるか判定する
3.5. ある場合、 N から dist を引いた値を移動回数として dist に再代入する - 移動後の手の位置を現在地として記録し、dist を加算する
のようなアルゴリズムを組みました。それが以下のコードになります。
N, Q = map(int, input().strip().split())
HT = [list(input().strip().split()) for _ in range(Q)]
# 手の現在地をここに記録する
# 初期値は左手が 1、右手が 2 にいる
hands = {
"L": 1,
"R": 2
}
other_hand = {
"L": "R",
"R": "L",
}
# 移動回数の合計をここに保存し、答えとして出力する
total_dist = 0
for ht in HT:
# h は "L"または"R"
# t は移動先の数字
h, t = ht[0], int(ht[1])
# hands[h] はその手の現在地（移動前の数字）を示す
# hands[h] と t のうち、小さい方を from_ 、大きい方を to_ に代入し、ルート決めに利用する
from_ = min(hands[h], t)
to_ = max(hands[h], t)
# ルートはリスト型で表現する
route = list(range(from_, to_))
# 上で決めたルートでの移動回数を求める
dist = to_ - from_
# 上で決めたルートの中に、反対の手があるか判定する
if hands[other_hand[h]] in route:
# ある場合、反対周りのルートで移動するので、移動回数を再計算する
dist = N - dist
# 移動先(t)を現在地として更新する
hands[h] = t
# 移動回数の合計を更新する
total_dist += dist
print(total_dist)
実務で出た問題
さて、だいぶぼかしますが、実務で以下のような状況にあったことがあります。
$ [a_1, a_2, ...] $ と $ [b_1, b_2, ...] $ の２つのリストがあります。($a_i$の型をA、$b_i$の型をBとする)
これらは元々１つのリスト$T$の中に混在していましたが、手元には２つに分離した状態で与えられます。そして元のリスト$T$の中での順番は型 A のみ持っています。
この状態で、元のリスト$T$の中で $ b_1, b_2, ... $ の順序を求めてください。
最初は元のリスト$T$の中で、型 B の要素にも順番を格納しようとしましたが、どうやら型 B は読み取り専用で編集ができないそうです。
そこで発想を変えました。
型 A が持っている順番の情報と要素の合計が分かれば、型 B の順番を求められることに気づきました。
すなわち...↓↓↓
A_list = ["a1", "a2","a3",]
A_order = [1, 3, 5]
B_list = ["b1", "b2",]
このような条件が与えられるので、
- 元のリストの要素数 N を求める
- 1 から N までの中で、A_order にない数字を B_order に格納する
このようにすることで型 B の順番を求められます。
コードに起こすと...↓↓↓
num_elem = len(A_list) + len(B_list)
B_order = []
for i in range(1, num_elem):
if i not in A_order:
B_order.append(i)
または...↓↓↓
num_elem = len(A_list) + len(B_list)
B_order = [i for i in range(1, num_elem) if i not in A_order]
とすることで、正しく型 B の順番を求められます。
上記の例の場合、B_order = [2, 4] となります。
競技プログラミングとシステム開発の共通点
競技プログラミングを始めると得られるスキルは様々ありますが、Web システム開発でも活用できるスキルは、制約のある中で最適なアルゴリズムを構築する能力だと今回自覚しました。
「片方の手はもう片方の手を越すことができない」「読み取り専用の型は情報を付与できない」といった条件がある中で、いかに論理的でありバグが起きず、色々なインプットでも正しい答えを出すコードを書けるかはどちらにも当てはまります。競技プログラミングの経験から培われた柔軟な発想で、今後も様々な場面で最適なアルゴリズムを構築していこうと思います。