2014年4月16日より2014年5月14日まで開催していたpaizaオンラインハッカソン(略してPOH![ポー!])Vol.2「女子大生とペアプロするだけの簡単なお仕事です!」で提出された最速コードはどのような高速化のアプローチでで生み出されたのでしょうか? POH Vol.2に登場した女子大生インターンプログラマの木野ちゃん(左のイラスト)にアルゴリズムを図解で教えるとしたら、どう教えるだろうか、という事で、今回は図解してみました。
今回は前回の最速コード発表レポート(【結果発表】女子大生プログラマの心を鷲掴みにした最強のコード8選)に引き続き、最速コードの裏側に迫ります。
■高速化のアプローチ方法について
今回もPOH Vol.1 と同様に、POH Vol.2では計算量の改善による高速化を柱とするアプローチを想定して出題されました。基本は定数倍高速化によって想定解法よりも悪い計算量のプログラムを通すことは難しいように設定していましたが、度重なるチューニングで見事すべて通されたスーパープログラマの方々も多いのではないでしょうか。
定数倍高速化はテストケースの特性に合わせた様々なテクニックがあり面白いのですが、今回の解説では基本の柱となる計算量の改善についての解説を行いたいと思います。
流れとしては、まずいちばん簡単な解法であるO(H^3 W^3 ) 解法について説明したあと、O(H^2 W^2 ) 解法、O(min(H, W) HW) 解法について説明します。今回のテストケースをすべて通すにはここまでで十分ですが、O(HW) 解法も存在するので、興味のある方はぜひ考えてみてください。
※O(HW)というような書き方は、その解法のオーダー(計算量)を表す書き方です。よくわからない、という方はランダウの記号について読んでみてください。
■問題文の再確認
まずは問題文の確認をしてみましょう。
インターンを締めくくる開発発表として、あなたの会社の得意先であるcodomo社から受注したスマートフォン向けの新OS Paizen(パイゼン)を開発中の木野さんは、今、ホーム画面へのウィジェット配置機能の実装を考えています。 現在のホーム画面に対し、指定されたウィジェットが配置可能な場所をすべて求める機能を実装することにしました。
ホーム画面は大きさ縦H、横W の長方形で、1 x 1の正方形サイズでH x W個の区画に区切られています。ホーム画面左上の区画を(1, 1)、右下の区画を(W, H) で表します。 ウィジェットは縦S、横T の長方形で、同様に1 x 1 の正方形のサイズ(ホーム画面と1区画と同サイズ)で区切られています。ウィジェット左上のエリアを(1, 1)、右下のエリアを(T, S) で表します。
ウィジェットの配置とは、ホーム画面に対して、他の既に配置されているウィジェットに重ならないように、かつ、画面からはみ出ないようにウィジェットを置くことを言います。 このとき、ウィジェットを回転させたり、斜めにしたりして配置することはできません。また、ホーム画面の区画に対して、 ウィジェットがずれないようにぴったりとはまる形で配置する必要があります。(半区画ずらすような事は不可)
さてウィジェットの配置機能実装の第一歩として、現在のホーム画面に対し、指定されたウィジェットが配置可能な場所をすべて求める機能を実装することにしました。そこでホーム画面の現在のウィジェット配置状態と複数のウィジェットが与えられるので、それぞれのウィジェットに対し 配置可能座標 (定義は問題文中段)の数をすべて求めてください。
詳しくはPOH Vol.2のサイトの問題文をご確認ください。
※POH Vol.2は応募期間は過ぎたため、プレゼント対象、計測対象には成りませんが、コードの実行は引き続き可能です。
ホーム画面のサイズよりも大きいウィジェットが与えられることがあるという点に注意してください。このケースを正しく処理できていないと、テストケース3 を通すことができません。
■O(H^3 W^3 ) の解法
この解法は、実際にすべての座標に対してウィジェットが置けるかどうかをひとつずつ調べていきます。一番シンプルなアルゴリズムで実装も容易ですが、その分小さいサイズのテストケースしか通すことができません。実際にこの解法ではテストケース3 までしか時間内に正答できません。
◆O(H^3 W^3 ) 解法の手順
- それぞれのウィジェットに対して以下を実行する。
- ウィジェットの縦幅、または横幅がホーム画面の大きさを超えていたら0 を出力する。
- ans = 0 とする。
- ウィジェットが画面に収まるホーム画面上のすべての座標に対してループ
- a. いま注目しているホーム画面上の座標をウィジェットの左上と仮定する。
- b. ウィジェットが置かれる範囲内のすべての座標についてループ
- c. b. ですべての区画が0 であればans に1 を加える。
- ans を出力する。
この解法の計算量は、ひとつのウィジェットに対して答えを求めるのにO(H^2 W^2) かかり、与えられるウィジェットの数がO(N) = O(HW) であることから、全体でO(H^3 W^3) になります。
◆手順詳細
下記の図のようにウィジェットサイズ2×1のサイズのウィジェットについて、どこに配置できるかを探索する場合次のような手順に成ります。
まずホーム画面の左上から右に一つづつ順番に空き区画を探していきます。右端まで探索したら、一行下の行をまだ左端から右端まで探索、というかたちで最終行まで探索を行ないます。(下記図の0は空き区画、1は既に埋まっている区画を表します。)
空いている区画に出くわしたら、その区画を起点に、ウィジェットの大きさ分の区画が空いているか調べます。
図0-1ではホーム画面の左上(1,1)が空き区画(0)のため、(1,1)を起点として、ウィジェットサイズ(2x1)の領域が空きかを調べます。このウィジェットだと対象区画の右側を調べる事に成ります。図0-1だと右隣の(2,1)は空いていないので、この区画にはウィジェットが配置できない事が分かります。
図0-2は(4,1)を起点に右隣の区画を調べていますがこちらも埋まっているため、ウィジェットが配置できません。
しかし図0-3の(2,2)を起点として右隣の(3,2)の区画を見てみると、こちらも空き区画のため(2,2)を起点としたウィジェットの配置は可能な事が分かります。
しかし図0-4の(4,2)を起点とするとウィジェット配置は出来ない事が分かります。
このように、空き区画を見つけるたびにウィジェットサイズ分の領域の検索を探索する、という事をウィジェットの個数分行なう、というのがO(H^3 W^3 ) の解法になります。
◆O(H^3 W^3) のコード(C言語)
C言語以外の言語(Java,PHP,Perl,Python,Ruby,C++,C#)のコードはpaiza会員ページにて公開しています。
⇒他言語のコードを見る(会員登録が必要)
#include <stdio.h> int main(void) { int h, w, n; int i, j, k; char display[310][310]; scanf("%d%d", &h, &w); for(i=0; i<h; ++i){ scanf("%s", display[i]); } scanf("%d", &n); for(k=0; k<n; ++k){ int s, t, cnt = 0; int y, x; scanf("%d%d", &s, &t); for(y=0; y<=h-s; ++y){ for(x=0; x<=w-t; ++x){ int ok = 1; for(i=0; i<s; ++i){ for(j=0; j<t; ++j){ if(display[y+i][x+j] == '1'){ ok = 0; goto next; } } } next: cnt += ok; } } printf("%d\n", cnt); } return 0; }
■O(H^2 W^2 ) の解法
この計算量の解法のひとつとして2次元累積和を用いる方法があります。2次元累積和とは、2次元配列a において、a[0][0] からa[x][y] までの長方領域に含まれる要素の合計値をすべてのx, y について事前に計算しておくことで、a[x1][y1] からa[x2][y2] までの長方領域に含まれる要素の合計値をO(1) で求めることができるアルゴリズムです。
この方法を用いれば、O(H^3 W^3 ) 解法のb. のループの部分の計算量をO(HW) からO(1) に高速化することができ、その結果全体の計算量もO(H^3 W^3) からO(H^2 W^2 ) へと改善されます。2次元累積和の計算はO(HW) でできるので全体の計算量に影響は与えません。
◆O(H^2 W^2 ) 解法の手順
- ホーム画面上において、ウィジェットがある区画を1、無い区画を0 として、2次元累積和を事前に計算する。
- それぞれのウィジェットに対して以下を実行する。
- ウィジェットの縦幅、または横幅がホーム画面の大きさを超えていたら0 を出力する。
- ans = 0 とする。
- ウィジェットが画面に収まるホーム画面上のすべての座標に対してループ
- a. いま注目しているホーム画面上の座標をウィジェットの左上と仮定する。
- b. 2次元累積和の表を用いてウィジェットの範囲内の値を調べ、0 であればans に1 を加える。
- ans を出力する。
◆手順詳細
ホーム画面上において、ウィジェットがある区画を1、無い区画を0 として、2次元累積和を事前に計算を図示すると下記のようになります。
まず図1のオリジナルの状態を行ごとに横に累積和を求めていったものが図2。図2の行ごとの累積和を、更に列ごとに縦に累積和を求めていったものが図3です。これが二次元類積和の表になります。
図3の2次元累積和の表を元にすると、ホーム画面の左上を起点とした(1,1)から任意の(x,y)の範囲が空いているかどうかが分かるようになります。上記図3でいうと(1,1)から(3,4)の赤色の四角いエリアの二次元類積和は4(このエリアは4区画が埋まっている)という事が分かります。
次に下記のような任意の領域を、図3の二次元類積和の表よりどのよう算出すれば良いでしょうか?
この場合まずホーム画面左上(1,1)を起点として、緑色のエリアの右下(4,4)迄の範囲の二次元類積和を求めます(図3-1)。この範囲の累積和は7です。
今回は緑の範囲のみを求めたいので、下記の灰色のエリアが不要になります。
そこで二次元類積和の図を使って、灰色の範囲をの累積和を引き算してやります。
やり方としては(1,1)から(4,2)のエリアの二次元類積和(=4)と、(1,1)から(1,4)の二次元類積和(=1)を図3-1の7からマイナスします。ただそれだけだと、(1,1)から(1,2)の範囲の二次元類積和をダブってマイナスする事に成ってしまいますので、その分をプラスします。
以上のように二次元類積和の図の4点から特定の領域の二次元類積和を算出る事が出来るようになるため計算量を減らす事が可能になります。
◆O(H^2 W^2 ) のコード(C言語)
C言語以外の言語(Java,PHP,Perl,Python,Ruby,C++,C#)のコードはpaiza会員ページにて公開しています。
⇒他言語のコードを見る(会員登録が必要)
#include <stdio.h> int main(void) { int h, w, n; int i, j, k; int sum[310][310]; scanf("%d%d", &h, &w); for(i=0; i<h; ++i){ char line[310]; scanf("%s", line); for(j=0; j<w; ++j){ sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + (line[j] == '1'); } } scanf("%d", &n); for(k=0; k<n; ++k){ int s, t, cnt = 0; scanf("%d%d", &s, &t); for(i=s; i<=h; ++i){ for(j=t; j<=w; ++j){ int num = sum[i][j] - sum[i-s][j] - sum[i][j-t] + sum[i-s][j-t]; cnt += num == 0; } } printf("%d\n", cnt); } return 0; }
■O(min(H, W) HW) 解法の解説
この計算量の解法にも様々なものが存在しますが、paiza で用意した解答は動的計画法を用いるものです。実装は多少複雑ですが元のアイデアはシンプルなものになっています。この解法は以下のアイデアに基づきます。
※詳細に解説するととても長くなるので、ここでは基本的な考え方だけの紹介にとどめます。、、すみませんこの解法は図解無理でしたw 要望が沢山有るようであれば次回のブログで解説します。
◆O(min(H, W) HW) 解法のアイデア
- ウィジェットは全部でHW 種類なので、全種類の答えを事前に計算することで、それぞれのウィジェットに対してO(1) で解を出力したい。
- すべての大きさについて別々に解を求めるのは大変なので、小さいサイズのウィジェットの解から順に求めて徐々に大きいサイズのウィジェットの解を求めたい。
- 1x1, 1x2, ..., 1xW のサイズのウィジェットの解は簡単に求まる。
- ホーム画面上の空いた区画の数を数えれば良い。
- 1x1, 1x2, ..., の解を用いて、2x1, 2x2, ..., 2xW の解を求める。
- この部分に動的計画法を用いる。
- 1x1, 1x2, ..., 1xW のサイズのウィジェットの解は簡単に求まる。
- 以下同様に、hx1, hx2, ..., の解を用いて、(h+1)x1, (h+1)x2, ..., (h+1)xW の解を求める。
この前処理にはO(H^2 W) かかります。この後、N 個のウィジェットそれぞれに対してO(1) で解を出力するので、全体の計算量はO(H^2 W + N) ですが、いまO(N) = O(HW) なので結局全体の計算量はO(H^2 W) になります。
この処理を行う前に、H よりもW が小さかった場合は適切にホーム画面とウィジェットを90度回転させるなどの高速化を行えば、最終的にO(min(H, W) HW) の解法を得られます。
O(min(H, W) HW) のコード(C言語)
C言語以外の言語(Java,PHP,Perl,Python,Ruby,C++,C#)のコードはpaiza会員ページにて公開しています。
⇒他言語のコードを見る(会員登録が必要)
#include <stdio.h> #define MIN(a, b) ((a)<(b)?(a):(b)) #define INF 1001001001 int main(void) { int h, w, n; int i, j, k; int dp[310][310], ans[310][310] = {{}}; char display[310][310]; int swap = 0; scanf("%d%d", &h, &w); for(i=0; i<h; ++i){ scanf("%s", display[i]); } if(w < h){ int t[310][310]; for(i=0; i<h; ++i){ for(j=0; j<w; ++j){ t[i][j] = display[i][j]; } } int tmp = h; h = w; w = tmp; swap = 1; for(i=0; i<h; ++i){ for(j=0; j<w; ++j){ display[i][j] = t[j][i]; } } } for(i=0; i<h; ++i){ for(j=0; j<w; ++j){ dp[i][j] = INF; } dp[i][w] = 0; } for(k=0; k<h; ++k){ int hist[310] = {}; for(i=0; i<h-k; ++i){ dp[i][0] &= display[i+k][0] == '0'; for(j=1; j<w; ++j){ dp[i][j] = display[i+k][j] == '0' ? MIN(dp[i][j], dp[i][j-1]+1) : 0; } } for(i=0; i<h-k; ++i){ for(j=0; j<w; ++j){ hist[dp[i][j]] += dp[i][j] && !dp[i][j+1]; } } int sum = 0; for(i=1; i<=w; ++i){ sum += hist[i]; ans[k+1][1] += i*hist[i]; } for(i=2; i<=w; ++i){ ans[k+1][i] = ans[k+1][i-1] - sum; sum -= hist[i-1]; } } scanf("%d", &n); for(k=0; k<n; ++k){ int s, t; scanf("%d%d", &s, &t); printf("%d\n", swap ? ans[t][s] : ans[s][t]); } return 0; }
その他の高速化ポイント
計算量の改善という観点では冒頭に述べたようにスタックを使うO(HW) 解法が存在します。その他には、定数倍高速化としていくつかの方法が考えられます。例えばウィジェットが置けるかどうかを判定する際に、すべての座標について調べるのではなく、ホーム画面上の情報を用いて適切にスキップして調べる方法などです。この方法は、ある特定のテストケースでは有効ですが、まったく有効でないようなテストケースも存在します。その場合はまたそのテストケースに合った高速化を行えば良いかもしれませんが、それではテストケースが大量にある場合に困ってしまいます。
その場合は定数倍高速化に頼らず、計算量の改善を目指してみると良いかもしれません。
paizaオンラインハッカソンのレポートは今回で終了ですが、次回開催の準備も進めておりますので是非次回も皆様のご参加をお待ちしております!
paizaは、技術を追い続けることが仕事につながり、スキルのある人がきちんと評価される場を作ることで、日本のITエンジニアの地位向上を目指したいと考えています。
「paiza転職」は、自分のプログラミング力が他社で通用するか(こっそり)腕試しができる、IT/Webエンジニアのための転職サービスです。プログラミングスキルチェック(コーディングのテスト)を受けて、スコアが一定基準を超えれば、書類選考なしで複数の会社へ応募ができます。
まずはスキルチェックだけ、という使い方もできます。すぐには転職を考えていない方でも、自分のプログラミングスキルを客観的に知ることができますので、興味がある方はぜひ一度ご覧ください。
また、paiza転職をご利用いただいている企業の人事担当や、paiza転職を使って転職を成功した方々へのインタビューもございます。こちらもぜひチェックしてみてください。
詳しくはこちら