90:55 + 1ペナ 6完
実装重いの多い割に頑張ったかなと思っていたら、G通されすぎてて詰んだ
A When?
もうちょっと複雑なら時間を分に変換して、60x24であまりを取る方針にするんですが、100分しかないので21時か22時かで場合分けすればよいです
(AC 2:40)
B Number Box
誤読でちょっと荒れてた印象、そんなにわかりづらくはないと思うんですが
始点を決めて、動く方向を全探索すればよいです
動く方向は手打ちしてもいいけど、x,yそれぞれ-1~1でループを回すと簡潔に書けるかも？
(AC 8:03)
C Rotation
今回もド典型
今の文字列ではどこが先頭か？を保持しておけば、あとはそこから何個進んだか？を簡単に計算できます
どこが先頭か？となるのもN回以上操作をすると結局元に戻るので、Nで割ったあまりで管理すればよいです
(AC 12:24)
D Trophy
こっちもド典型
2回目以降のクリアをするならば、Biが短いものを選ぶのが最善です
ということで、iまでみたときのBiの最短は何分か？という情報を管理します
そうすると、iまでクリアするとしたときの最短時間は
1~iまでの1回目のクリアにかかる時間(Ai + Bi) + (最短のBi x 残り回数)
となるので、これをそれぞれ見ていって最短時間を見つければよいです
残り回数が負にならないように一応気をつけます
(AC 16:28)
E Packaging Potatos
えーーー、めちゃくちゃ難しいというか時間がかかると思います
最近のEだと段違いにきつく感じた
まず、ポテトの箱詰めをiからはじめたときに何個になるか？を計算しましょう
これだけでも1問分の重さはある気がしますが...
まず、上限の重さX > N個のポテトの重さの総和であれば、あらかじめN個分をまとめて足しておきましょう
足す回数は X / sum(W0 ~ WN-1)になります
こうすると、あと何個必要か？という問いの答えがN未満になります(あらかじめ足した分を除く)
残り必要な個数は、まだ箱に入れられる重さをVとして
V ≦ sum(Wi ~ Wi+k)
となる最小のk-1となります
これは、累積和の配列を持っておくことで二分探索で計算できます
こういう循環するタイプは配列を2周分確保しておくと実装が楽なことが多いです
もうここで終わっちゃだめですか？？？
さて、iから始めたときに箱に入るポテトの個数がわかりました
問題に答えるためには、K回目の箱はどこからスタートするか？がわかればよいです
K=1のときは先ほどの答えを利用すると、すぐにわかります
たとえばN=3で、0から始めたときに入れる個数が5であれば
5 %3 = 2からスタートします
同様に考えると、aからスタートしたら次はbから始まるという関係がわかり、これを有向グラフの形で表すことができます(a -> bの辺を貼る)
問題は0からはじめて辺をK回通ったらどこにたどりつくか？と言い換えられます
この手の問題にはダブリングが有効です(ダブリング知らない人は調べてみましょう)
なので、先ほど求めた情報を使ってダブリングテーブルを構築すると、各クエリにO(logKmax)で答えられて十分高速です
はーー疲れた、やること多すぎませんか？
(AC 53:19)
F Main Street
こういうの結構すき
まず問題を見て、各クエリO(1)ないしはO(log なんとか)じゃないと間に合わなそうと思います
動き方はたくさんあるようにみえますが、あんまり適当に動くのはよくないので最適なパターンは結構絞られるはずです
具体的には、
1. そのまま直行する
2. いったん大通りに出る
の2つが考えられます
1はいいとして、2を考えると「大通りに出る前にどこか無駄な動きをする」というのは明らかによくなさそうなので、大通りには直行することにします
こうすると、調べる点は(sx,sy)から
左の大通り、右の大通り、上の大通り、下の大通り
に直行した時の点4つだけになります
(gx,gy)のときも同様です
あとは、s,gそれぞれについて、どの点を通るか？を全探索すれば4x4で十分高速です
とやってみると、サンプルが微妙に違います
こういうサンプルからデバッグするときのコツ？なんですが、
「サンプルとの大小比較」はかなり大事です
もし、サンプルより大きいなら実は速く行けるパターン(もっと考慮しないといけない点)を忘れていることが考えられます
もし、サンプルより小さいなら最適に見える方法ができないことがあると考えられます
そうやってみると、サンプルより小さな値が出ているので、実は最適にできないパターンがあるんだろうと思ってデバッグをします
すると、大通りの点から大通りの点に向かうときに直行できない(大通りじゃないところを横切ってしまう)パターンを見つけたので、そこを場合分けして修正します
場合分けもそんなに丁寧にする必要はなくて、大通りだけを通るなら上下左右どこかの大通り同士の交点を通ることになるので、それを全探索しました
ここを直すとサンプルも合うので投げると無事AC！
(AC 85:55)
G Triangle
Fまでやってよしよしと思っていると、謎にめちゃくちゃ通されていて困ります
O(N^2)で解けないか考えて、「こんだけ通されているということは蟻本か？既出か？」とか思って探しますが、とくに見つからず悲しくなります
仕方がないので、残り5分で愚直を書いて投げます
......が、最後の方で落とされます
いやー詰める時間なかったなー、あとで考えるかと思ってコンテストが終わります
想定bitsetと聞いて、そんなのあったなーとなるのでどうせ解けてないんですが、ちょっと高速化すると愚直が通るのでしょんぼりします
最後まで粘っとくべきだったな～～
(AC コンテスト後)
総括
FとGの点数逆にしませんか？
