AOJ 2441 : FizzBuzz
大変そう・・・。問題を分割すると、
- ある数字までのFizzBuzz String の長さを高速に計算する
- ↑の数字を[0, s)の間で二分探索
というところまで分かる。
なぜ二分探索が出てくるかというと、
ある数字までのFizzBuzz Stringの長さは単調増加しているから。
FizzBuzz Stringの長さがs以下となる最大の「ある数字」を求めるということ。
ある数字までのFizzBuzz Stringの長さは、ある数字をnとしたとき
O(log n)で求めることができる。
各桁数ごとに、(9999 - 999) * 4というように数えていき、
3の倍数、5の倍数の数だけ引き、15の倍数の数を足し、
3の倍数、5の倍数の数だけ4（len("Fizz"), len("Buzz")）を足す。
終端も同様に行う
（ごちゃごちゃしていますが、関数funcにまとめています）。
これでO(log^2 s)
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2353262#1
1-indexedに少し苦労した。
時間を計ったら1:04:28.42と出た。
こんなものかなあ（もう少し早く解きたい）。
AOJ 1157 : 大玉転がし
Roll-A-Big-Ball | Aizu Online Judge
直方体を直方体の底面を表現する線分4つ（反時計回り）と高さhで表現する。
コースも線分として捉えると、各直方体への距離が求めることができる。
このときの距離を d とすると、h >= d のとき、そこを通過できる最大半径は d になる。
それ以外の場合は以下のようになる。
円に交わっている点は2点しかないので、ここから円を求めることはできない（たぶん）。
そこでrを[0,1000+eps)の範囲で二分探索して円が直方体の頂点(-d, h)を内包する
最小のrを求める（円の中心は(0, r)）。
この操作をすべての直方体に対して行い、
最小のrを出力すればACとなる。
直方体の底面がコースを内包するケース（サンプルケースの最後から2番目）に注意。
内包判定は反時計回りで表現した線分（ベクトル）を用い、全ての線分に対して
点（始点終点それぞれ）が左にあるかどうかを求めればよい。これは外積を使う。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2352942#1
AOJ 1140 : Cleaning Robot
Cleaning Robot | Aizu Online Judge
巡回セールスマンライクな問題。汚れの数が最大10なのでbitDPで解くことが予想できる。
bitDPが分からない場合、以下の資料が大変参考になる。
あらかじめ汚れにインデックスを振っておき、
各汚れ間に何回の移動で到達できるか幅優先探索しておく。
便宜上、ロボットの初期位置も汚れとして扱うと楽。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2352824#1
これに似た問題で、AOJ 0245 Time Sale(タイムセール)がある。
PCK2011予選の問題だけど、こちらの方が難しめなのでオススメ。
AOJ 1176 : 輪番停電計画
Planning Rolling Blackouts | Aizu Online Judge
まず長方形を考えたとき、全体の和 - 長方形内の値の和が
抑制需要になり、s - 抑制需要が予備力となる。
予備力が0より小さいときは、それ以上分割しても結果は同じなので、
遷移する必要はない。
2つに分割したときに小さい方の予備力を取れば、
最大抑制需要に対する予備力が求められる。
愚直にやると無理そうということが分かるけど
状態:値を「長方形:何個の長方形が作れるか」と置くと、
h^2w^2 だけ計算すれば良いことになる
（左上のx, y、右下のx, yと持つ）。
遷移はO(h + w)で行い、あらかじめ長方形内の値の和を
持っておいてO(1)で遷移可能かチェックできるようにする。
メモ化DPで書いて、O(h^2w^2(h + w))
AOJ 2741 : インビジブル
ゲーム系の問題。
困るのはスタックで配列で持っていたりすると解けない。
しかしよく考えてみると「最後に-1を出したのはいつか」
を持てばスタックの状態を表現できる。
（これだけでは不十分で最後にパスしたインデックスを
高速に求められるようにしておく必要があるが
これはTreeMapを使えば実装できる）
memo[turn][pass][index1][index2][block1][block2] :=
turnの手番でpass回パスして
互いのデッキのインデックスが
それぞれindex1, index2で、
相手のデッキのblock1, block2番目の後に
-1のカードが置いてあるときの
自分にとって価値が最大の点数
オーダーはギリギリ大丈夫だけど
これ以上は増やせない。
パスするときは、相手のblockインデックスか、
前にパスしたときの互いのインデックスの
大きいほうを取り出し、今指しているインデックスまで
足していき、点数を計算する。
このとき、点数計算を愚直にやるとさらに
O(n + m)かかってしまうので
あらかじめ累積和を取っておいてO(1)で
求められるようにしておく。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2311971#1
最初誤読していたり、埋め込んだバグを取るのが大変だったりで
解くのに3時間くらいかかりました・・・。半分ぐらいに減らしたい。
でも自力で解けたのは嬉しくて、図書館でやっていたのに
ACしたときはつい大声をあげてしまいました・・・。
Codeforces Round #380 (Div. 2) A B C D
A
めっちゃ実装に時間がかかった。どう書けばスマートか分からない。
ogoにhitしたらgoが続くまでfor文内のindexを増やす方式にしてAC。
B
actorがいないマスで上下左右に一つでもactorがいればカウントアップしていく。
一番最初SegmentTreeを書いてTLEする。
O(mn)で書けることに気づいてAC。
C
コンテスト中は解いている人が少なかったので飛ばした。
どれくらいの容量vがあれば時間内に到達できるか判定したいので、
二分探索だとけっこうすぐに分かった。けどコンテスト中には実装しきれずおわり。
コンテスト後もTLEやWAをたくさんもらった。
一番最初次のスタンドに行くのに最大何km飛ばせるかを知るために二分探索を書いていて
二重の二分探索でTLEになった。logってバカにならないんだなあ。
落ち着いて考えればO(1)で求まることに気づく。
バグを押さえて、FastScannerにすればACできた。
D
0のまとまりを考えた時に、
真ん中真ん中と撃って2分していけば最適だと勘違いする。
pretestで落ちて、一番多く減る分け方を全探索して通すが
System TestでTLEになる。
落ち着いて全探索してACしたケースを見てみると
左からb - 1からbずつ右に向かいながら撃っていけば最適であることが分かる。
でもTLE。1secってなんだよ。
FastScanner、StringBuilderを用いてAC。
Submission #22365076 - Codeforces
2完しかできずレートが落ちました。
悲しい・・・。
青色までの道のりは遠いなあ。
AtCoder Beginner Contest 023 C D
C
図に書いてみると、行と列にどれぐらい点があるか着目すればよさそう。
このとき、
- i行にある点がc[i]個のとき、k-c[i]となる列の中から点そのものでない（クロスしたところ）を数える
- i行にある点がc[i]個のとき、k-c[i]+1となる列の中から点そのものを数える
とすれば解がもとまる。
これを愚直に実装すると部分点がもらえる。
Submission #985894 - AtCoder Beginner Contest 023 | AtCoder
点そのものの数を高速に求めるには、(i行目, j列目の点の数, j)としたデータを
ソートしてバイナリーサーチをすればよい。
counterをlongにするのを忘れずに。
Submission #985917 - AtCoder Beginner Contest 023 | AtCoder
考察メモ
D
二分探索の典型。解を決めるとそのペナルティ内に全部撃ち落とせるかどうかの判定問題になる。
愚直に実装するとO(n^2 log sn) で部分点。
Submission #986020 - AtCoder Beginner Contest 023 | AtCoder
ここで、
h[j] + s[j] * i > mid
は
i = (mid - h[j]) / s[j]
と式変形できる（iは次のタイミングでペナルティを超えるとき）。
これをlistに突っ込んでソートすれば、前から順々に見ていけばいい。
これでO(n log n log sn)。ちょっと危険だけど制限時間は5sec。
Submission #986082 - AtCoder Beginner Contest 023 | AtCoder
昔解けなかった問題が解説も見ずに解けて成長を感じる・・・。
ちょっと嬉しい。
C問題には2015年5月9日（たぶんコンテスト日）にチャレンジしてWAをもらったみたい。
