競技プログラミングで大切なことを再発見した話
仕事ではもっぱらGoを使っているのだが、最近は新しくelixirを勉強している。
関数型言語であり、コードをシンプルに保つことが出来て可読性が良い。信頼性のあるErlang VMの上で動作するので堅牢でもあり、モダンな言語らしく並列実行やプロセス間通信が簡単に実現できる。
そして何より名前がカッコイイ。Elixir、不死の霊薬である。そしてWebフレームワークの名前はPhoenix、Elixirを使うエンジニアはAlchemistと呼ばれる。厨二心がくすぐられる。
Elixirを学ぶ際には、公式のGetting Startedが非常によくまとまっている。ここで基本的な文法についてはあらかた学んだので、次のステップとしてAtCoderにチャレンジすることにした。
AtCoderは日本発の競技プログラミングコンテストサイトで、様々なレベルのオンラインコンテストが毎週開催されている。さらに、過去のコンテストの問題は全て公開されており、その全ての問題にチャレンジすることが出来る。
その中でもAtCoder Beginners Selectionは、競技プログラミング初心者に向けた良問が取り揃えられている。学んだばかりの言語を書き慣らすにはうってつけだと思い、このコンテストの問題を解いていくことにした。
競技プログラミングの問題を解くのは学生時代以来数年ぶりだった。当時はAtCoderは存在せず、TopCoderというアメリカのサイトが競技プログラミングのメッカだった。全世界から参加者が集まる関係上、開催時間が日本時間の深夜であることも多く、夜中に起きてられない自分は中々参加することは出来なかった。その頃に比べると、日本の競技プログラミングの環境は飛躍的に良くなったと感じる。
本気で取り組んでいたわけではなく、ダラダラと1年ぐらい続けて動的計画法すらマスターできずにやめてしまったのだが、社会人になる前に、競技プログラミングを通してコーディングの基礎をしっかり固めることが出来た。会社に入ってから、Subversion/gitの使い方とか、テストコードの書き方とか、リーダブルなコードを書くことの重要性とか、学ぶことはたくさんあったのだけれど。
AtCoder Beginners Selectionには以下のような問題がある。
シカのAtCoDeerくんは二つの正整数 a,b を見つけました。 a と b の積が偶数か奇数か判定してください。
なんのことはない、aとbを掛けて2で割った余りを判定するロジックを書けばいい。肩慣らしには丁度いい問題だ。
以下のような問題もある。
N 枚のカードがあります. i 枚目のカードには, aiという数が書かれています. Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります. 2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.
文字だけだと少し分かりづらいが、要は床にばらまかれているカードを順番に取っていって、その合計数が多いほうが勝ちというゲーム。Aliceが先に取るため必ずAliceの方が勝つ出来レースになっているのだが、「Alice は Bob より何点多く取るか」はどう求めたらいいのだろうか。
「自分の得点を最大化する最適な戦略」とは何だろうか。床にあるカードはどれでも好きに取って良いのだから、当然数字が一番大きなカードを選ぶ。次の手番では、その次に大きなカードを選ぶ。つまり、AliceとBobはカードの数字を降順にソートしたものを交互に取っていくはずである。つまり、
- カードの数字を降順にソートする
- 1枚目はAlice、2枚目はBob、3枚目はAlice...のように交互に振り分ける
- それぞれの持っているカードの数字の合計を計算する
- Aliceの合計から、Bobの合計を引く
とすると、求める答えに辿り着くことが出来る。
最初は上記のような方針でロジックを書いていこうとしていたのだけど、途中で行き詰まってしまった。愚直にコードを書くことは出来るのだけど、どうもelixirっぽくなる気がしない。
elixirでは|>という演算子を使って、データの処理の流れを一直線に書いていくことが出来る。しかしAliceとBobにカードを振り分ける部分でどうしてもその流れが途切れてしまう。悩んだ結果、以下のようにロジックを修正した。
- カードの数字を降順にソートする
- 先頭から順番に2枚ずつにグルーピングする
- それぞれのグループで、1枚目と2枚目の差を計算する
- その差を合計する
このようにするとelixirっぽく書くことが出来た。AliceとBobの最終的な合計の差を計算しているわけではないが、1ターンずつ積み上がっていく差を合計する事によって、知りたい答えと同じものを求めることが出来る。
以下のような問題もある。
英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。 - T の末尾に dream dreamer erase eraser のいずれかを追加する。
単純なようだが意外と難しい。文字列Sの先頭がdreamerとなっていても、それが本当にdreamerなのか、dreamにerase、またはeraserがくっついた形なのか、判断がつかないからだ。Sは1万文字に達することもあり、試行錯誤しながら文字列を組み立てていくロジックを組むと、あっという間に実行時間が超過する。
必要なのは発想の転換だ。文字列を先頭から見るのではなく末尾から見ていくと、それがdreamerなのかeraserなのか一意に定まることがわかる。この方針で行けば良さそうだ。
さらに、文字列を組み立てていくのは時間がかかる。文字列を組み立てていく代わりに、文字列の末尾からdream,dreamer,erase,eraserに当てはまるものを消していき、最終的に文字が全て無くなれば、Sは組み立て可能だと判断することが出来る。最終的なロジックは次の通り。
- 文字列Sを逆にする
- 文字列の先頭から
maerd,remaerd,esare,resareに当てはまるものを順番に消していく - 空文字列になるかどうかを判定する
問題では「与えられた文字列のリストから特定の文字列を組み合わせることが出来るか」なのに対し、やっていることは文字列の消去、さらに見ているのは与えられた文字列の逆である。しかし、これでも知りたい答えは手に入る。解く問題が変わったとしても、知りたい答えさえ手に入ればいい。
問題を解いている間、すごく懐かしい気分になった。競技プログラミングをやりはじめの頃、難しそうに見える問題でも愚直にロジックを書いた。大抵そのコードはバグにまみれているか、実行時間制限を軽く超過してしまう。徒労感に覆われたままコンテストが終了し、他の出場者のコードを見ると、そのエレガントなコードに驚かされた。コードの見た目やコードサイズの話ではなく、「与えられた問題Aを解くことになる別の簡単な問題B」を見つけていることに驚かされていた。
数学の対偶証明と同じように、ある命題Aを証明することが難しくても、その対偶Bを証明することができれば、Aを証明したことと同じことになる。同じことが競技プログラミングの世界でもあって、与えられた問題Aが難しければ、その問題が解けたことになる別の問題Bを見つければいいのだ。
ここまで考えて、そういえば仕事でも同じような思考をしていることに気がついた。あまり具体例は書けないんだけど、自分は社内システムを担当していて、ユーザからよく「○○の機能を追加してくれ」と言われる。ユーザが考えるものなので仕方がないのだけど、その機能は工数が物凄くかかったり、そもそも実現不可能だったり、実現できたとしても明らかにユーザが使いこなせなかったりする。そのまま実装するのは、地獄へと続く一本道だ。
そうした時には「そうおっしゃるという事は▲▲に困っているということですよね？ であれば、□□とすれば解決できそうなのですが、どうですかね？」と切り返すことが多い。□□の部分には、別の機能の提案だったり、既に実装している機能の活用法だったり、自分の担当外の別のシステムを紹介したり、色々なものが入る。
「機能を追加してくれ！」と言われて、追加する/追加しないの二択で考えるのでは泥沼にハマる恐れがある。「機能を追加してほしい」という要望はある問題を解くため、にユーザ側が何とかして編み出した解決法である。エンジニア側はその解決法をそのまま実装しようとするのではなく、同じ問題を解決したことになる別の簡単な解決法はどこにあるのか、模索する必要があると考えている。簡単に解決できれば、ユーザにとっては早く業務が改善できることになり、エンジニア側にとっては楽してお賃金を稼げることになる。
この考え方のルーツを意識したことはなかったのだが、競技プログラミングの問題を解いていくうちに、ここが自分の仕事の仕方の原点だったんだなと思い出してきた。競技プログラミングは仕事では役に立たないという意見は未だに根強い。確かに、上級コンテストに出てくるような高度なロジックを必要とする業務は一般的な企業には存在しない。それでも少なくとも、競技プログラミングを通して得られる考え方は、実際の業務においても有用なのではないだろうか。競技プログラミングを通して再発見した考え方を、これからも大事にしたいと思う。
