[問題]

平面上の整数座標にN個の出発点と、N個の目標点があり、全ての出発点を目標点に移動させる

。そのために、塔が３個ある。塔を使うと、全ての頂点を塔の反対側に移動させる。(塔を中心として全ての頂点を180度回転させる。)　塔は何回使っても良い。

移動が可能なら"possible"、不可能なら"impossible"を返す。

1≤N≤50

-1,000,000≤x,y≤1,000,000

[解法](終了後)

ある点から、頂点を２回使った後の移動先を考える。

f:id:yoshiokatsuneo:20150115010718p:plain

上記の図で、黒い点が塔、青い点がある点の移動とする。

２回移動すると、黄色い線を使った三角形と、赤い線を使った三角形は相似形で２倍の大きになる(黄色と赤は平行線)。つまり、ある点について２回移動すると、３つの塔が作る三角形の線分の２倍移動できることになる。

そのため、2n回移動した後の点は以下のような塔３個三角形の２倍の三角形の組み合わせになる。(ちょっとずれてるけど。)

f:id:yoshiokatsuneo:20150115011612p:plain

この三角形たちの頂点のいずれかであれば2n回後に移動できる。

頂点かどうかは、三角形のうち二片のベクトルが作る座標を、直行座標に変換して整数かどうかで確認する。これは、２片によるアフィン変換の逆行列から計算する。

２片が平行な場合(行列式が0の場合)、GCDの倍数かどうかで判定する。

頂点は複数あるので、目標点の全てについて、移動した場合に全ての頂点を相似形で移動できるか確認する。

これで2n回後に目標点に行けるかどうかが判定できる。

2n+1回後は、3つの塔のいずれかでの反転先が座標上にあるかで判定する。

[コード](C++)

[感想]

上は説明になっているのだろうか。。。

平行な場合を考えたり、longlongにしたり、などを含めて時間内に動くコードを書くのは難しかった。

2015-01-15

SRM 645 Div1 Easy JanuszTheBusinessman

TopCoder Statistics - Problem Statement

[問題]

365日の中に、重なるかもしれないN個の区間がある。いくつかの区間を選び、すべての区間が選択した区間と重なるようにしたい。最小でいくつの区間を選べばよいか？

2≤N≤50

[解答](後で)

区間を終了日順でソートして未決定区間とする。

未決定区間の中の最初の区間と交わる区間の中で、(未決定区間以外を含む全ての区間から)終了日が一番遅いものを選択する。選択した区間と交わるものを未決定区間から省く。

これを未決定区間がなくなるまで繰り返す。

[コード](C++)

[感想]

本番は「(未決定区間以外を含む全ての区間から)終了日が一番遅いもの」の所を「(未決定区間の中での)終了日の一番遅いもの」としてしまい失敗。注意不足。。。

けど、失敗した人が多かったようで、レーティングはあまり下がらず。

2014-12-19

SRM642 Div1 Medium TaroCutting

競技プログラミング C++ TopCoder

TopCoder Statistics - Problem Statement

[問題]

N本の木とD本のカッターがある。木は最初height[i]で1日にadd[i]のびていく。カッターは木の高さをdevice[i]丁度にすることができる。

各カッターは、1日に一回だけ使うことができる。

time日後、最小の木の高さの合計はどれぐらいか?

[解答](C++, 後で)

それぞれの木については、高々１回切ればいいので、木の高さの合計をコスト、流量(切った数と切らない木の合計)Nの最小費用流で計算する。

カッターはそれぞれの日に一度だけ使えるので、STARTからD * time個の頂点にコスト0、流量1の辺を張る。そこから、N本の木に対応する頂点まで更にコストdevice[i]+(time-i-1)*add[i]、流量1の辺をはる。カッターを使わない場合のため、STARTからN本の木までコストheight[i]+time*add[i]、流量1の辺も張る。木からSINKまでコスト0、流量1の辺を張る。

さらに、計算量を減らすため、カッターをdeviceでソートし、カッターiからカッターi+1にコスト(device[i]-device[i+1])(負の数だけど先の頂点はそれより大きい辺しかこないのでDijkstraでもOK)、流量Dの辺をはり、カッターから木の辺はそのカッターでしか切れない範囲までの辺にする。

[コード]

[感想]

テストケースによっては計算時間が1.9秒程度なので、ぎりぎり。。。