Codeforces Round #15（ノーコンテスト）
コンテスト過密月間。
A. Cottage Village
問題
x軸上に、中心がx軸を通り辺のうち二つがx軸に平行な正方形の形をしたコテージが並んでいる。
それぞれのコテージの中心はxi,一辺の長さはaiで与えられる。
今、一辺の長さtのコテージを新しく作りたい。
- 新しく作るコテージの一辺はすでにあるいずれかのコテージの一辺に接する
- 新しく作るコテージの中心はx軸上にある
- コテージ同士が重なりあってはならない
このとき、コテージの作り方は何通りあるか。
既にあるコテージが重なり合っていることはない。
試行錯誤
うん？コテージの中心が整数になるように作る作り方？（←両端が意味不明なのでどうみても誤読）
サーバ落ちで15分くらい後にWA判明。あっれ。
接するようにってことはコテージとコテージの間には最大2通りしか置けないってことかなあ。そんな感じに修正。
WA.
……EPSつけてみる。
よく考えたら新しく作るコテージの中心の座標を整数にしたらサンプルと矛盾するじゃん！
もう一度問題をじっくり読み直す。
新しく作るコテージの中心が整数とは一言も書いてない。
書き直した。送信。
PE.デバッグコード消してなかった。もう今日は全然ダメだな。
送信。AC.
B. Laser
色々とサーバが不安定のよう。というかなんか自分酷すぎ。どうしたんだろう。
問題
一辺1の小正方形が横n個、縦m個並んだ形の長方形のチョコレートがある。
このチョコレートを、ロボットアームにつけられた以下のような二つのレーザーで溶かす。
- 2本のレーザーは最初それぞれどこかの正方形の中央を照射している
- レーザーは別の正方形の中央へ、チョコレートの辺と平行な方向へのみ動ける
- レーザーが小正方形の中に入るとその小正方形の部分が溶ける
- レーザーはアームに固定されていて、アームを動かすと同じように動く
- レーザーがチョコレートの外へ出てはいけない
レーザーの初期位置が与えられるとき、レーザーが溶かすことのできない位置にある小正方形の数を求めよ。
試行錯誤
n,m≦10^9らしい。シミュレートするとダメ。
というか問題文解りにくいなー；
図を描いて考える。両方の角が溶けないのかな？
いや、例えばレーザーが横に広く配置されてると真ん中が溶けなかったりする。
各レーザーの溶かせるチョコレートの数と、両方のレーザーが溶かせるチョコレートの数を求めて足して引いてすればいいんじゃないのか。
書いた。送信。AC.
C. Industrial Nim
問題
n個の山の中に更にそれぞれ小さなmi個の山が入っているような石取りゲームを考える。
mi個の山は1番目がxi個、2番目がxi+1個、... mi番目がxi+mi-1個の石からなっている。
更に、
- 一度に同じ小さな山からは何個石を取り除いても良い
- 石は必ず1つ以上取り除き、石を取れなくなったプレイヤーが負けである
とき、このゲームが先手必勝か後手必勝かを求めよ。
試行錯誤
n≦10^5,
xi,mi≦10^16
はいゲーム来た（死亡）
Nimの必勝法ってどんなんだっけか……
紙に書いて考える。山が1個のときは先手勝ちでー…2個だと、先手と後手が勝つ場合があってー……？？？
15分くらい考えてもよくわからん。
ちょっとまって昔PKUで解いただろNim。昔のコードを探す。あった。
- 各山の個数のビットXORを取って非0なら先手勝ち
- 0なら後手勝ち
らしい。xi,xi+1, ... ,xi+mi-1のXORっていくつだよ。
うん？どうも100くらいまで試してみると
1^2^3^ ... ^n=
- n (n≡0 mod 4)
- 1 (n≡1 mod 4)
- n+1 (n≡2 mod 4)
- 0 (n≡3 mod 4)
ぽい！！なんでだ！！でもn大きくしても反例出ない。
xorは二回行うと0になるので、
xi,xi+1, ... ,xi+mi-1のXORは
(1^2^3^, ... ,^xi-1)^(1^2^3^, ... ,^xi+mi-1)に等しい。お解けた。
書いた。
PE.デバッグコード消してないよアホ！！
修正。AC.ペナルティが酷いことになってる。
D. Map
なんか高速データ構造の問題ぽかったので読んでない。
E. Triangles
解いてる人がDより多いからこっちに取り組んでみよう。
問題
深さnまでの三角形の格子の内部において、格子にそって散歩するときの場合の数をmod 1000000009で求めよ。
散歩道は以下の制約を満たす必要がある。
- 三角形の格子の上の自分の家から出て、正の距離を歩いてまた家へもどる。
- 図の灰色の部分（森が密のところ）は入ることはできない
- 散歩のコースが自分自身と交差してはいけない
図は描けないので略。
試行錯誤
あからさまにDPっぽい？
図を描く。まずは森がない場合を考えよう。
n=2で10通り？なんでだ？あー別に最短距離じゃないこともありうるからか。
難しくないこれ。
よく受験数学とかで直線に関して反転して場合の数を調べるっていう問題あるよな。
そんな感じの解答つくれないだろうか。
自分自身と交差しないっていう条件がよくわからない。
しかも散歩道の複雑な形がかなり考えられる。うーん。難しいなあ。
結局解法まったく思い浮かばず。
