ブラウザで動くゲームを作っているのだが、全画面APIというものがあるのを初めて把握した。スマホだと画面に対してアドレスバーとかが占める面積が多くて没入感が削がれるなあ…と思っていたのだが、スマホでも動くことを確認した。素晴らしい。

---

ARC159に出た。

A: MOD Nで同じ頂点はほぼほぼ同じ扱いで良い。最初にワーシャルフロイドしてsi MOD Nとti MOD Nの距離を見ればよい。si MOD N=ti MOD Nのときは、si=tiならば距離は0だしsi≠tiならば距離は行って戻ってくるときの距離になるが、この問題ではsi≠tiが保証されているのでそこの場合分けはしなくてよい。

B: gcdが等しい場合を一気に処理したくなる。g=gcd(a,b), a=ga’, b=gb’とおく。一般性を失わずb’>a’とする。

gcd(a’-k,b’-k)≠1となる最小の正整数kを求めればその回数まとめて引くことが出来る。全探索では間に合わない。細かい証明は省くが、頑張って考えるとkはb’-a’の約数であることが分かるので約数全探索すればよい。kを求めてa,bそれぞれからgkを差し引く。これを繰り返せば解ける。

あとは同じgcdを一気に処理するのが何回程度で済むかという話だが、このアルゴリズムを考えるとgは少なくとも1回に2倍以上ずつ増えていくため、$O(\log max(a,b))$回で終了する。約数全探索部を考慮しても$O(\sqrt{\max(a,b)}\log \max(a,b))$なので間に合う。

C: 分からず。一回の操作で増える総和はN(N+1)/2で一定のはずであり、すべてのAの値が等しければAの総和はNの倍数になるはずなので、最初のAの総和にN(N+1)/2の倍数を足してNの倍数にならないならば不可能だということは分かる。そこから先は分からない。

D: [Li, Ri]という連続部のどこかを採用するなら連続部の最後まで採用しても損はない。後ろにより大きい値まで伸びる連続部があるならばそちらへ遷移できるし、後ろにそのような部分がないなら現在の連続部で最後まで採用するのが最良だからだ。これを考えると連続部の端点における状態のみ考えればよいことが分かる。普通のLISのアルゴリズムをちょっと工夫する。

Li未満の値から遷移するとき、これは単純にLi未満で終える単調増加列の中で長さが最大となるところから遷移すればよい。DP[Ri]←max(DP[Ri], DP[x]+Ri-Li+1)

[Li, Ri]の値から遷移するとき、このときも最終的なRi地点における単調増加列の長さを最大化したいことは変わらないが、ちょっと事情が変わる。仮にDP[x]から遷移したとするとき、このように遷移しなければならない。

DP[Ri]←max(DP[Ri], DP[x]+Ri-x)

このような式になるため、これを最大化するには、DP[x]が最大な場所ではなくDP[x]-xが最大な場所を取ってくる必要がある。ここに気を付ければ解ける。

本質的な考察はほぼ完ぺきだったのだが、細かい実装でミスりまくっていてWAを何度も出し、結局通せなかった。ランダムケースによるテストをしたらすぐに撃墜ケースが見つかったので本当にダメ。

ランダムテストが突破口になるのは何度も何度も身に染みているはずなのに今回もできなかった。今度テスト用のライブラリを作ることにする。