naoya_t@hatenablog

いわゆるチラシノウラであります

CodeChef June Challenge 2017

f:id:n4_t:20170613182755j:plain
今月のLong Challenge (6/2〜6/12)
途中の数日間(6/5〜8)だけ参加。
694.98973点・282位でレーティングも割と上がって (1634→1843) 4★

Long Challengeへの参加は2度目。前回が昨年の12月。
2時間半とか3時間で終わるコンテストと違って、(解けるか解けないかは別として)問題をひと通り読んで、空き時間に適当に参加できるのがいい。
ちゃんと考えて、いろいろ工夫しないとlargeが通らないように問題が出来てるし、考えるのが楽しかった。

A Good Set (GOODSET) 8285 / 46.83%

https://www.codechef.com/JUNE17/problems/GOODSET

最初の2つを例えば {1, 2} と決めて
(※n=1なら{1}だけ返せばいい)
要素2つを選んだ和の全てを set<int> に放り込んでいって
そこにない最小の数字を選んでいく
(small (n\le10) だけなら何も考えずに1,2,4,8,16,32,... みたいなのを返せばいい。これは500までの数しか選べないlargeでは使えない手だが)

Xenny and Coin Rankings (XENRANK) 7182 / 38.5%

https://www.codechef.com/JUNE17/problems/XENRANK

座標 (x, y) のコインのランクは
s=x+y とおくと\displaystyle\frac{s(s+1)}2+(x+1)で表せる
(0,0)..(U,V) の長方形で一番ランクが高いのは右上の角 (U, V)
これをあてはめるだけ

Triplets solved (SUMQ) 3316 / 7.26%

https://www.codechef.com/JUNE17/problems/SUMQ

yそれぞれについて、y>x_i,y>z_jx_i, z_j だけの (y+x_i)(y+z_j) を求めて足したやつを求める
(y+x_1)(y+z_1) + (y+x_1)(y+z_2) + ... + (y+x_N)(y+z_N)
= \displaystyle(\sum_i{y+x_i})(\sum_j{y+z_j})
= \displaystyle(|x|y+\sum_i{x_i})(|z|y+\sum_j{z_j})
ここで |x|, |z| は それぞれ、y以下のx_i, z_iの総数。→二分探索でO(\log p), O(\log r)
\displaystyle\sum_i{x_i}, \sum_j{z_j} はそれぞれ、y以下のx_i, z_jの合計。
→accumulateしておけばO(1)
これのy個分なので O(q(\log p+\log r))とか
余裕っしょ、と思ったらWA:accumulate部分でvector<long long>にしたのはいいんだけど1e9+7でmodしたやつじゃなくて生値を入れてたせいでオーバーフロー。そこだけ直してAC

Chef and the Feast (NEO01) 4612 / 15.45%

https://www.codechef.com/JUNE17/problems/NEO01

・非負スコアのものはできるだけまとめたい
・負のスコアのものは個別に食べる
いや、負のものでも非負組に入れていい場合があるのでは。
例えば、[-1, 2] は個別に食べると -1\cdot1+2\cdot1=+1 だけど
2つまとめて食べると (-1+2)\cdot2=+2 になるんだよね
ソートしといて、(0以上の和) ✕ (0以上の個数)、から始めて
負のやつを1つずつ取り込んだ場合のスコアを見ていくか。
あとは
・スコアはaccumulateした配列を用意しておく
という程度
→AC

Pairwise union of sets solved (UNIONSET) 3351 / 18.24%

https://www.codechef.com/JUNE17/problems/UNIONSET

bitset<2500> に入れて総当りunionして愚直にカウント
→smallはOK。largeでTLE

cinが遅い?と思ってvector<int>読み込み用自作ルーチンに差し替えて少しスピードアップ
しかしTLEが続く

O(KN^2)
最悪ケースのサンプルを作ろうとしてて思ったんだけど
\displaystyle\sum{len_i} \le10000 ってことは、例えばN=2500のとき、len_1=2500, len_2=2500, len_3=2500, で残り2500 を (4,1,1,1,...,1) みたいにしか分けられない
ってことは、len_i + len_j  \ge kのケースだけunionを計算(O(K^2))する、みたいな枝刈りが結構効くのでは?→その通り
→AC

Chef and Prime Queries (PRMQ) 1042 / 3.99%

https://www.codechef.com/JUNE17/problems/PRMQ

\displaystyle a_i=\prod{{p_k}^{e_ik}}としたとき、
\displaystyle\prod_{i=l}^r{a_i}=\prod{p_k^{\sum{e_ik}}}について、[x,y]の範囲の素数p_kの指数e_ikの総和を求めたい。

エラトステネスの篩で100万までの素数表を用意。(P=|primes|=78498)
そしてとりあえず各 a_i素因数分解
\displaystyle A_{nk}=\sum_{i=0}^n{\sum_1^k{e_ik}} をあらかじめ計算しておく。
テーブルAのサイズは78498×Nになるが、N=1000まで(Subtask #1,#2)なら行けるだろう。

各クエリ (l,r,x,y)。
x,yについて、何番目から何番目の素数にあたるか (u, vとする)を素数表から二分探索で調べる(\log P)。あとは A_{rv}-A_{ru}-A_{lv}+A_{lu}O(1) で引けるので、クエリQ回で O(Q\log N)。N=1000でも(100000でも)大丈夫だろう。

これでSubtask #2までは行けるのだけれど。
1\le N,Q\le 10^5 になるSubtask #3はこれでは解けない。
(テーブルAの要素数が7.8e9になるので時間もメモリも足りない)

クエリを先に読んでおいてテーブルAの必要な箇所だけ保存したとしても、メモリは節約できるがかかる時間は短縮できない…
というか、何ができれば間に合うんだ?
ある範囲に含まれる全ての素数についてその指数(というかその合計)が分かればいい
累積テーブルを作る以外にどうしたら?


segment treeの使い時では?

a番目の素数からb番目の素数について、その指数の合計を得たい。
配列のa番目からb番目の合計を得られればいいわけで、素数であることは忘れていい。
a_i素因数分解して素因数 p_k とその指数 e_{ik} を得るたびに、segment tree の該当箇所(それが何番目の素数か)を +=e_{ik} していく。

クエリq(l,r,x,y)A_{rv}-A_{ru}-A_{lv}+A_{lu} の4要素に分解。クエリqの答えをans_qに格納するとして、ans_l=ans_l+A_{lu}, ans_i=ans_i-A_{lv}, ans_r=ans_r-A_{ru}, ans_r=ans_r+A_{rv} はそれぞれ独立に行っても良いので、素因数分解a_l, a_r の位置まで進んだ時にそれぞれ行えば A_{nk} のテーブルも作らなくて良くなる。
A_{nk} は具体的には、A_0からA_nまでを素因数分解した結果の(各素数ごとの指数の合計)を収めたsegment treeから、u番目からv番目までの素数について指数の総和を計算したもの。
→large通った

segment treeの使い所を見つけて実際に問題が解けたことで、何というか、レベルが1上がったような気がした。

Saboteur (Challenge) (SBTR) 368 / 58.92%

https://www.codechef.com/JUNE17/problems/SBTR
チャレンジ問題。(ミニマラソン)

・ノード数の少ないやつ (\le20) は全探索で行ける
・全結合してるやつは高いのを2つだけ残す
・ホイール状のグラフは真ん中を消して残った輪を1箇所切るか、真ん中を残すけど回りの輪は1つ置きに切る(奇数の場合は一箇所注意)
・それ以外はビームサーチ的な何かで、閉路をもたないツリーを紡いで行く

とりあえず1.2秒ぐらい使って得点を確定して(その後何もしてなくて)
これはもうちょっと取れたはず

Cloning partially-solved (CLONEME) 246 / 2.76%

https://www.codechef.com/JUNE17/problems/CLONEME

とりまsmall通して10点;
mediumまでは通せたんだけど(30点)
large(Q=1e5)が解けなかった

ある地点までにどの数が何回使われたか統計をとっていくみたいなのは、制約がゆるいうちは良いけど1e5 x 1e5 では通用しないよね…
てか、ソートした時に1つだけ違っていい、ってどういう事?
..aabdd...
..aacdd...
みたいな、あるいは
..aaadd..
..aaddd..
なんかその辺りから制約を絞って攻めようと考えたけれど解けなかった

Euler Sum unsolved (ES) 100 / 1.4%

https://www.codechef.com/JUNE17/problems/ES

1e100までで50点、1e4000までで更に50点。
\displaystyle\frac{n(n+1)}{e}-\frac{n}{2} あたりに行きそうなんだけど)正確な値をどう求めたらいいか。
その辺りで当てずっぽうに(乱数を加えたりして)何回か通したらテストケース通るかな、みたいなのを眺めてみたけどかすりもせず。

Persistent oak (OAK) 38 / 2.77%

https://www.codechef.com/JUNE17/problems/OAK

・実が成ったときの処理(その枝が落ちなくてもその上流のどこかで落ちるかもしれないから上に辿っていく;落ちたら落ちたでそこから下の負荷がなくなるからその旨上流に知らせたい)。落ちた枝に実が成ったり鳥が止まったりするようなテストケースが来たりしないか心配してた。
・鳥が止まったときの処理(下流の実を全部落として、上流の負荷を解消して)
ってのがちゃんと見切れてなくて(そこに至るまでに)暫く試行錯誤を続けた。

状態がrootに近いほうのクエリ(親)から子クエリをDFSで巡回していくために、クエリを処理するVMと、それ用のコードを吐くコンパイラを書いてた(一応末尾再帰とかしちゃったりして)
最初のケースは通せたんだけど、2番めがSIGABRT出てて、3番目以降TLE。
最悪ケース(キャパシティ最大の枝を10万本直列に繋げた末端で1つずつ実が成ったりとか)で死ぬのは分かる。そこを乗り越えられずに(自分の)持ち時間が終わった。