秋山です。
paizaでは先日、2018年卒業予定の学生でSランク・Aランク（※）の方に向けた「paizaでpizzaを食べながら！もぐもぐ就活勉強会」を開催いたしました。
今回は、そのイベントで出題したプログラミング問題と、解き方について解説したいと思います。
イベント当日の様子はこちら
paiza.hatenablog.com
※paiza新卒では、オンライン上でプログラミングスキルチェック問題を解いていただき、その成績をもとにS・A・B・C・D・Eと6段階のスキルランクを付与しています。企業ごとに求められる規定のスキルランクを満たしていれば、事前の書類選考なしで必ず面接に進むことができます。
スキルチェック問題はこちら
■1問目：本の整理 (Aランク相当)
paizaラーニングで問題を公開しています→「プログラミング練習問題：本の整理」
問題
パイザ図書館には N 冊の蔵書があります。この蔵書はすべて 1 段からなる本棚で管理されています。そして、それぞれの本には 1 から N までの相異なる整数の ID がついています。本棚の本は ID 順に並んでいます。
しかし、ある日、あなたが蔵書の点検をしていると、本棚の本がバラバラに並べられていることに気づきました。
そこで、あなたは、次のルールに従って本を並び替えることにしました。
次の手順を N 回繰り返す。
1. i (1 ≦ i ≦ N) 回目の手順では、まず本棚の左から i 番目の位置に立つ。
2. 左から i 番目の位置にある本から、本棚の右端にある本までのうち、最も ID が小さい本の位置を歩きながら見つける。この位置を j とする。
3. i = j なら、何もしない。 i ≠ j なら、i 番目の本と j 番目の本を入れ替える。
本を取り出して入れ替えるのには時間がかかります。そこで、このルールに従って本を整理するときに、何回本を入れ替える必要があるのかを計算してください。
この問題の最も単純な解き方は、手順 1. 2. 3. を素直にシミュレーションすることかと思います。
手順に沿った実装をした場合、挿入ソートを行うことになり、計算量は O(N^2) となります。蔵書の数が10万冊ということもあり得る条件となっているため、そのままだと最悪100億回もの処理を行うことになってしまいますね。この場合は計算量の改善が必要です。
2. の手順の「最も ID が小さい本の位置を歩きながら見つける」 という点に着目してみましょう。この問題で、IDが最も小さい本の位置は、必ず左の方へと移動させていくことになります。
ということは、各IDがどこにあるかを記録しておき、順番にその記録と参照して、本を並び替えていけばよいということになります。
この時、各IDの本の位置も随時並び替えて行くので記録も入れ替わっていきますが、本の位置交換と同時に記録も交換していけばよいので、毎回全ての記録を見直す必要はなく、処理の回数を大幅に減らせます。
ちょっとわかりにくいですかね……当日の詳しい解説スライドはこちらになりますので、参考にしてみてください。スライドの最後に書いたとおり、バケットソートのような手順で計算量を減らすことができます。
■2問目：文字列収集 (Sランク相当)
こちらは、あくまで当日に1問目を解けた人向けのおまけとして出題でしたので、解説を充分に用意できておらず失礼しました……。実際、当日は多くの優秀な方に挑戦していただけたので、解説をします。
問題
あなたは文字列の愛好家で、文字列を収集することにとても熱心です。
文字列は市場で高値で取引されています。
今、市場には N 個の文字列が出まわっており、文字列 Si (1 ≦ i ≦ N) の価格は Pi です。あなたは数ある文字列の中でも、とくに先頭がある特定の文字列で始まる文字列に興味があり、そのような文字列をすべて買い占めたいです。例え、同じ文字列が複数売っていたとしてもそのすべてを買います。
市場に出回っている N 個の文字列 Si とそれぞれの価格 Pi (i ≦ i ≦ N)
M 個のクエリ文字列 Qi (1 ≦ i ≦ M) が与えられます。それぞれのクエリ Qi に対し、市場に出回っている文字列の中で先頭が Q_i で始まる文字列すべてを買い占めるのに必要な金額を出力するプログラムを作成してください。
- a で始まる文字列を買い占めたい場合
aaaa, abc, abcd の3つで 131 + 20 + 9
- x で始まる文字列を買い占めたい場合
xyz の1つで 16
- abc で始まる文字列を買い占めたい場合
abc, abcd の2つで 20 + 9
まずは単純な手段を考えてみましょう。
文字列と価値の一覧を持つ、買い占めたい各クエリごとに、全ての文字列と前方一致を探そうとすると
N個の文字列 × 前方一致を行うためにSiの長さ × クエリ総数
という計算量になります。
高速化のためには、いくつかの方針を想定しています。
想定していた解き方は、「トライ木」というデータ構造を使い、N個の文字列を探す処理を高速化したものです。
トライ木はN個の文字列を全て含んだ木を作ることができ、その中にある文字列が存在するか検索する際に、検索文字列の長さにのみ依存して探せる木構造です。
上記コードでは、 maketrie というメソッドで作成しています。今回は、各木の枝にはそれまでの文字列の価値を sum として合計しながら記録していきます。
トライ木をつくる計算量は N個の文字列の数 × 各単語の文字数 となります。
intrie は、文字列を1文字ずつにわけてトライ木を探索していって最後の文字の枝を返す、もしくは sum が0ということを返すというメソッドになっています。クエリ文字列の長さ分の計算量がかかります。
この問題ですが、当日の参加者の解法の中には、想定してなかったものもありました。
N個の文字列から、存在し得る全ての検索文字列の価値計算を事前に全てしておく……という方法です。
この場合、価値を事前に計算するためにかかる時間は N個の文字列の数 × 各単語の文字数 となり、トライ木と同等になります。
事前に計算した後で値を取り出すため、取り出す際の計算量は O(1) となりますが、トライ木の場合は Si の長さ分 かかりますから、こちらの方が高速に取得できます。
では、どちらの解き方がよいのでしょうか？
この問題の条件とpaizaのスキルチェック的な採点においては、どちらも満点となります。
計算量については、事前に N個の文字列の数 × 各単語の長さ の処理をどちらも行っています。
価値の合計を出力する処理においては
- トライ木 : クエリ文字の長さ
- 事前に全ての文字列を作る方法 : O(1)
となり、トライ木の方が不利となります。
ということは、トライ木を使わない方がよいのでは？と思われるかもしれませんが……今回の問題設定とは異なりますが、例えば各 N個の文字列 の長さが 1000文字であった場合、事前に全ての文字列を作るとなると1000種類になります。この場合もトライ木であれば、1文字ずつ分割をして木として保持することができるので、データ量の面においてはかなり有利になると言えます。
この問題については、上記の手段の他にも、
N 個の文字列をソートする→ソートすることにより二分探索が使えるようになり、前方一致する単語の先頭と、後方の2箇所が分かれば範囲が確定。ここから範囲内のコストの合計を出しますが、区間のコストを高速に求めたい場合は、累積和をとっておけば前後の数字の引き算で求めることができます。
……というような解き方も想定していました。
いろいろな解き方について考えることは、それぞれ有利な点や状況による使い分けを検討するためのよい勉強になるかと思います。ただ今回、全てを事前に計算しておく解法が想定できていなかったため、テストケースの設定や解説が不十分になってしまったことを、当日参加された皆さんには申し訳なく思っています……。
参加された皆さんからは「今後もこういったイベントがあれば参加したい」という声をいただいておりますので、今後も就活の役に立つ勉強会や、面白くてためになる問題を考えていきたいと思います。
「もっといろいろなプログラミング問題を解いてみたい」という方は、paizaのスキルチェック問題にぜひ挑戦してみてください。
途中でブログパーツとして使ったオンライン実行環境サービス「paiza.IO (パイザ・アイオー)」はこちら
