Overall Editorial
by 
hirayuu_At
ヒント集
各問題の簡単なヒントです。解けないときの参考にしてください。
A - ARC Arc
ヒント1
ARCRARCR... とつなげるのが良さそうです。
ヒント2
\(N=4\) や \(N=8\) の場合を考えてみると、\(N\) が \(4\) の倍数の場合は簡単なことに気付けるはずです。
ヒント3
\(N\) が奇数の場合はどうでしょう。\(A\) の要素がすべて \(0\) のときは厳しそうです。
ヒント4
\(N=7\) のときの ARCRARC や \(N=9\) のときの ARCRARCRA という文字列を考えてみましょう。
ヒント5
円環なので \(A\) をシフトしてもよいことに注意してください。
ヒント6
\(N\) が \(4\) で割って \(2\) 余る場合はどうでしょう。\(A\) の要素がすべて \(0\) だったり、\(A\) に \(1\) が \(1\) つしか含まれていないときは厳しそうです。
ヒント7
\(N\) が \(4\) で割って \(2\) 余る場合に、\(2\) 箇所を除いてすべて \(1\) にできるような文字列は構築できるはずです。いくつかのそのような文字列について、\(1\) にできない場所の特徴を観察しましょう。
B - Fennec VS. Snuke
ヒント1
\(S\) に添字が含まれているような \(A\) の項を区別する必要はないので、\(X=\sum_{i\in S}A_i\) として考察を進めましょう。
ヒント2
ある \(A\) について、\(X=0\) のときに必勝法がある人は \(X=2\) のときも必勝法があります。なぜでしょう。
ヒント3
相手が \(X=0\) のときの必勝法と関係ない部分で \(X\) を減らす操作をしたならば、自分も \(X\) を減らすことで大筋を崩さずに \(X\) を \(2\) 減らせます。
ヒント4
ヒント3の要領で考えると、\(X=0\) または \(X=1\) としてよいことがわかります。
ヒント5
\(A\) の要素についても、偶奇さえ考えれば十分であることがわかります。ここまできたら実験するのが良いでしょう。
C - Range Sums 2
ヒント1
\(P_i=1\) または \(P_i=N\) なる \(i\) を特定するのが楽でしょう。
ヒント2
\(1\) 次元の点の集合が与えられたとき、ある点から最も遠い点は両端の点のどちらかです。これは何を意味するでしょうか。
ヒント3
\(s\) を適当に設定して、すべての \(t\) に対してクエリを送ると、返り値が最も大きいときに \(P_t=1\) または \(P_t=N\) となることがわかります。\(P_t=1\) と仮定しておきましょう。
ヒント4
端の点からは、距離の順番がそのまま点の順番になります。\(P_1\lt P_2\) という制約を無視すれば、\(P\) は特定できそうです。
ヒント5
\(A\) のほとんどの要素は差分を計算すれば特定できるはずです。残りの質問回数を特定できていない \(A\) の要素に使いましょう。
ヒント6
\(P_1\lt P_2\) という制約を考えましょう。以下の \(2\) つの場合にクエリの返り値は必ず等しいですが、なぜでしょうか。
D - Fraction Line
ヒント1
\(f\left(\dfrac{x}{y}\right)\) の特徴を観察しましょう。
ヒント2
素因数ごと独立に考えられそうです。
ヒント3
素因数ごとの答えは比較的単純なDPで計算できそうです。
ヒント4
素因数ごとの答えをまとめあげるには総積をとるだけでよいです。
E - Snuke’s Kyoto Trip
ヒント1
\(0\leq x\leq W\) かつ \(0\leq y\leq H\) なるすべての格子点に区画があり、かつ \((0,0)\) から始めるときの通り数をできるだけ早く求めましょう。
ヒント2
ヒント1で正しい式を見つけている（もしくは知っている）ならば、\(0\leq x\leq W\) かつ \(0\leq y\leq H\) なるすべての格子点に区画がある場合の通り数はその式を変形していくことで求まるはずです。
ヒント3
前計算に \(O(W+H)\) 時間かけるのは前提として、そのあとに \(O(1)\) 時間で処理する必要はありません。
ヒント4
通れない領域の周囲を全探索して、通れない領域を通るものを適切に数えましょう。
posted:
last update: