AOJ埋め11

AOJ

1999年のセット．例年のセットに比べ簡単な問題ばかりが並ぶ．
俺TUEEEEEできて気持ちいい．

1208 Rational Irrationals

候補となる数を全部試すと1億〜5000万通りくらいあるしたぶんTLEなので工夫する．
下限について． u/v<√p ⇔ u^2<pv^2 なので，分母vを固定して考えると，pv^2を超えない最小のu^2を求めればいいことになる．
これには，map<int,int> mp に mp[j*j]=j を入れておいて，mpに対してlower_boundをかければそのようなuが得られることになる．
これを各vについて考えればよい．上限についても同様．

1209 Square Coins

典型的なおつりの払い方DP．

1210 Die Game

top,north,westの値を保持して書くだけ．

1211 Trapezoids

形が台形であるというのがポイント．
台形なので，dfsで台形の上底の長さ，下底の長さ，高さが分かればあとは台形の面積っぽい式で台形の面積が求まる．

1212 Mirror Illusion

点をx,yに0.25ドットずつ動かしながらシミュレートする．座標を100倍しておくとやりやすい．
幾何ライブラリとかは用いなくていいと思う．

1213 Heavenly Jewels

凸カットして面積求めるだけ．
最初宝石が整数座標にしか落ちないと勘違いしてて面倒くさいなぁとおもってたのだけどよくみたら落ちる確率はどの点でも一様であるとか書いててなにこれーみたいな．

1214 Walking Ant

BFS．

1215 Co-occurrence Search

入力，出力が面倒．というか形式がよく分からん．
データセット自体は2つの文字列だけからなるのだけど，一続きの文字列でも72文字を超えていたらわざわざご親切に改行で区切ってくれていることに注意．
最短のsubstringを求めるには，まずsubstringの左端となる位置posを固定する．そこで，それぞれの含有したい文字に対し，posの位置に現れるものでもっとも早く現れる位置を探す．そのような位置でもっとも大きいものが左端posに対する最小の右端となる．
右端を探すにはsetのlower_boundを使えばいい．

2202 Canal: Water Going Up and Down

この前の国内模擬予選の問題．シミュレーション… と見せかけてDPな嫌な問題．
問題文が長い上にそこそこ難解なので頑張って読まないといけない．
位置p，船nに対して

  • dpIN[p][n]:=nがpに入ってくる時間
  • dpOUT[p][n]:=nがpから出ていく時間
  • alv[p][n]:=nがpの位置にある閘門から出て行く時間

などとすると漸化式が立てられるのでそれでDPする．これを本番中に思いついたチームはすごいと思う…．
番兵として，n=0の船は最初から無限遠までいってしまっているなどと仮定するとやりやすいかもしれない．
はまった点としては，入力値でUD=1のときはF,Dの値をスワップするだけでいいのかと思いきや，「最初閘門の水位は東西のうち低い方の水位に合わされている」とあるので，開始直度のこれらの閘門は「待ち」の状態にあることに気をつける．これのせいで1時間くらい悩んでしまった．不毛．


配列の確保が不足してWA出したりしちゃったけどすぐに直してAC．