2016/3 Solved (2)
3/17
3/18
市松模様をイメージしてジグザグに並べていく。
キューに入っていく様子をシミュレーションする。キューに入ったものの先頭と取り出し、実行→その実行が終わる時間よりも先に入ってくるプロセスをindexを進めながらしゃくとり的にキューに入れられるか否かを見ながら押し進めていく。と交互にやっていく
LCMを決め打ちにすれば、その値の約数であるかどうかで各数列の値が要素になりうるかが決まる。数列のそれぞれの値は上限がと大きいが、LCMの上限
は
以下であり、これ以上の値については考える必要が無い。まず数列の値がどれがいくつあるかを配列に保存して数え上げ、その倍数の位置にもそれらを足しあわせてあげれば良い。数字を1つ受け付けるごとにやっていると時間が足りないので、始めに数列全体を受け取ってから、値が大きい方から埋めていくことで正しい物が得られる。後は
以下の部分で最も大きい部分を取り、その数で割り切れるindexを出力すれば良い(submission)。
3/19
後ろから見ていく。まず、全体を見ればk番目に若いのはk位の人である。そこから、今注目している順位の人がkより小さければそれを1増加させる(k番目に若い人が後ろに1つずれる感じ)。そのindexの人がすでに今注目している順位よりも高いところにいるならすでに除外されているはずの人なので、順位の範囲におさまるまで押し進める。なんか一連の流れはしゃくとり的な感じ(submission)。
CF IndiaHacks 2016 - Online Edition (Div. 1 + Div. 2)に参加
ABCの3完。Dはフローだった。要復習。
ARC 049に参加
ABの2完。そろそろARCのC埋めを始めようかなと思った。
3/20
- CODE FESTIVAL 2014 リレー J - Color Game nが小さいケースを試して、こんな感じかな―と思って投げてみたら通った。
3/21
3/22
(サークルの追いコンがあって何もしなかった)
3/23
3/24
(引っ越し準備してて何もしてない)
3/25
(引っ越し準備してて何もしてない)
3/26
全ての桁が一致していて、かつ2数の差が少ないのは10の位と1の位を入れ替えた数であることに注目して、bをL+1~Rまで全探索、そのbに対してaをa>=Lに注意してb-1~b-100の範囲を探してあげれば十分。
各頂点から1つずつ有向辺が出ているので、どの頂点からスタートしても最終的にはループに入ることになる。また、問題設定ではそのターンが終了するごとに判定を行うことになっているが、2つのトークンがKターン後に違う場所にいるのなら、その途中で一緒になっていることは一本道なのでありえない(途中で一緒になったら最後までずっと一緒にいるはずである)。これを利用して、各頂点iからスタートした時にKターン後にどこにいるかを速く求めることが出来る。トークンがたどるルートは、(ループに入る前の部分+)ループの形で構成されているので、剰余を取って計算することが可能。各頂点からKターン後にたどりつく場所が求まったら、それぞれの頂点に対して、どれか１つを選ぶ・選ばないのx+1個の選択肢があるので、それらをかけあわせれば良い。
時間と座標を持ってBFSする。300より先の座標にも進めることを分かってなくて、はまり続けた...
3/27
(引っ越し準備してて何もしてない)
3/28
3/29
3/30
(引っ越し準備してて何もしてない)
3/31
(引っ越し準備してて何もしてない)
