医療とテクノロジーの交差点にて【第４話】競技プログラミングのススメ

どうも、トア・ルドクターです！
今回の内容は「競技プログラミング」になります。

競技プログラミングとは？
制限時間の中で数学的な問題をプログラミングを用いて解いていき、解答時間と獲得点数により順位を競う競技（コンテスト）です。複数回のコンテストの成績をもとに各人のレートが定まりランク（色）付けされます。一般に最上位ランカーは赤色なので「レッドコーダー」と呼ばれ、エンジニア界隈では一目置かれる存在と言えます。

海外ではTopCoder, Codeforces, GCJ(Google Code Jam)等のコンテストが有名です。中には機械学習に特化したkaggleや、セキュリティ系に特化したDEFCONといったコンテスト（所謂ハッキングコンテスト的な）もあります。日本でも幾つか有名なコンテストがあり、その１つがAtCoderというコンテストサイトです。とりあえず登録してみてください。「馬には乗ってみよ」「案ずるより産むが易し」的な精神で。

今回はAtCoderのABC139というコンテストの問題を扱います。AtCoderには大きく３つのコンテストがあり「上級者向けのAGC/ARC」「初心者〜中級者向けのABC」に分かれております。

では実際に問題を見ていきましょう。本記事のコードはすべてpython3を用いております。

【問題】 ABC139 (2019年9月1日) F問題

要するにこういうことです。

【咀嚼した問題文】
N個のベクトル（X[i], Y[i]）が与えられている。
これらの任意の組み合わせで得られる合成ベクトル（ベクトル和）のうち、大きさが最大のものに関して大きさを求めよ。

中級者向けコンテストのABCの中では最難関のF問題なので、正直、私はかなり苦戦しました。試行錯誤の果てに、漸く正解（AC ; Accepted Code）に辿り着けたのですが、その分、自分にとっても学びの多い問題でした。武術における「心技体」に照らして自分の学びを言語化しつつ、問題の解説をしていきます。いわば、プログラミングの心技体についてです。

（１）プログラミングにおける体（知識）

本問を通してpythonの科学計算用ライブラリであるnumpyの使い方に習熟できました。numpyの知識はマストではありませんが、ベクトルを扱う上でnumpyの有用性を実感できました。

import numpy as np

# a,bはただの配列
a = [1, 2]
b = [3, 4]

# c,dはベクトル
c = np.array(a)
d = np.array(b)

print(a+b) # 配列の連結
print(c+d) # ベクトルの足し算
---------------------------------
>>
[1,2,3,4]
[4,6]

import numpy as np

# a,bはベクトル
a = np.array([1,2])
b = np.array([3,4])

# np.dotでベクトルの内積・行列の掛け算
print(a*b, a*a, b*b)                            # 各要素の掛け算
print(np.dot(a,b), np.dot(a,a), np.dot(b,b))    # ベクトルの内積

# np.linalg.normでノルムを計算
print(np.linalg.norm(b, ord=1))    # L1ノルム：マンハッタン距離
print(np.linalg.norm(b, ord=2))    # L2ノルム：ユークリッド距離
-----------------------------------------------------------
>>
[3,8] [1,4] [9,16]
11 5 25
7.0
5.0

（２）プログラミングにおける技（構想力）

本問は、解法さえ思いつけば半分解けたも同然の問題でした。とはいえ、アイディアが閃いてから漏れなく実装するまで大変だったのですがね・・・。以下に、私の思考過程を示します。

「合成ベクトルの長さが最大になる組み合わせ」は少なくとも１つ存在する（題意を満たす合成ベクトルは１つとは限らない）から、そのうち１つの合成ベクトルについて考える。その合成ベクトルは、その方向からみて±90度の半平面内のベクトルを”過不足なく”全て足し合わせたものである。
↓
直観的にこれでよさそうだけど、一応厳密な証明を求める。もし半平面エリアに使ってないベクトルがあれば、そいつを使うことでより大きな合成ベクトルを作れる。逆に、もしエリア外のベクトルを使っていれば、そいつを除外することでより大きな合成ベクトルを作れる。故に、半平面内のベクトルを”過不足なく”全て足し合わせた合成ベクトルを片っ端から調べれば、そのどれかが正解の合成ベクトルである。
↓
調べる半平面エリアの選定は、個々のベクトルの法線ベクトル（NV ; Normal Vector）の±90度エリアを考える（個々のベクトルの延長線で隔てられる半平面）。元のベクトル＝接線ベクトル（TV ; Tangent Vector）に対して、法線ベクトルは２つ存在し、それぞれの法線ベクトルに対して±90度エリアを考えることで、両側の半平面を考慮できていることに注意する。
↓
これで全ての半平面の合成ベクトルを網羅できるから、全ての合成ベクトルの大きさをみて、その中で最大のものを選べば正解のはず・・・。

（３）プログラミングにおける心（忍耐力）

結局は、知識があろうとアイディア閃めこうと「最後までやり抜く忍耐力」「幾度も試行錯誤する粘り強さ」なしには正解に辿り着くことはできません。そもそも、閃き・アイディアというのは試行錯誤の中で生まれるものなので、粘り強さなしには技術向上は成し得ません。以下は、私が実際に悪戦苦闘した過程そのものです。

先ほどの解法には実はトラップがある。法線ベクトルの「-90度方向のベクトル群」と「+90度方向のベクトル群」は干渉してしまうので共演NGの関係にある。つまり、どちらかのベクトル群を除外すれば、合成ベクトルはもっと大きくすることができる。ただ、どっちを除外すればいいのか。
↓
冷静に考えれば、どっちを除外すべきか分からなくとも「-90度群を除外した場合」「+90度群を除外した場合」の各々で合成ベクトルを作ってみて大きい方を採用すれば良いだけ。これで今度こそ正解と思いきや・・・。
↓
実は更にトラップがある。「-90度群を除外した場合」「+90度群を除外した場合」の各々を考える必要があるのは、双方が共演している場合だけである。即ち、一方の群しか存在しないケースにおいては、そのベクトル群を消すことで寧ろ合成ベクトルは小さくなってしまう。このトラップにさえ気づけば解決法は至極簡単。「-90度群を除外した場合」「+90度群を除外した場合」「どちらも除外しない場合」の３パターンで合成ベクトルを作ってみて最大のものを採用すればいい。これで漸く正答に辿り着く。

試行錯誤の末に正答に辿り着けた場合、その達成感は格別なものですし、自己成長の喜びもあります。加えて、競技プログラミングの場合はライバルと切磋琢磨できる楽しさもあり、ここに競技プログラミングのトキメキがあります。一人でも多くの人が競技プログラミングについて知り、AtCoderなどチャレンジしてくれたら幸甚の至りです。最後にACコードを載せときます。

【解答】 

import numpy as np

n = int(input())
x,y = np.array([list(map(int,input().split())) for _ in range(n)]).T

# 内積が0以上かどうか
def isin90deg(v1, v2):
   if np.dot(v1, v2) >= 0 : return 1
   else: return 0

# 内積が0かどうか
def is90deg(v1, v2):
   if np.dot(v1, v2) == 0 : return 1
   else: return 0

ans = []
for i in range(n):
   # tangent-vector, normal-vector
   tv, nv1 = np.array([x[i],y[i]]), np.array([y[i],-x[i]])
   nv2 = - nv1
   # tvを境界とする半平面におけるベクトル和を考える
   # ただし、tvに平行なベクトル群（posi/nega）だけ例外処理
   for nv in [nv1, nv2]:
       sum,posi,nega = np.array([0,0]), np.array([0,0]), np.array([0,0])
       for j in range(n):
           v = np.array([x[j],y[j]])
           if isin90deg(v,nv): sum += v
           if is90deg(v,nv) and isin90deg(v,tv): posi += v
           if is90deg(v,nv) and not isin90deg(v,tv): nega += v
       # ユークリッド距離
       ans.append(np.linalg.norm(sum, ord=2))
       ans.append(np.linalg.norm(sum - posi, ord=2))
       ans.append(np.linalg.norm(sum - nega, ord=2))

print(max(ans))

それではまたいつか！

上級者の方々は、改善点やアドバイスなど御指摘もらえると幸いです。

【著者プロフィール】
都内で医師として研鑽する傍ら、独学でプログラミングを学ぶ26歳。趣味は『ギター / バイオリン / 美術鑑賞 / youtube鑑賞 / 創作料理 / 囲碁 / チェス / 折り紙 / スノボ / サーフィン / ドライブ』など枚挙にいとまがない。CIAの格闘武術クラブマガを始める。得意料理はバナナシチュー。ビールと牡蠣は生派だが生セックスは断固せず、経験人数の常用対数は２未満と清純を極める。略歴としては高２で数学全国１位（駿台）、文系で官僚をめざすも、ドラマ『コードブルー』の影響から気づいたら医師に。ディープラーニングG検定、統計検定２級、知的財産検定３級など取得。TOEICは次回900目指す予定（仮）。

【記事アーカイブ】
【第１話】医者なのにプログラミングを勉強してみた話
【第２話】pythonプログラミングの小技（１）ラムダ
【第３話】プログラミング初心者が学ぶべき３つのポイント
【第４話】競技プログラミングのススメ
【第５話】競技プログラミング物語（１）バイトリーダーの苦悩
【第６話】プログラミングで自作する実用アプリ（１）NEVER-NOTE
【第７話】プログラミングで解析したDNA鑑定の精度
【第８話】統計学は最強の学問であるのか？
【第９話】プログラミングすれば人類最高IQに対抗できる説