ICPC模擬地区予選2022 準備記

ICPC模擬地区予選2022 参加者の皆様、お疲れ様でした。ご参加いただきありがとうございます。

スタッフとして現地にいたほか、問題準備にも携わっていました。問題セットや解説などはそのうちアップロードされると思います。以下、担当の問題に対する感想です。

E: Sharp 2-SAT

データセットを担当しました。

当初、入力をランダムに生成したら、充足不能なものばかりできてしまい困りました。最終的には、変数の割り当てをいくつかランダムに決めて、それに矛盾しない節をランダム生成、という方法を取りました。

時間制限は 8 秒になっています。分割統治のたびに (I)FFT が 48 回必要なので、定数倍が軽いとは言えないものの、一応 Java でも 4 秒くらいあれば通ったので、ちゃんと実装すれば時間制限はそこまでキツキツではないはずです。

F: Seimei Handan 999.0

原案・データセット・解説を担当しました。

Parameterized matching に帰着させてロリハ・(K)MP・Z などで解けます。どのみち重複除去のためにロリハ (か、さもなくば接尾辞配列等) を実装する必要があることもあり、まあロリハで解かれるだろうなと思っていました。実際そうだったんですが、1 チームだけ Morris-Pratt で解いたチームがあってびっくりしました。正当性は自明というわけではないので、知っていたのではないかと思います。

Parameterized matching の部分は論文そのままで解けるので、もうちょっとひねりを加えられないかと考えてはみたのですが、思いつけなかったのでそのままになりました。とはいえこの概念を知っている人が参加者の中に 1 人くらいしかいなかったような気がするので、杞憂だったかもしれません。検索ありのルールだったらもっと解かれていたんでしょうか。

G: Avoid bombings

問題文・テスターを担当しました。

実装したくないなぁとずっと思いつつ、一週間くらい前につらみを感じながら実装始めました。こんなもの誰も解かないだろと思っていたら、案の定提出は 0 件だったので、我々の苦労が報われることはありませんでした。

円弧がなければライブラリゲーなので、円弧の代わりに微小線分の折れ線で近似する、という解法も実装してみました。ジャッジ解の正当性の検証には役立ったものの、精度を妥協してもなお実行時間が分単位になったので、本番これで解けることはないと思います。

ジャッジ解自体の精度にも不安があったので、実は許容誤差が問題文記載のものの 1.1 倍に緩和されていたりします。この配慮が生きることはありませんでした。

H: Sloppy city planning

原案・問題文を担当しました。Insane Connection Plan City (ICPC) という、命名の時点で常軌を逸した、一方通行だらけな上に強連結とは限らない都市が舞台です。強連結にしたところで根本的に住心地が改善するとはあまり思えません。絶対住みたくないですね。

本家の ICPC で完全グラフ関連の問題が出ていたこと、制約次第では (特に国内予選形式では) Warshall-Floyd 回すだけで解けるということもあり、模擬国内 D-E にちょうどいいかなと思い、2019 年に提案していました。長らく使われなかったので日の目を見ることはないと思っていました。

3 乗時間解法を落とすために頂点数が最大 3000 と大きくなっていますが、そのせいでファイルサイズが大きすぎて、ジャッジシステムへのアップロードに失敗するというトラブルもありました。制約を落とすという案もありましたが、最終的にはシステム担当者が頑張ってくれたので、そのまま出題できました。感謝です。

I: N-1 Truths and a Lie

線形時間解法の方針の一つ (ちょっと間違っていた) を提案しましたが、未実装です。あと、N=1 が問題文の記述に反せずコーナーケースになっていることを指摘し、最終的には制約で弾くことになりました。お誕生日系のコンテストだったらそのまま出ていただろうなぁと思います。

J: Most distant point from the stations

特にかかわってはいないんですが、幾何 2 問もいる?と内心思っていました。いらなかったと思います。ボロノイ図の実装ってどれくらい大変なんでしょう。

K: Sort Compressed Strings

原案を担当しました。

構文解析パートは本家で 2 回 (国内2006国内2019) と模擬で 1 回 (模擬国内2019) 出ているということもあり、典型と言っていいでしょう。とはいえ最初のを除き構文解析パート以外が本質です。AtCoder などで構文解析が出題されることは少ないので、練習機会の提供という意味で言うと、ほぼ純粋な構文解析問題みたいなのもあった方が良かったりするんでしょうか。

展開後の文字列長の上限について、原案時点では 10^18 文字になっていたんですが、ハッシュの衝突確率の評価がやばくなるという指摘を hos さんより受け、今の形になりました。それはさておき、1e9+7 など有名 mod を落とすケースは入っているようなので、注意しましょう。mod (2^61)-1 の方法などがおすすめです。

…と書いてみたはいいものの、実は原案出しておきながらまだ実装していないので、どのあたりが難しいのかわかっていません。実装してみたらかなりハチャメチャになるという噂ですが、果たして。

それと、個人的にローリングハッシュはあんまり好きではなくて、deterministic な解法が無いかと模索してはみたのですが、見つけられませんでした。誰か思いついたら教えてください。

L: Tree Automorphism

原案を担当しました。

部分木のハッシュの衝突に注意しましょう。map<子のソート済みハッシュ列, 新たなハッシュ値> を管理するようにすると、多少遅くなるかもしれませんが、衝突の可能性を考慮せずに済みます。ただし全方位木 DP には使えません。

実装上の工夫として、辺を倍化すると答えが変わらない上に場合分けが減るんですが、これをしたチームはほとんど見ませんでした。そもそも全方位木 DP (?) っぽい方法で解いてるように見えたチームもありましたが、楽なんでしょうか。よくわかりません。

おわりに

JAG の問題セットは、数少ないまともな問題案の中からなんとか絞り出しているような感じで、バランス等も安定しているとは到底言えない状況です。そもそも問題案が枯渇しかけていて、来年以降問題セットを作れるかどうかすらわかりません。ICPC 引退した人が JAG に加入して問題をドシドシ提案してくれると、とても助かります。ご検討のほど、よろしくお願いいたします。
jag-icpc.org

Xmas Contest 2019 H - Stamps 3

問題はこちら
snukeさんによる解説と方針が違ったので書いてみる。

とりあえず、上の解説に述べられている通り行ごとに独立に考えればよく、各行0, 1, 3回で塗れるかは容易に判定できる。
特に、事前に白マスの位置を配列で持っておくと、そのサイズをnとするとき、1回で塗れるかの判定はO(n + log W)でできる。(log WはGCDの計算のため)

さて、2回で塗れるかの判定についてであるが、「1つ目のスタンプを決めたときに、残った白マスを1回で塗れるか」を判定できればよい (ここまで上の解説と同じ)。
ここで、nマスを2回で塗れるということは、少なくとも片方のスタンプでn/2個以上のマスを塗る必要がある。このようなスタンプの間隔をpとする。
ところで、間隔pのスタンプで塗れるマスは高々ceil(W/p)個しかないので、ceil(W/p)>=n/2 が成り立たなければならない。言い換えると、考慮すべきpの上限はO(W/n)となり、nが大きければpの上限が小さくなる。
また、そのようなスタンプの初期位置についても、(白マス位置) mod pの頻度がn/2以上となるものだけ試せばよく、これは高々2箇所しかない。残った白マスを1回で塗れるかは前述の通り。

計算量は緩く見積もってもO(HW log W)となる。

ACPC2015Day3 F / AOJ 2763 - Miko Mi String

問題はこちら

入力文字列Sについて、長さをn、最小周期をpとします。
さらに、q=p*floor(n/(3*p)+1)とおきます。
このようにすると、
2*q<nであるときかつそのときに限り、題意を満たす文字列A,Bが存在し、さらに求めるべきABの長さはqとなる
ということが容易に証明できます。

以上の考察を基にコードを書くと次のようになります。

#include <stdio.h>
#include <string.h>

char s[1000010];
int mp[1000010];

int main(){
	int i, n, t, p, q = 0;

	fgets(s, sizeof(s), stdin);
	n = strlen(s) - 1;

	mp[0] = -1;
	t = -1;
	for(i = 0; i < n; ++i){
		while(t >= 0 && s[t] != s[i]){
			t = mp[t];
		}
		mp[i + 1] = ++t;
	}
	
	p = n - mp[n];
	q = p * (n / (3 * p) + 1);
	if(q * 2 >= n){
		q = 0;
	}

	if(q != 0){
		printf("Love %.*s!\n", q, s);
	}
	else{
		puts("mitomerarenaiWA");
	}

	return 0;
}

さらに頑張ると、次の162バイトのコードになります。

char s[1<<20];m[1<<20],n,t;main(){for(gets(s);s[n];m[++n]=--t)for(;t&&s[~t]-s[n];t=m[~t]);t-=~n;n=!printf(t*2<n?"Love %.*s!\n":"mitomerarenaiWA\n",t*=n/3/t+1,s);}

CODE FESTIVAL 2014 上海ツアー参加記

CODE FESTIVALの上海ツアー(2014/12/20 - 2014/12/23)に参加してきました.

だいぶ前

これのためにパスポートを取得する.

1日目

空港集合が10時半という極めて人道的な時間だったので,優雅に8時頃起きて朝食を食べる.
9時頃家を出て,無事に空港まで辿り着く.
チェックイン後,保安検査でベルトを外し忘れて-25.00ptsを得る.つらい.
保安検査を抜けて,とりあえず100元(2100円程度)両替する*1
同行者(@cyagiya0122さん)がプロだったので,空港のラウンジに入れた.ありがてぇありがてぇ.
やや遅れて飛行機出発.機内食が出たので食べる.特筆すべきことはなかった.
上海浦東国際空港に無事着陸.入国審査では特に何も聞かれることなくそのまま通過.
上海市街地へこれで移動.300km/h.結構速かった*2
ホテル到着.集合まで10分しかなかったので,荷物を部屋に置いて急いで戻る.
上海観光.黄浦江を見た後,謎トンネルで黄浦江の下を通る.
その後テレビタワーか何かに上る予定だったらしいが,人が多すぎたらしく断念.色々あって夕食が早まることに.
船上で夕食.たまに見た目を裏切られてなんだこれは…ってなる.スプライトの美味しさに気付く.
夕食後にクルーズ.寒い.
おしくらまんじゅう(物理)している人がいた*3.絶対何か間違ってる.
クルーズ後にレーザーの洗礼を浴びる.現実は非情である.
ホテルに帰る.とりあえず部屋を色々確かめる.カーテンレールが窓の端の方しかないため絶対に閉まらないという謎構造を発見する.
リクルート社よりモバイルWi-Fiルータを2つ受け取っていたので確認する.1つは問題なく使える.もう1つは使う以前にそもそも電源ケーブルが刺さらない*4.色々試行錯誤した結果,使えることが判明.
後者のルータを使ってTwitterする.その後VPN Gateを設定する.快適なTwitterライフを送ることができた.ありがてぇありがてぇ.
1日目は普通に寝る.

2日目

トイレを詰まらせる.
お腹が空いていたので,とりあえず放置して朝食会場へ行く.
朝食後,従業員を呼ぼうかと思ったが面倒に思う.洗面台に昨日使用した歯ブラシがあったので,トイレに突っ込んでかき回してみる.無事に流れる.
その後は集合時間までゆっくりTwitterしていようかと思ったが,途中で清掃員っぽい人が来る.何かよく分からないことを言われたので,"About 10 minutes."と答えてみる.通じたのかよく分からないけどとりあえず10分後に部屋を出ることにする.
部屋を出てホテルのロビーでだらだらする.集合時刻になる.「まだ、ここにない、出会い」がある.今何時だか知っていますか.
ちょっと遅れて出発.そのまま早めの昼食.まあまあ美味しかった.
その後,上海交通大学でコンテスト.4問しか解けなかった.つらい.確率は苦手だった.
懇親会は特に何事もなかった.スプライトがおいしかった*5
夜はsnukeさんの部屋におじゃまする.きゅうりを集めたり王様を引いて死んだりする.楽しかった.

3日目

この日は一日中観光.
昼食で北京料理を食べる.すごく美味しかった.
何か豪邸を見る.家だった.
その後は上海老街で買い物など.レーザーの洗礼を浴びる.雑貨屋的なところで楕円体状の磁石*6をちょくだいさんが4組買ってた.
続いて小籠包作り.美味しさ0の小籠包ができた.
小籠包作りの後,記念撮影をする.迂闊なことに,帽子を深めにかぶっていてさらにマスクをしていたため,顔がほとんど隠れてしまった.ごめんなさい.
夕食は上海の海鮮料理.上海蟹は食べづらく,労力に見合うだけのものがないと判断してほとんど手を付けなかった.
夕食後に上海雑技団を見る.プロ.
ホテルに戻る.翌日のTLEは命にかかわるので早めに寝る.

4日目

起きて朝食を食べる.一度部屋に戻る.トイレを詰まらせる.2日目と同じ方法で解消させる.
出発して空港に着く.実は元を全く使っていなかったので,空港で使うことにする.てきとーに買って99元使う.
その後搭乗.機内食はパン1個だった.
着陸.入国審査を抜ける.なぜか保安検査の人に質問される.
という感じで何事も無く上海ツアー終了.

まとめ

リクルート is GOD

*1:結局両替したのはこれが最初で最後だった

*2:時間帯によっては430km/hまで出すらしい

*3:ちょくだいさんとかしめじさんとか

*4:後で確認したら,明らかに他の人とケーブルが違っていた

*5:炭酸苦手なのでちょっと振って抜こうかと思ったら,油断して服にかかった.

*6:1組(磁石2つ)で2元

CODE FESTIVAL 2014 参加記

CODE FESTIVAL 2014 本戦に参加してきました.
以下,ほぼ殴り書き.

予選A

出てみたら12位で予選通過した.
Mi_Sawaさんが面白かった.

予選B

予選Aで通過していたので,気楽に出る.6位タイ.
Mi_Sawaさんが面白かった.

本戦前日

前泊組なので前日に東京入り.
@hotpepsiさん,@Darseinさん,@kyos1704さんとともにご飯を食べに行く.
カレーを食べたら胃の容量的な限界を感じたので,3人と別れてホテルに戻る.
夜道なので気をつけていたが特に何もなかった.

本戦1日目

@Darseinさんが隣の席だった.
この時点で@DarseinさんとのPokeが連続5700回くらいだったので,6000を目指すことにした.
普通に達成した.間近にいる人とPokeするのは楽しい.
その他,数人の参加者とPokeした.@tsunenarazuさんごめんなさい.

本戦開始直前

FA賞とLA賞があるということが公表される.
ルールの穴を突いてみる.オープンコンテストへの参加が認められる*1

本戦(本番)

問題と順位表はこちら

コンテスト開始.
とりあえずABCDEを普通に解く.
F以降,難易度が急激に上がっていて驚く.
とりあえず問題を一通り読んでみる.
Fはピンと来ない.
Gは素因数分解まで自明だけどそれ以降さっぱり分からない.
Hはよく分からない.
Iはクエリ先読み+平面操作+LCAでできそう.実装つらそうだった.
Jはどう見ても最終防衛っぽい.
というわけで,この時点でできそうなのがIだけだった.絶望.
仕方がないのでIを書くことにする.頭付いていないので,45度回転を思いつけなかった*2
バグらせながらも何とかサンプル合う.通らないだろうと思いつつ提出.通る.すごく驚く.ついでにFA賞らしかった.それとパーカー確定.
Fを考えてみる.サンプルから,こんな感じかなぁと思いつつ書いてみる.提出する.通る.
Gをググったり*3Hを考えたりしたけど,解けない.
諦めて,用意された軽食を食べる.ゆで卵剥くのはどう考えても面倒なので手を付けないことにする.
そのまま終了.

結果発表

順位表(凍結)を見た感じ30位以内は確定っぽいので,上海ツアーは行けそうだなーと思いつつ結果発表を待つ.
21-30位にはならなかったので賞金は貰えそう.嬉しい.
11-20位でも名前が出てこなかったので,賞金>パスポート取得費用が確定.嬉しい.
6位になっても名前が出てこなくてやべぇってなる.
5位でようやく名前呼ばれる.エキシビション出場することになってうあぁってなる.

解説

Hは諦めずにもうちょっとちゃんと考えれば糸口がつかめたかもしれないと思う.ちょっと残念.
Iはやっぱり45度回転させるべきだと思った.

フードタイム

肉がどう提供されるのか気になっていたけれど,割と普通だったので安心(?)した.
あと,少量ながら野菜もあったのは嬉しい.

診断人さんのニコ生

面白かった(小並感)*4

エキシビション

問題はこちら
準備のため早めに会場へ.このせいでライトニングトーク見られない.つらい.肉LTとnotさん見たかった….
1時間で2問と聞いてあっ…(察し)ってなる.
コンテスト開始早々,準急さんのタイピング音が聞こえてきてやばすぎでは…ってなる.
とりあえずA問題をてきとーに書いて投げてみる.案の定WAなのでもっとちゃんと考えてみることにする*5
色々紙に書いて実験してみた結果,次の仮説が生える:

  • 与えられたグラフから,3つ組に関係しない辺を取り除いたグラフを,Gとする.Gのすべての連結成分をクリークで置き換えたグラフをG*とする.このとき,G上で目的の遷移が可能 iff G*上で目的の遷移が可能.

G*での判定は,実際に遷移をてきとーにシミュレートしてみればできそうだった.
という感じの方針で書いてみる.終了5分前に提出.通る.嬉しい.
残り5分でできることはさすがに残っていなかったので,clarでたこ焼き乞食してみる.
終了直前に準急さんがBを通していてやべぇってなる.終了.

2次会

楽しかった(小並感).
ホテルに戻ったのが0時半頃だった気がするので,寝坊しそうな気がしていた.

本戦2日目

なんとか起きる.つらい.
用意された軽食を食べる.おにぎりおいしい.

朝プロ(Hard)

問題はこちら
A読んでみる.分からない.
B読んでみる.自明っぽい.普通に通る.
頭回っていなくてA考えるの面倒なのでググるこんなページが出てきたのでそのまま書いてみる.通る.
Cは定数倍やばそう.つらいので解かないことにする.
Dはスネルの法則っぽいがどう考えても解けそうにないのでやめる.
後で聞いてみたら,Cは普通に2次元累積和で間に合うらしかったので,書けば良かったと後悔.
それと,Aは普通に思いつくべきだった.つらい.

コンテンツ色々

ご飯食べた後,colunさんのトークライブを見に行く.
折角だからと書道コーディングもしてみる.今流行りのis_uruuを書いてみる.
秋葉先生のトークライブを見に行く.リプライ投げればスクリーンに流れるらしいと聞いて,男の娘喫茶*6について聞いてみる.満足.
秋葉先生のトークライブを途中で抜けて,ライトニングトークを聞きに行く.
山本さんとtokoharuさんのLTを見る.面白かった.りんごさんのLT(?)を見る.なんだ,これは…(困惑).
残った時間でimosさんのトークライブを見に行く.imos法の解説は役に立つかもしれない.

チーム対抗リレー

結果はこちら
チームに@japljさんがいてやべぇってなる.
ルールを見る.途中で交代不可というのがどう見てもやばそう.慎重に行かないとダメっぽい.
チーム戦略としては,2人ずつ5グループに分かれてA-Eを担当することになる.私ともう1人はEを読むことになる.
問題文を読む.マンハッタン距離とかランダムとか出てきてやばそうに見える.最後まで読むとなんだこれは…ってなる.自明だった.
ペアの人が詰まりそうな気がしたので,おせっかいかと思いつつ紙にコード書く.
自分の担当が終わったので,F以降を読んでみる.Jだけ明らかに難易度おかしいように見える.
色々あって,Iを担当することになる.色々バグらせたので10分ほどかかる.サンプル合ったので提出.通る.緊張感がやばかった.とりあえず戦犯にはならなかったようなので一安心.
と同時に,Jが既に解けていたらしいので,@japljさんがコード書きに行く.1分でACして全完.3位.
解法聞いて後でじっくり考えたらなるほどなぁ…という感じだった.

帰宅Phase

名残惜しいと思いつつ帰宅.
ポケモンジェットだった.

まとめ

とても楽しかったので来年あるなら参加したい.
そのためにはアンケートを書かなければならない(義務).

*1:個人的にはメリットがなかったので参加しなかったが,@nikollsonさんあたりはLA賞絡みで参加していたようだった.

*2:このせいで実装量が40行程増えた.

*3:Multiplication Magic Squareという概念らしいことは分かった.

*4:yellow+target <<(超えられない壁)<< target と思ったのは内緒.

*5:TLEも出たが個人的にはどうでもよかった.

*6:正確には男の娘バーだったらしい

ACM-ICPC 2014 国内予選参加記

九州大学のチーム # kotoshi koso namae wo kangae として参加*1
ABCDEを解いて12位.

発生した事案は時系列順に以下の通り.うろ覚えなのでもしかしたら間違っているかもしれない:

開始0分.
まずはF5キーを押す.すぐに開けないのは例年通り.
1分くらい経って問題を閲覧できたので,1部印刷.
Aをチームメイト1に,Bをチームメイト2に任せ,私はCを読むことにする.

C読んでみる.
幾何っぽい図がある.嫌な予感がする.
問題文の読解に時間かかる.
なんとか理解できたので解法を考える.
「y軸に平行な直線で太陽をぶった切れば,あとはやるだけ」ということにすぐ気付く.
幾何だけど,幾何じゃなかった.
2年前までのCは割と実装問題が多かった気がする*2ので警戒していたが,今回は実装軽そう.
解けることを確信.

チームメイト2に状況を聞いてみる.
ただのシミュレーションらしい.
D問題を読んでもらうことにする.
その間にEの問題文を読む.
どう見てもこれにしか見えない.
解けることを確信.

チームメイト1の様子を見てみる.
Aで詰まっていたようなので,代わりに解くことにする.
Aの問題読んでみる.何か面倒そう.
制約見てみる.Aらしく小さい.
税抜き前の価格全探索するのが楽そうなので,その実装にする.
税抜き前の価格として0円がありうるのか気になる.記述を探す.ありえないということがInput欄に書いてある.なぜそこに書いた.
とりあえず書く.色々ミスりながらも,書き終わる.サンプル通る.投げる.18分くらいでAC.

チームメイト2にBを任せる.
その間にDを読んでみる.
ただの探索っぽい?
実装量よく分からないので,確実にできるEを先に解くことに決める.

チームメイト2がBを書き終わる.
サンプル通らない.
コード印刷して,紙デバッグしてもらう.
交代して,私がC書き始める.
書いている途中でBのバグ見つけたらしいので,再度交代.B修正してもらう.
修正はすぐ終わる.サンプル通る.投げる.36分くらいでAC.
交代してCの続き書く.書き終わる.サンプル通る.投げる.41分くらいでAC.

Dより先にE書き始める.結果的には失敗だったかもしれない.
木の直径を線形時間で求める方法が重み付き木でも使えるかどうか自信なかった*3ので,幅優先探索をn回繰り返すことにする.nの上限は800なので余裕.
書き終わる.サンプル通らない.よく見たら入力形式間違えてる.
修正.サンプル通らない.葉の処理ミスってた.
さらに3回くらい修正.ようやくサンプル通る.投げる.56分くらいでAC.

そのままD書き始める.
あっさり書き終わる.サンプル通る.投げる.65分くらいでAC.
この時点で3位*4.6完以上がそんなに出るとは思えないので,この時点で国内予選通過をほぼ確信.
以降は割と気楽にやる.

F読んでみる.
Fはサイコロ.そういえばサイコロを持って来なかったことに気付く.失念していた.
impossibleかどうかの判定方法が分からない.チームメイトに任せてみる.

Gは面倒そうな幾何.できるか分からないけどやってみることにする.「どうなってもいいよね?」とチームメイトに聞いてみたが,大丈夫らしい.好きなようにやることにする.
色々書いてみる.ダメそう.頭付いてない.
結局何もできないまま,国内予選終了.

結局,全体で12位.学内1位なので国内予選通過確定.

後日,Gの解法を師匠*5に聞いたら,3つ以上の円が共通部分を持たないという制約から,割と簡単に解けるらしい.思いつかなかった.やっぱり私はまだ幾何初心者らしい.

全体を通して,WAが1回も出なかったので,その点は良かった.
6完できなかったのは残念だけど,仕方ない.

*1:昨年のチーム名は // ato de namae wo kangaeru

*2:昨年は軽かった

*3:実際には使えたらしい

*4:上は東大しかいなかった

*5:@Mi_Sawa

AOJ 2562/JAG春コンテスト2012H: Rings

JAG春コンテスト2012の問題がAOJに収録されたので,以前書いたコードを投げてみました
公式の解説によれば

  1. 座標変換
  2. 平面同士の交線を求める
  3. 円と直線の交点を求める

ということをするらしいですが,そんな回りくどいことしなくても解けるということで久しぶりにブログ書いてみます.

まずは記号の定義です.
円1について,中心を\bf{c}_1とし,中心から円周への直交するベクトルを\bf{u}_1,\bf{v}_1とします.
円2についても同様です.

とりあえず円2について考えてみます.まずは2次元で考えましょう.
2次元の円上の点は,角度θを用いて(cosθ,sinθ)と表せます.
これは,直交する単位ベクトル(1,0), (0,1)を用いれば (1,0)cosθ+(0,1)sinθ とも書けます.
もっと言えば,直交する単位ベクトル\bf{u},\bf{v}を用いて\bf{u}\cos \theta+\bf{v}\sin \thetaと書けるはずです.
(より一般に,\bf{u},\bf{v}が直交していれば,\bf{u}\cos \theta+\bf{v}\sin \thetaは楕円となるはずです.図1参照.)
最早これは2次元に限った話ではなく,当然3次元でも同様の表記が可能です.
すなわち,円2上の点は,角度θを用いてp_2=\bf{c}_2+\bf{u}_2\cos \theta+\bf{v}_2\sin \thetaと表すことができます.
f:id:climpet:20140228001054p:plain

次に,円1について考えます.
円1を含む平面S1について,2つの円が繋がっているのは,次の条件を満たすときです.

  1. S1と円2の交点が2つ存在する.
  2. 2つの交点について,片方が円1の内側,もう片方が円1の外側にある.

さて,S1の法線ベクトルは\bf{n}_1=\bf{u}_1 \times \bf{v}_1です.
ここで,\bf{p}_2がS1上にあるならば,(\bf{p}_2-\bf{c}_1)\cdot \bf{n}_1=0が成り立つはずです(図2参照).
これとさっきの\bf{p}_2の式を合わせて色々整理すると,
a cosθ+b sinθ+d=0 という式になります.
さらにここらへんの式を使うと,
e sin(θ+φ)+d=0
という式になります.a,b,d,e,φについては普通に計算できるはずなので,各自計算してください*1
この式から,(交点が存在するならば)θを2つ求め,それぞれp_2=\bf{c}_2+\bf{u}_2\cos \theta+\bf{v}_2\sin \thetaにぶちこめば
p_2が求まります.
あとは,それが円1の内側かどうか判定すればよいです.これは,|\bf{p}_2-\bf{c}_1|<1であれば内側,さもなくば外側となります.
f:id:climpet:20140228001103p:plain

所々端折りましたが,以上のような手順で,高校数学程度の知識(のはず)があれば,座標変換など使わずに答えを求めることができます.

*1:ぶっちゃけ結果忘れました

AOJ 2506 - Operation training for BYDOL

この問題では、「弾が点Aから壁上の点Pで反射して点Bに達する」という条件を満たす点Pを求める必要があります。これは二分探索や三分探索で求めることもできるらしいですが、今回は探索なしで求める方法を述べます。

以後、壁の中心座標を(0,0)、半径をrとします。また、点A,B,Pの位置ベクトルを、それぞれ\vec{a}=(a_x,a_y),\ \vec{b}=(b_x,b_y),\ \vec{p}とします*1。さらに、\vec{p}=r\vec{u}を満たす単位ベクトル\vec{u}=(x,y)を定義することにします。単位ベクトルなので、当然x^2+y^2=1となります。

f:id:climpet:20130321173642p:plain
図1のように、ベクトル\vec{v}=\vec{AP}が点Pで反射した後のベクトル\vec{w}がどのような計算式で求められるか考えてみましょう*2。ここで、ベクトル\vec{v}を、\vec{u}に平行な成分\vec{v_o}と、垂直な成分\vec{v_n}に分けてみることにします。ベクトル\vec{w}についても同様です。このとき、図から\vec{v}=\vec{v_o}+\vec{v_n},\ \ \ \vec{w}=\vec{w_o}+\vec{w_n},\ \ \ \vec{w_o}=-\vec{v_o},\ \ \ \vec{w_n}=\vec{v_n}が成り立ちます。また、\vec{v_o}内積を用いて\vec{v_o}=(\vec{v}\cdot\vec{u})\vec{u}と表すことができます。これらの式から、\vec{w}=\vec{v}-2(\vec{v}\cdot\vec{u})\vec{u}が成り立ちます*3

反射後のベクトル\vec{w}は、ベクトル\vec{PB}=\vec{b}-\vec{p}=\vec{b}-r\vec{u}と同じ向きでなければなりません。従って、\vec{w}\times\vec{PB}=0が成り立ちます(2次元ベクトルにおける外積については、ここを参照してください)。これらの式から色々と計算し、さらにy^2=1-x^2を用いてyを除去すると、次の方程式が得られます。
4(c_1^2+c_2^2)x^4-4(c_1c_4+c_2c_3)x^3+(c_3^2+c_4^2-4c_1^2-4c_2^2)x^2+(2c_1c_4+4c_2c_3)x+(c_1^2-c_3^2)=0
ただし
c_1=a_xb_y+a_yb_x
c_2=a_xb_x-a_yb_y
c_3=r(a_x+b_x)
c_4=r(a_y+b_y)
とします。
これは4次以下の方程式です*4。幸運にも、4次以下の方程式については代数的解法が知られているため、厳密解を求めることもできます。それ以外の方法としては、ベアストウ法と呼ばれる数値計算法が知られており、この方法でも解を求めることができます*5。いずれの手法でも、解は複素数として得られます。
これを解くことで得られた、-1\le x\le 1を満たす*6実数解xに対し、y=\sqrt{1-x^2}とします。このとき、P(rx,ry)またはP(rx,-ry)が、反射点の候補となります。

このようにして求められた反射点候補の中には、実際には反射点でないような点も含まれている可能性があります。そのため、本当に反射点であるのかどうか確認する必要があります。ここで、Pが反射点であれば\vec{w}\vec{PB}は平行でかつ同じ向きとなるため、\vec{w}\times\vec{PB}=0*7および\vec{w}\cdot\vec{PB}\gt 0の両方が成り立ちます。これらを計算することで、反射点でない候補を除外することができます。

f:id:climpet:20130321173708p:plain
ただし、この判定を行っても、除外できない非反射点が存在します。それは図2の点P'のように、「円の内側で反射して点Bに達する」というものです。これを除外するためには、「線分APまたはBPと円の交点が、端点以外に存在するかどうか」を判断すればよいです。図2では、反射点である点Pについては、線分APおよびBPと円の交点は、端点以外に存在しません。一方、非反射点である点P'については、線分AP'上に交点Qが存在します(線分BPについても同様)。したがって、点P'は反射点ではないと判断できます。
この問題では、どの道すべての壁との交点判定を行う必要があるため、特に手間が増えるということはないでしょう。

以上が、反射点を探索なしで求める方法です。ここからグラフを作って最小費用流に帰着させることになりますが、詳細は省略します。公式スライドなどを参照してください。



…記事書いてみて思ったのですが、u,\ v,\ wって微妙に見分けつきにくいですね。。。

*1:ベクトルはボールドイタリックにしたいのですが、はてなでの書き方が分かりませんでした…

*2:図と本文で書体が違いますが、ご了承ください

*3:この性質は、3次元の反射でも成り立ちます。例えばAOJ 1289では同じ方法により、3次元球面上での反射を考えることができます。

*4:係数は0になることもあるので、必ずしも4次方程式であるとは限りません。

*5:ただし、ベアストウ法は数値計算的な手法のため、誤差が生じます。以後の計算では、これにより生じうる誤差より大きな値をEPSとして用いる必要があります。

*6:誤差の影響で、x=1.00000000001などの値が解として得られる可能性があります。そのため、xの絶対値が1に極めて近い値については、1または-1として扱う必要があります。 また、やや乱暴ですが、x>1であればx=1として、x<-1であればx=-1として、それぞれ扱うこともできます。このようにしたとしても、反射のチェックで除外されるため、最終的な結果には影響を与えません。

*7:正確には、誤差を考慮するため、「外積の絶対値がEPS未満」という判定にする必要があります。