Codeforces Round #97
Result
444(1WA) / 936 / 1200 / (4WA) / -
36位 2036 -> 2140
A. Replacement
問題
数列が与えられる。この数列の項を一つだけ（必ず）変更して、ソートする。
変更後にそれぞれの位置に来る項の最小値を求めよ。
制約条件
n≦10^5
数列の各項は1以上10^9以下
試行錯誤
最大要素を1にすればいいんじゃないだろうか。
やけに簡単。書いた。送信。
WA.
あ、最大の要素が1だったら2にしないといけない。
訂正。送信。pretest passed.
B. Rectangle and Square
問題
8つの点が与えられる。
それらを4つの点からなる共通しない集合2つに分ける。
そのうち一方が正方形の4頂点になっていて、もう一方が長方形の4頂点になっている（正方形でもよい）ような分け方は存在するか。
存在するならYESおよびその分け方を一通り出力し、そうでないならNOを出力せよ。
制約条件
座標の絶対値は10^4以下
試行錯誤
全通り試すだけなのでは。
next_permutation使って全通り調べるコードを書く。
意外に実装めんどい。
サンプル合わない。
長方形の判定まちがってる。ADはABを90度回転させたものではなくて、
方向だけが90度違う。長さで割らないと。
合った。送信。
今日少し幾何を解いていたのでそこそこ早く書けた（つまったけど）。
C. Zero-One
問題
0と1からなる文字列に対して二人が次のようなゲームをする。
- 手番を交互にもつ
- 手番のプレイヤーは1つ文字を消す
- 残りが2文字になったら終了
- 先手は、残る文字列を最小化し、後手は残る文字列を最大化する
ただし、与えられる文字列には'?'があり、
そこには0または1の好きな文字を当てはめてよい。
結果として残る文字列としてありうるものを全て出力せよ。
制約条件
長さ≦10^5
試行錯誤
先手は0,1があったら1を消す。
後手は0,1があったら0を消す。
じゃあ0,1が複数個ある場合どれを消すのだろう。
一番左から消していくっぽい。
てことは、同数の0,1があった場合01または10が出来て、
そうじゃないときは00か11固定になる。
同数の0,1があったとき、一番右が0と1どっちになりうるかで01ができるか10ができるかが決まる。
nが奇数の場合個数がずれてめんどい……
なんか凄く汚いコードになったけどまあサンプル合ってるので送信。
pretest passed.
D. Cycle
問題
0と1からなるグリッドが与えられる。
このなかで、coolなcycleのうち、最も長さの長いものの長さを求めよ。
coolなcycleとは以下を満たすcycleである。
（辺を共有して）隣接する1からなる折れ線で、
どのcycle上の1も、2つの（同じcycleに属する）1に隣接している。
かつ、内部には1を含まない。
制約条件
幅,高さ≦1000
試行錯誤
グリッドは、1をたどると、ループがいくつかできてて、
その中で一番長いものを選べばいい、のか？
でも内部に1が含まれてるとダメなので、枝分かれがあったらなるべく内側を通りたい。
うーん？
cycleの内側は全部0で埋まっているわけなので、内側の0を塗りつぶしていって、その周がcycleになっているかを見ればよいのでは。
隣接は8方向を見ればよくて、最外周以外で1があったらだめなのはどうなるだろう。
3方向以上で0と隣接してたらダメ？
書いてみよう。
あれ全然答えあわない。あー嘘すぎる、角とか余裕で3つの0と隣接するし。
全部の1が二つの1と連結しているかチェックする。
サンプル合った。
送ってみる。WA.
その後ad-hocに色々修正して送ってみるけど全部WA.
E
読んだけど題意がわからない。
System Test
A,B,C通った。
