HUPPC #1 問題解説 - Darseinのプロコン日記

　HUPPC #1で取り上げた問題について、僕の想定解法＋αを解説します。
　コードに関しては、Aizu Online Judge→Virtual Arena→Contest→HUPPC #1→Standingと進めば参加者のコードが読めるようになっていますので、そちらを参考にして下さい。

A. Sum of Consecutive Integers

　連続した数字の和がNになるような数字の選び方が何通りあるか答える問題。

　始点と終点を決めて、その間の連続した数の和がNになるかどうかを調べて数え上げればよいです。
始点・終点ともにNまでの中から選べばよいのでO(N^2)のアルゴリズムとなります。
(より正確には、1<=始点<終点<=(N+1)/2で選べばよい。2つ以上の数の和でなければいけない、すなわちi==Nは数え上げないことに注意)
Nがたかだか1000までなので、このアルゴリズムで問題ありません。
これが想定解で、全探索の問題として採用したつもりです。

　ここからは余談といってもよいですが、この問題はさらに計算量を落とすことができます。
僕のVirtual Arenaのコードは、sum[i]に1からiまでの和を格納し、
sum[j]-sum[i]==Nとなるようなi,jの組合せがあるかどうか調べています。
sum[i] = 1+2+…+i , sum[j] = 1+2+…+j, より、sum[j]-sum[i] = (i+1)+(i+2)+…+jという連続部分を調べられます。
僕のコードのように愚直に調べるときはこの方法もO(N^2)ですが、
sum[i]が単調増加であることに注目すると、sum[i]+N == sum[j]となるようなjが存在するかどうかを二分探索で求めればよいので、O(NlogN)で解くことが出来ます。

　また、少し違う始点から問題を見てみましょう。連続した数が何個あるのかに注目します。
あるsに対し、s個の連続した数の和がNになる組合せはたかだか1つしか存在しません。
これは、始点を1だけズラすと和は必ずsズレることから明らかです。
ここで、s個の数の中央の値に注目します。
sが奇数の場合、中央の値をmとするとmより左側の値はm-1,m-2,…と減っていき、
もう一方の右側の値はm+1,m+2,…と増えていきます。
左右の数の個数も等しいので、s個の連続した数の和は、m*sとなります。
したがって、m*s==Nとなるmが存在するのか、すなわち、Nがsで割り切れるかを調べればよいことになります。
偶数の場合はもう少し複雑です。ちょうど中央となる値が整数として存在しないからです。
しかし、中央に位置する2つの値の和をm2とすると、同様にm2*s/2==Nを満たせばよいことに気付きます。
よって、Nがs/2で割り切れるかを調べればOKです。
sは最大でもNまで調べればよく、ひとつのsにつき定数時間でチェックができるため、この方法はO(N)で高速です。
ただし、すこし終了条件に気をつけないと、0+1+2+… +s-1= Nなどといったケースも数え上げてしまうので、注意が必要です。中央の値<(s+1)/2のとき終了するようにしましょう。
　ちなみにこのアルゴリズムは後輩が考えたもので、僕は彼の話を聞くまで思いつきませんでした。優秀で頭が下がりますね。

B. CamelCase

　U: 文字列における単語の先頭が大文字になっている(先頭文字も大文字)
　L: 文字列における単語の先頭が大文字になっている(ただし先頭文字は小文字)
　D: 単語と単語の間を’_’で繋いでいる
という文字列を、相互変換する問題です。文字列処理に関する問題として出題しました。
文字列の扱いは複雑で難しいですが、その分慣れる必要があると思います。

　問題としては言われたとおりに文字列に処理を行うだけなので、特に解説する部分はありません。
ただし、C言語などでchar型の定数長配列によって文字列を管理している場合、入力の文字列の長さが100文字以下でも、この問題の場合’_’の挿入により答えが100文字越えすることもある点には注意しましょう。
　大文字<->小文字の変換は、’a’-32や’A’+32を用いてできる、という知識は覚えておきましょう。
文字型<->整数型の変換で、char - ’0’を利用するのも頻出なので、是非覚えましょう。

　ちなみに、提出コードにはU->L,U->D,L->U,…というように、すべての場合の変換を書き下したものと、一度すべて小文字の単語に変換した後、結合する際に変換を施すものがありました。
個人的には後者の方をおすすめしたいです。
前者のような個々の場合分けが増えると、複雑になったり、コーナーケースが怖くなりますので、より一般化された後者のような解き方が選べるなら、そちらがよいと思います。

C. Red and Black

　二次元平面においてスタート地点(‘@’)から始め、隣接する上下左右のマスを辿り続け、赤マス(‘#’)を通らずに行けるマスの数を求める問題。

　典型的な探索問題です。探索は深さ優先探索(DFS)でも幅優先探索(BFS)でも構いません。
今回は、再帰関数の練習としてDFSを想定解とします。

　入力をchar board[H][W]などに受けたら、board[y][x]=’@’についてdfs(y,x)を答えとします。
dfs(y,x)は、マス(y,x)から到達可能なマスの数を返す関数です。
これは、(y,x)に隣接する4マスから到達可能なマスに、(y,x)の1マスを足した値ですので、
dfs(y-1,x) + dfs(y,x+1) + dfs(y+1,x) + dfs(y,x-1) + 1とすればよいです。
ただし、マス(y’,x’)が’#’であったり、範囲外であるときは0を返しましょう。
また、一度訪れたことのあるマスを重複して数えないような処理が必要です。
今回の場合、訪れたマスを’#’で上書きすることで解決できますが、盤面の状態を変更したくない場合もあります。
そういうときは、盤面とは別にvisit[H][W]のような配列を用意し、すでに訪れた場合は1を、訪れていない場合は0を値に取るようにする、などとすればよいです。
全てのマスについて、訪れる回数はたかだか一回なので、オーダーはO(H×W)となります。

　また、補足として、この問題に限ったことではありませんが、プロコンで二次元グリッド平面を扱うときには注意が必要です。
二次元配列に要素を格納するとき、入力の関係からもgrid[高さ][幅]とすることが多いですが、これを数学的な座標で表そうとすると(y,x)となります(上記でも暗黙としてこの表記を用いていました)。しかし、数学では座標を(x,y)と書くのが一般的で、混同しやすいです。
さらに、二次元配列では左上が(0,0)、右下が(y,x)ですが、数学では(0,0)が左下、(x,y)が右上で、上下関係も逆です。上に進みたいときはyの値を減らさなければいけない点も複雑なので、取り扱いには十分注意しましょう。

D. Cicada

　二次元平面を(0,0)から(H-1,W-1)まで最短経路で移動する。各マスに何匹かいる蝉にできるだけ遭遇しないようにするとき、出会う蝉の数の最小の数を求める問題。

　これも典型問題で、想定解法は動的計画法(DP)です。
最短経路でゴールに辿り着くためには、必ず右か下に進まなければなりません。
逆に言えば、あるマス(y,x)に到達するとき、左のマス(y,x-1)か上のマス(y-1,x)を通らなければなりません。
ということは、(y,x)に至るまでの最小の蝉の数は、(y,x-1)までの最小の数と(y-1,x)までの最小の数のうち小さい方に、(y,x)にいる蝉の数を足したものとなります。
これを(0,0)マスから始めて左から右へ、上から下へ求めていくと、(H-1,W-1)での最小の蝉の数が求まります。

　動的計画法は、
1. ある状態における解が一意に定まる
2. ある状態から別の状態に移る規則が定まる
3. 状態同士の順序関係(どちらから先にもとめるか)が定まる
とき、1つ1つの状態の解をメモしておくことで、複数回同じ状態の解を求めるときでも何度も計算しなおすことを防ぎ、効率的な計算を行うアルゴリズムです。
　今回の場合、
1.あるマスに至るまでの最小の蝉の数は一意に定まる
2.あるマスからは右、もしくは下のマスに移る
3.より左、もしくは上のマスから順に求める
とわかるため、動的計画法が使えます。
動的計画法のオーダーは基本的にO(状態数×ある状態から遷移できる状態の数)となるため、今回はO(H×W×2)= O(H×W)となります。

E. Carden Lantern

　ちょうちんで灯された道だけですべての史跡を訪れられるようにするとき、必要になるちょうちんの数を最小化する問題。

　町を頂点、道を辺とすることで、グラフ構造に落とし込めます。
このとき、ある道に必要になるちょうちんの数をその辺のコストとすると、
すべての頂点を連結するように辺を選んだときのコストの和を最小化すればよいことになります。
すなわち、このグラフの最小全域木(最小スパニング木、MST)を求める問題となります。
MSTを求めるアルゴリズムとしてはクラスカル法とプリム法が有名で、
どちらもO(|E|log|V|)です。どちらでも構いません(僕はクラスカル法で実装しています)

　この問題はMST、およびそれを求めるアルゴリズムを知っていればそれを実装するだけなので、知識があるかどうかを問う問題といってもよいです。覚えておきましょう。
プログラミングコンテストチャレンジブック2-5節に実装を含め説明が掲載されています。

F. Circle and Points

　平面上に点在する点を半径1の円で少しでも多く囲もうとするとき、最大いくつの点を囲めるかを求める問題。

　言うまでもなく幾何の問題で、明らかに今回のセットで最難の問題です。
幾何の問題は発想の部分でも数学色が強く、実装面でも独特の知識を要求され、また浮動小数点演算による誤差まであり、競技プログラマの中でも苦手だったり嫌いだったりという人が最も多いジャンルの１つです。
しかし、この問題は幾何の中ではそこまで難易度の高い問題ではないと思いますので、是非理解しておきましょう。

　まずはアルゴリズムについての解説です。

　実際に円を描いてみて、その中に何個の点が含まれるのか調べればよさそうですが、
離散でなく連続である平面の点全てを中心にして試してみる、というのは当然不可能です。
よって、中心とする点の候補を減らす工夫が必要となります。
ここで、１つの点だけを囲むのは簡単にできるので、2つの点を囲むことを考えます。
２つの点の距離が2よりも離れていると円で囲むことは出来ませんが、2以下であれば囲むことが出来ます。
このとき、この2点を囲みつつ他の点を最大限囲むにはどうすればよいでしょうか？
２点が円周に重なるようにギリギリにするのがよいように思えます。
下図を見ると、少しでも右にずらすと2点が囲めなくなり、逆に左にずらすと、右側の点が囲めなくなります。

もちろん、左にずらせば右側から外れる点よりも多くの点を囲むことが出来る場合もあります。しかし、結局そのような点に関しても、それを同様に円周上に乗せるようなギリギリの囲み方をする方が多くの点を囲めます。
すなわち、すべての2点の組合せについて、2点が円周上にあるような円を描いて、囲んでいる点の数を数えて最大値を求めればよいです。
任意の２点の組１つにつき、それらを円周上におくような円はたかだか2つなので、2点の組合せの数n(n-1)/2から、n(n-1)個の円だけ調べればよいことになります。
ある点が円に囲まれているかどうかは、その点と円の中心との距離が1以下かどうかを調べればよいので、すべての点について調べると１つの円につきn回かかります。
よって、全体でO(n^3)となります。nはたかだか数百なので、十分間に合いそうです。

　しかし、簡単に「2点を円周におく円を求めればよい」と言いましたが、実際どうすれば求められるでしょうか？作図しながら考えてみましょう。

2点A(xa,ya)とB(xb,yb)がわかっているとき、それを円周上に持つ円Oの中心(x,y)を求めたい、というのが今回の問題です。
２点が円周上にあるということは、中心からの距離が半径と等しいということです。
すなわち三角形OABはOA=OBの二等辺三角形となるので、OからABへの垂線との交点をMとすると、は、OMはABを二等分するためMはABの中点となり、
M=( (xa+xb)/2 , (ya+yb)/2)とわかります。
また、∠OMA=90°なので、ベクトルABの単位法線ベクトルに|OM|を掛けたものの始点をMに合わせると、Oの座標がわかります。

　実装について以下でさらに解説します。
幾何の基本はベクトルです。
C/C++にはベクトルを扱うデータ構造はライブラリとして与えられていないので、自作してもよいですし、C++のcomplex型という複素数を扱う型を代用することも多いです。複素平面を考えて利用します。

以下、僕の解答コードの一部です。

typedef complex P;
P center(P a,P b){
P m = (a+b)/2.0;
P n = (a-b)*P(0,1);
n = n/abs(n);
double x = abs(a-b)/2.0;
return m + n*sqrt(1.0 - x*x);
}

　typedefの部分は、単に何度もcomplexと書くのが面倒なだけなので、特に気にしなくともよいです。適宜補完して読んで下さい。
m = (a+b)/2.0の部分は中点mを求めています。そのままです。
n = (a-b)*P(0,1)は法線ベクトルを求めています。これは少しわかりづらいですが、ベクトルa-b = (x,y)とおくと、(x+yi)*(0+i) = (-y + xi)となり、すなわちベクトル(-y,x)を表します。
つまり、a-bを反時計回りに90°回転したものとなり、これは法線ベクトルとなります。
n = n/abs(n)は単位法線ベクトルを求めています。nの大きさで各座標値を割ることで標準化しています。
１つ飛んで、最後の行は、点mを始点とし、単位法線ベクトルに|OM|を掛けたものの座標を求めています。|OM|は三平方の定理より、sqrt(半径^2 - |AM|^2)に等しいため、最後の行の式となります。xは|AM|を表しています。

　幾何は一見しただけではなにをやっているのかわからないような独特の実装や知識が用いられることが多いため、慣れることはもちろんですが、よく使うものはテンプレ化して持っておくのがよいでしょう。今回は用いませんでしたが、内積や外積、３点の位置関係、線分の交差判定など、よく問われるものは他にも数多くあります。
また、誤差にも注意しましょう。例えばif(a+b==1.0)のような判定を使っていると小さな桁の誤差によりWAが出る可能性が高いです。小さな定数EPSなどを用いてif(abs(a+b-1.0)