![? 方法１：頻度を計算しておく
? 「それぞれの数字がいくつ含まれるか」を、配列を
使って求めておき、２つ以上含まれる数字がないか
を調べる。
for (int i = L; i <= R; i++) freq[A[i]]++;
頻度の計算の例
判定のやり方](https://image.slidesharecdn.com/arc022-140503083040-phpapp02/85/AtCoder-Regular-Contest-022-10-320.jpg)
![満点 N 10^5
? 尺取法を使う。
? 判定の部分に 方法２ を使う場合は、データ構造が
削除クエリに対応している必要があります。
l = 0;
for (r = 0; r < N; r++) {
while ([l,r]に同じ数字が２つ以上含まれている) l++;
answer = max(answer, r - l + 1);
}
尺取法の例](https://image.slidesharecdn.com/arc022-140503083040-phpapp02/85/AtCoder-Regular-Contest-022-13-320.jpg)
AtCoder Regular Contest 022 解説
- 1. AtCoder Regular Contest 022 解説 AtCoder株式会社 2014/5/3 1
- 3. A-問題概要 ● 文字列Sが与えられる ● Sからいくつか文字を省いて”ICT”を作れるか 判定せよ ● 大文字小文字は区別しない 1≦∣S∣≦100
- 4. A-想定解 ● 残す'I'はSの中で一番最初の'I'でよい。 ● 残す'C'はその'I'以降で一番最初の'C'でよい。 ● 残す'T'はその'C'以降で一番最初の'T'でよい。 ● 順番に貪欲的に文字を取っていく。 ● O(|S|) – 想定解
- 5. A-想定解2 ● 今回は探索する'ICT'が3文字なので、さまざまなその 場しのぎのアルゴリズムが考えられる。 ● 3文字を全通り試す – O(|S|^3) ● 'C'を決めてその左右に'I'や'T'があるか判定 – O(|S|^2) ● 最初の'I'と最後の'T'の間に'C'があるかどうか判定 – O(|S|)
- 6. A-大文字小文字 ● この問題では大文字小文字を区別しない ● 知るかぎり、どのプログラミング言語でも大文 字と小文字は別物と判断されるので、何とかし なければならない – 自前の比較関数を作る – あらかじめ全て大文字か小文字に揃える
- 7. B問題 細長いお菓子
- 8. 問題概要 ? お菓子がうんぬんと言っていますが要するに、 ? 長さNの数列Aが与えられるので、同じ数字を２つ 以上含まない最長の区間の長さを求めよ。 ? 部分点（50点）： N 100、Ai 100 ? 部分点（99点）： N 1000、Ai 1000 ? 満点：N 10^5、Ai 10^5
- 10. ? 方法１：頻度を計算しておく ? 「それぞれの数字がいくつ含まれるか」を、配列を 使って求めておき、２つ以上含まれる数字がないか を調べる。 for (int i = L; i <= R; i++) freq[A[i]]++; 頻度の計算の例 判定のやり方
- 11. ? 方法２：集合を扱うデータ構造を使う ? 例えばsetやDictionaryなど。 ? 集合に数字をどんどん追加していき、すでに追加さ れている数字があれば、ダメ。 判定のやり方
- 12. 部分点（99点）N 1000 ? 区間の左端だけを全部試し、それぞれに対してどれ だけ区間をのばすことが出来るかを調べる。 ? ひとつずつ数字を見ていき、その数字がすでに区間 の中に入っていたらその時点でストップ、とする。 ? 判定の方法は50点の部分点の方法と同様の方法を 使えば良い。（方法１でも方法２でも良い）
- 13. 満点 N 10^5 ? 尺取法を使う。 ? 判定の部分に 方法２ を使う場合は、データ構造が 削除クエリに対応している必要があります。 l = 0; for (r = 0; r < N; r++) { while ([l,r]に同じ数字が２つ以上含まれている) l++; answer = max(answer, r - l + 1); } 尺取法の例
- 14. C問題 ロミオとジュリエット
- 15. 問題概要 ? 要するに、 ? 頂点数Nの木が与えられるので、距離が最長となる 頂点のペアを１つ見つけよ。 ? 部分点(40点)：N 1000 ? 満点：N 10^5
- 16. 部分点（40点）N 1000 ? 片方の頂点を全て試し、その頂点から最も遠い頂点 を探す。 ? 最も遠い頂点を探すためにはBFSを使えば良い。木 なのでDFSを使ってもOK。 ? 木の上ではDFSをすることが多いので、DFSで書け るようになっておくのがオススメです。
- 17. 満点 N 10^5 ? ２頂点間の最大の距離＝直径と言います。 ? すなわちこの問題は、木の直径を求める問題です。 ? 木の直径を求めるアルゴリズムを２通りほど紹介し ます。
- 18. 木の直径の求め方その１ ? 簡単な木DPをする。 ? とりあえず根を適当に決めて根付き木にします。 ? 任意の２頂点間の移動は「まず根の方向にいくつか 辿り、根から離れる方向にいくつか辿る」となって います。 ? LCA(Lowest Common Ancestor) に注目します。 （移動で通る頂点のうち最も根に近い頂点がLCAです。） 4 5 1 6 2 3 87
- 19. 木の直径の求め方その１ ? ある頂点(Vとする)をLCAとする頂点のペアのう ち、最も距離が離れているものは、 ? 「あるVの子の子孫のうち最もVから遠い頂点」（V の子の数だけある）と「V」のうち、 Vから遠い順に２つ選んだ時の頂点のペア になります。 ? これをボトムアップに（葉から順に） 計算して行けば良い。 4 5 1 6 2 3 87
- 20. 木の直径の求め方その２ ? こちらは、方法としてはとても単純です。 ? まず、頂点を適当に選んでWとします。 ? Wから最も遠い頂点を探してVとします。 ? Vから最も遠い頂点を探してUとします。 ? すると、VとUが答えになっています。
- 21. 木の直径の求め方その２(仕組みについて) ? 木には中心というものがあります。 ? 木の中心とは、直径の中心のことです。 → 中心は辺上の点になることもあります。 ? 全ての直径は木の中心を通ります。 → 中心から各頂点への距離は直径/2以下で ????と考えたりすると証明できます。 V U W
- 22. 木の直径の求め方その２(仕組みについて) ? Vは中心をまたいでWと反対側にある最も遠い頂点 であるため、直径の端点となる。 ? Uは中心をまたいでVと反対側にある最も遠い頂点 であるため、直径のもう片方の端点となる。 ? というからくりになっています。 V U W
- 24. D問題 スプリンクラー
- 25. D-問題概要 ● 直交座標上にN個の格子点(x, y)が与えられる ● 各格子点に対して、それを中心として原点を通 る円を考える ● いずれかの円に含まれる格子点の個数を求めよ ● N ≦ 10^5 ● -10^5 ≦ x, y ≦ 10^5
- 26. D-部分点1 ● N ≦ 100 ● -100 ≦ x, y ≦ 100 ● 頂点と円の組み合わせを全て調べても間に合う ● O(N |x| |y|) – 10点が得られる
- 27. D-部分点2 ● N ≦ 1,000 ● -1,000 ≦ x, y ≦ 1,000 ● 全頂点の走査なら可能そう ● いろいろな図形を重ねた時に、何枚重なってい るか数える都合のいいアルゴリズムがあった気 がする???
- 28. D-部分点2 累積和
- 29. D-部分点2 ● 長方形ではないのでいつもの二次元累積和は使 えない – 一次元に分けたらできる ● 円周の左側を+1 右側を-1する
- 30. D-部分点2 ● +1や-1する点は円1つあたり、たかだかO(半 径)個くらい – 今回なら 1000 * √2 ● 総計算量はO(N max(|x|, |y|)) – 計30点が得られる
- 31. D-考察 ● 累積和をすると、そこにいくつの円が重なって いるかという余計な情報も求めることになる – 無駄 ● 1個以上重なっているかどうかさえわかればい い – 無駄な+1, -1をしないように削る
- 33. D-考察 ● どうやら完全に外側に接している部分付近だけ の+1, -1で充分 ● 外周さえ求まれば なんとかなりそう ● どうすれば 求まるのか???
- 34. D-部分点2 凸包
- 36. D-考察 部分点3 ● どの三角形の内側にも入らない点だけを考えれ ば良い – つまり凸包上にある頂点だけを考える ● 頂点は全て格子点にあるので凸包上にある点は たかだか√|x|個くらい ● 凸包で頂点を減らしてimos法をすれば良い – O(x log x + x√|x|) 計60点が得られる
- 37. D-さらに処理を少なく ● 凸包上の点を中心とする円でも、その円周が全 て外側に触れている(外周)わけではない – 外周のところだけで計算してよい ● 円どうしの交点、つまり円弧の両端が求まれば 良い ● 交差する円は、凸包の多角形における隣り合う 頂点に対応する円だけ – 幾何の計算をいくらかすれば交点はもとまる
- 38. D-外周だけを考える ● 各円弧の両端が求まれば、その間に含まれる範 囲だけ考えれば良い。 – ある点がある円弧に含まれるかどうかは凸包と同様 に外積を使えば良い ● 外周だけ考えるのは何とかなりそうだけれども はたしてそれで満点の制約において間に合うの か？
- 41. D-計算量 ● 各円弧の両端と原点を結んだ三角形の原点の部 分の内角は、その円弧の円周角に当たる。 – 全外周の円周角の総和はたかだか360° – よって中心角の総和はたかだか720° ● 円の半径は|x|*√2以下なので、外周の上限は |x|*4√2 * (円周率) ● 今回の問題ではおおよそ2,000,000くらい
- 42. D-計算量 ● 外周をたどって一回りする時、いろいろなy=k と交わる。 ● いまy=aと交わったとする。その次に交わるの はy=a+1, y=a-1, y=aのいずれかである
- 45. D-想定解まとめ ● スプリンクラーと世界一の花で凸包を取る。 ● 凸包上の点とそれに対応する円を順番に見てい き、隣の円との交点を求め、外周となる範囲を 得る ● 外周上を順番に走査してy=k(kは整数)との交 点を全て列挙する ● 左端と右端が全て求まるので適当に各yについ て引き算をして、総和を取ると答えになる
- 46. D-計算量まとめ ● 凸包でO(N log N) – バケツソートによる基数ソートをすればO(N) – 凸包上の点の数をMとする M = O(√|x|) ● 円どうしの交点を求めるのにO(M) ● y=k(kは整数)との交点を全列挙するのにO(|x| *4√2 * 円周率) ● おおよそ10^6オーダー