2019-02-26

AtCoder Grand Contest 020：B - Ice Rink Game

問題

https://atcoder.jp/contests/agc020/tasks/agc020_b

考え方

考えていたこと

ナイーブに考えると $i$ 回目のラウンド前にいた人数を $x$ とするとラウンド後は $f_{i}(x) = x - x\ mod\ k_i$ となることは分かる。1 回目のラウンド前にいる人数を $N$ として $f$ を順に $k$ 回適応すると最終的な人数が決まる。 $k$ 回適応したときの結果を $g(N) = f_{k}(f_{k-1}(\cdots f_{1}(x) \cdots ))$ とすると求めるべき解は $g(N)=2$ を満たす最小/最大の $N$ となる。

$N$ はある区間上に存在することになるから二分探索で求められる... と考えたが、単純に評価関数を $g(N)=2$ であるかどうかとする二分探索はできない。区間であるから条件を満たさない区切りが区間の大きい場合と小さい場合の $2$ 種類存在するためである。

三分探索とかいけるか？と思ったけど、仮に条件を満たす区間の値を $-1$ としてそうでない区間の値を $0$ とすると、そうでない区間がすべて $0$ になるので正しく区間を絞ることができないのでダメである。

解説見た

$g(N) \ge 2 \land g(N) \le 2 \Leftrightarrow g(N)=2$ を用いることになる。

直感的には $g(N)$ に単調性があると想定できるが、単調性がわからないと以下の評価関数を定義することができなさそう。一応示すと以下のようになる。

$f_p(x+1)-f_p(x) = (x+1 - (x+1)\ mod\ p) - (x - x\ mod\ p) = 1 + (-1) \ mod\ p \ge 0$ であることから $f(x)$ について単調性が示せた。 $g$ は $f$ の合成関数であることから同じく単調性を持つ。

$g$ に単調性があることから以下が言える。

$g(N) \le 2$ なる $N$ については単調であって、ある値 $x$ までは条件を満たし、 $x$ よりも大きい値は条件を満たさない
$g(N) \ge 2$ なる $N$ については単調であって、ある値 $x$ までは条件を満たさず、 $x$ よりも大きい値は条件を満たす

よって、それぞれの最小/最大値が二分探索で求められることになる。

Submission #4388322 - AtCoder Grand Contest 020

どこに着目して考察するべきだったか

評価関数を工夫すると二分探索が適用できるようになる。区間の最小値、最大値を二分探索で求めたいときには応用できるかもしれない。

何がバグっていたか

得た知見(典型ポイント)

二分探索の評価関数を工夫する
ある値x以下かつある値以上はある値

類題

2019-02-25

AtCoder Grand Contest 006：B - Median Pyramid Easy

問題

https://atcoder.jp/contests/agc007/tasks/agc007_b

考え方

$x = 1, x = 2*n-1$ の場合は中央値になりえないので必ず NO になる。そうでない場合、例えば $N=4, x=2$ の場合は可能かどうかというと可能である。 $O(N!)$ で実験すると容易に分かる。

上の段の中央値になる場合の条件について考えていこう。

1列目	2列目	3列目
-	`2`	-
`*`	`*`	`*`

まず上の段で 2 になる場合は、必ず下の段(簡略のためにソート後としておく)の真ん中の値は 2 になる。そうでない場合は上の段の中央値になりえない。また少なくとも 1 つは 2 以下の数になっていて、少なくとも 1 つは 2 以上の数になっている。

このように構築すると上の段の真ん中の値は 2 になって、上の段の真ん中左の値は 2 以下の数になる。上の段の真ん中右の値は 2 以上の数になっている。よって最終的には 2 が一番上の数になる。

つまり、構築する数列を $\{a_N\}$ とし、一番下の段の中央の index を $k$ とすると $a_k = x, a_{k-1} = x-1, a_{k+1} = x+1$ が必要条件である。十分条件ではない(一番上の数が $x$ だからといって $a_k = x, a_{k-1} = x-1, a_{k+1} = x+1$ が満たされるわけではない。一番下の関係ないマスは任意に埋めていくだけでOK。

Submission #4383041 - AtCoder Grand Contest 007

どこに着目して考察するべきだったか

実験をする。必要条件を考える。

何がバグっていたか

得た知見(典型ポイント)

類題

2019-02-25

AtCoder Grand Contest 007：B - Construct Sequences

問題

https://atcoder.jp/contests/agc007/tasks/agc007_b

考え方

えー、難しい...

$N$ の順列 $p_i$ の順番になるように $a_{p_i}+b_{p_i}$ を構築する。その際に $\{a_N\}$ は単調増加で $\{b_N\}$ は単調減少になるようにする必要がある。

いろいろな条件をいっぺんに考えることが難しいときは、ひとつずつ考えていくのがよさそう。

まずは $\{b_N\}$ は忘れて、 $\{a_N\}$ だけで条件を満たす数列を構築するとしよう。 $a_{p_1}=1, a_{p_2}=2, \cdots, a_{p_n}=n+1$ としておく。これは $b_{p_i}=0$ とすると $a_{p_i}+b_{p_i}$ が単調増加であることを満たす。数列の項がすべて $a_i \ge 0$ または $a_i \le 0$ である数列の累積和をとると単調性が満たされるので累積和をとることを考えよう。そうすると $\{a_N\}$ について単調増加になる。

さて累積和を取る過程の $a_{i+1} = a_i + a_{i+1}$ をする際に $a_{i+1}$ に足す分の $a_i$ を $b_{i+1}$ から引くことにする、つまり $b_{i+1} = -a_i$ とすると $a_{i+1} + b_{i+1} = a_i + a_{i+1} -a_i = a_{i+1}$ となって $a_{i+1} + b_{i+1}$ は $a_{i+1}$ によって定まることがわかる。したがって $b_{i+1} = -a_i$ とした $\{b_N\}$ を仮定しても $a_{p_i}+b_{p_i}$ は単調増加であることに変わりがない。具体的には最初に構築した $a_{p_1}=1, a_{p_2}=2, \cdots, a_{p_n}=n+1$ が保たれる。

$\{b_N\}$ について考えよう。 $b_{i+1} = -a_i$ であることから $\{b_N\}$ はすでに単調減少になっていることが分かる。ただし $\{b_N\}$ は $b_i \lt 0$ になりうる。構築すべき数列は $1 \le a_i, b_i \le 10^9$ であるので、 $|min(b_i)|+1$ を $\{b_N\}$ に一様に足すことで数列の大小関係を維持したまま、 $b_i \gt 0$ とすることができる。

よって上記のような手順で数列 $\{a_N\}, \{b_N\}$ を構築すると解が求められることになる。

Submission #4383041 - AtCoder Grand Contest 007

どこに着目して考察するべきだったか

差分をキャンセルするという考えにいたると解けるかもしれない...

何がバグっていたか

得た知見(典型ポイント)

類題

D - Non-decreasing 数列の累積和に一様に値を足す考えは似ています。

2019-02-25

AtCoder Beginner Contest 119：D - Lazy Faith

問題

https://atcoder.jp/contests/abc119/tasks/abc119_d

考え方

各クエリに対して $O(logN)$ ないしは $O(1)$ で答えないといけない。神社用と寺用のTreeSet(二分探索木)に各 $s_i, t_i$ をあらかじめ入れておけばクエリごとにある位置 $x_j$ に対して左右にある最短の神社と寺の位置を求めることができる。

あとは神社と寺を訪問するパターンを網羅すれば最短距離を求めることができる。右の神社→左の寺...など全 $8$ パターンある。

Submission #4380845 - AtCoder Beginner Contest 119

実装テクとしては右端と左端に番兵 ( $-2^{60}, 2^{60}$ ) 程度の値を入れてしまうのが楽。

どこに着目して考察するべきだったか

何がバグっていたか

得た知見(典型ポイント)

類題

2019-02-24

AtCoder Grand Contest 004：B - Colorful Slimes

問題

https://atcoder.jp/contests/agc004/tasks/agc004_b

考え方

典型っぽい。ある変数を固定すると、最適な操作が見えてくる問題。

何を固定するか？

最小の秒数を $x$ 秒として二分探索
- 「 $x$ 秒で全色のスライムを集めることができるか？」というYes/No問題に切り替える
- しかし、結局最適なスライムの集め方の考察が必要で問題が進んでいない
魔法の回数を $k$ とする
- あるスライム $i$ を集めるときの最小のコストは $min\{a_{i-k}, a_{i-k+1}, \cdots, a_{i}\}$ で求められることになる
- 各スライムについて、上記の方法で最小コストを求めれば解ける

よって上記から魔法の回数を $k$ 回使うとすると、各スライムを集める秒数の最小値を求められることになる。区間 $[i-k,i]$ の秒数の最小値はセグメントツリーを用いることができるし、 $k$ の小さい値から考えることで自然に求めることもできる。セグメントツリーを使った場合は計算量は $O(N^2\ logN)$ となる。

どこに着目して考察するべきだったか

魔法の回数を固定しないとはじまらない。

何がバグっていたか

得た知見(典型ポイント)

ある変数を固定して考える

類題

2019-02-24

AtCoder Grand Contest 005：B - Minimum Sum

問題

考え方

式だけみるとぱっと何を求められているかわからないので、まずはナイーブに $O(N^3)$ の実装で実験してみる。そうすると区間の数について最小になる要素を求めて、その総和を求める問題であることが分かる。

さて、区間の数をまとめて計算したい。「最小値が $i$ になる区間が数列上にいくつ存在するか？」という問題を考える。これが高速に求められれば $i$ と区間の数 $cnt$ を掛けて、その総和を計算すれば良い。

サンプル3を例に考える。数列は以下のように与えられている。1-indexed で考えていくことにする。番兵として一番右と左に -1 があることにする。

8
-1 5 4 8 1 2 6 7 3 -1

このとき数列の要素 $2$ が最小値になる開区間の左端と右端の index はどこになるか、というと左端の値は $a_4=1$ で $4$ 、右端は $a_9 = -1$ で $9$ となる。 $a_5=2$ であるから、区間の左端の候補の数は $5-4$ で右端の候補は $9-5$ である。よって $(5-4) * (9-5) = 4$ 個の区間で最小値が $2$ になることが分かる。

ある値 $k$ を考えたときに $k$ 未満の要素の右端の最大の index と左端の最小の index を求める必要がある。これは値の小さい値から数列上の index を TreeSet に含めていくようにして求めていくと、求める前には必ず今考えようとしている $k$ よりも小さい数の index しか TreeSet 上に存在しないので左端と右端の index が $O(logN)$ で求められることになる。

Submission #4362828 - AtCoder Grand Contest 005

どこに着目して考察するべきだったか

小さい値から考えていくことで候補の index が高速に求められることに気づく必要がある。

何がバグっていたか

得た知見(典型ポイント)

小さい値から貪欲

類題

2019-02-23

yukicoder：No.794 チーム戦

問題

https://yukicoder.me/problems/no/794

考え方

きれいな問題で好き。 $\{A_N\}$ はソートしても問題がないのでソートする。マッチングする際に $A_i$ が大きい値ほど候補になる相手が厳しく、候補が絞られるので $A_i$ が大きい値から考えていく。

サンプル1 の場合ソート後の数列で考えると以下のようになっていて

4 6
1 2 3 4

$a_3(0-indexed)$ の候補になれる数は $a_1=2$ までである。

$i$ 番目について考える時、候補の相手は二分探索で求めることができる。 $[0, i-1]$ の範囲に対して $K-a_i$ 以下の最大の要素のindex $j$ を求めれば良い。 $N$ は偶数なので、 $\displaystyle \frac{N}{2}$ ペアを作れば良い。二分探索する回数は $\displaystyle \frac{N}{2}$ である。また後ろから考えて、すでに $cnt$ 人ペアを作っている時で $i$ 番目について考える時、その候補に含まれる数のうち、 $cnt$ 人はすでにペアになっているので候補の対象にはなりえない。よって、 $cnt$ 分は候補の数から差し引く。