naoya_t@hatenablog

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

CodeChef July Challenge 2017

今月のLong Challenge (7/7〜17)
f:id:n4_t:20170717214702j:plain
https://www.codechef.com/JULY17
強い人たちがTCO17MM3やら何やらで不在の中、845.89933点・46位で6★に昇進。(2077→2239)
オレンジコーダー!


とても自分向きのコンテストだと思う

Whats in the Name (NITIKA; 6920, 38.49%)

https://www.codechef.com/JULY17/problems/NITIKA
// python
小文字化してスペースで切ってそれぞれcapitalizeして
最後以外を s[0] + '.' に変えて
' '.join()
→AC
Solution: 14425808 | CodeChef

Chef and Sign Sequences (CHEFSIGN; 4797, 15.18%)

https://www.codechef.com/JULY17/problems/CHEFSIGN
こういう問題どこかで見たような
→Hackerrankのこれだ:
www.hackerrank.com
"><" のところから攻めていく
priority_queue使ってみた
→AC
Solution: 14428892 | CodeChef

Calculator (CALC; 4397, 16.15%)

https://www.codechef.com/JULY17/problems/CALC
三分探索
→AC
Solution: 14430783 | CodeChef

IPC Trainers (IPCTRAIN; 2309, 12.96%)

https://www.codechef.com/JULY17/problems/IPCTRAIN
誰も1コマも教えない状態からスタートして
priority_queueに毎日新規投入して
より多く悲しむ奴から貪欲に入れていく
→AC
Solution: 14441081 | CodeChef

Tree Expectancy (EXPTREE; 1150, 24.22%)

https://www.codechef.com/JULY17/problems/EXPTREE
メモ化再帰しながらシミュレーションして
ああこれって分母はカタラン数
https://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%BF%E3%83%A9%E3%83%B3%E6%95%B0

分子は二項係数の真ん中の項
https://oeis.org/A000984

剰余演算を駆使して求めようとしたけど
1e3でも結構時間かかる
約分できるのでは
できた
2次/1次
n*(n-1)でオーバーフローw
int128とか?いや
n(n-1) % mod = (n % mod)((n+mod-1) % mod) % mod だ
1e18を10万回やっても1秒に収まるようになった
→AC
Solution: 14465531 | CodeChef

Pishty and tree (PSHTTR; 687, 5.84%)

https://www.codechef.com/JULY17/problems/PSHTTR
xorで距離?いや、必要なとこだけxor取らないといけない
どこか適当なノード(1番でいい)をrootにして、
u→vのxor値は、ROOT→u, ROOT→v のxorと等しいし
c_i値の小さい順に1つずつグラフに足して行って、クエリもKの小さい順にこなしていけば良いのでは
largeの2つ目がTLE (1.5sec)以外はAC
Solution: 14441355 | CodeChef
ああ、ずらっと1列に並んだ場合に死ぬよな

2投目、uとvのLCAで止まるように書き直したけど
やっぱり最後のやつでTLE
Solution: 14441415 | CodeChef
鬼畜か
少しでも速くなるかと思って for (auto p : ...) みたいなのを普通のforループに替えたりしたけどTLEのまま
Solution: 14442621 | CodeChef
後で

再訪

もしかして?と思って、みんな通ってるってことは最悪ケースでも大したことないんじゃね?、rootを0じゃなくてN/2にしたらどうよ、と思って投げたやつが通りやがったwwwww
→AC
Solution: 14450895 | CodeChef

Two Coins (TWOCOINS; 285, 8.95%)

https://www.codechef.com/JULY17/problems/TWOCOINS
木DP
親までしか見ないやつ解いてた
そこまでは見覚えがある
もうちょいだ

    • -

最初の4投はWA。制約を誤読してる… 上下からは来ちゃいけないと思ってて
そうじゃなくて
親と祖父から、子と孫から、みたいなのは3手になるからアウトで、
みたいな気付き(というか読み違い)がいくつかあって
直して
→smallだけ通った(40pts)
Solution: 14479412 | CodeChef
とりあえず制約の誤読はなくなったと思うけど、なんでlarge通らない?
後で

    • -

ほとんど全員、40だけじゃなくて100で通してる
特別なことはないと見た
あれこれ見直したけど
もしかしてoverflow?
ああ
1e5(impossible)を1e5回足す可能性があるのか
→long longにしてAC
Solution: 14502666 | CodeChef

Servers (Challenge) (SRVRS; 174, 42.82%)

https://www.codechef.com/JULY17/problems/SRVRS
チャレンジ問題。
まずは愚直に(問題を理解してるか確かめるために)1投。priority_queueに、タスク処理時間を足したスコアで全CPUを放り込んでみる。(位置関係ガン無視で)
→Correct Answer
Solution: 14506627 | CodeChef
0.237ptsって。20点台だけど点もらえてる。Correct Answerって言ってるし、とりあえず違反はないってことだろう

さて、ちょっと改造。スコアに全体の中心からのユークリッド距離を含めてみる。
→(当然といえば当然だけど)ちょっと伸びた
Solution: 14508051 | CodeChef
後で

再訪

ここまでpriority queueを1つだけ用意して、中心に近いサーバが有利なように采配してきたけれど
中心から遠い場所からのリクエストに対しても一旦中心を介するのはオーバーヘッド大きすぎ。
動的に、二次元平面上での距離を含めたスコアの良さそうなやつを見繕うにはどうしたらいい?

とりあえず、盤面を適当にグリッドに区切って、各地域にpriority_queueを立てて、そこに問い合わせても空きCPUがない場合には近隣に問い合わせる、みたいなのを書いてみた。
→93点とか出たw
Solution: 14536881 | CodeChef

再々訪

グリッドの大きさを変えてみたりしたけどそれ以上は伸びず
Solution: 14583429 | CodeChef

終結果では95.89933pts付いてた。

終了後

これ読んだ https://discuss.codechef.com/questions/105486/srvrs-editorial-unofficial-discussion
そうか、CPUをプロセス終了時の時空座標 (x_i, y_i, p_i) に置いて、クエリを同じく (x, y, 0) にあるとしていちばん近いやつをkd-treeで探す、と。
時間がかかるものを、空間的に「遠くに」配置する、という発想ができなかった。

Multiplication Program (MULDIG, 47, 7.02%)

https://www.codechef.com/JULY17/problems/MULDIG
1つのテーブルで乗算と加算を表現しないといけないよね
easiest(3進法の、01しか使わないケース)だったら、繰り上がりがないから割と簡単では?
とは言ってもトリッキーな事をしないといけない気がする。
0 1 0
1 2 0
0 0 1
というテーブルを編み出した。f(x,x)={0->0, 1->2, 2->1) を利用して、x*y = f(f(x,x), f(y,y)) で求まる。
そして、x,yが共に0か1ならこのテーブルはそのまま加算に使える。
→partial AC (20pts)
Solution: 14445312 | CodeChef

乗算と加算の両方、というか、乗算結果の上の桁と下の桁、加算結果の上の桁と下の桁、を編み出すにはどうしたらいいか
全パターン生成してみたけど思いつかなかった

終了後

これ読んでる https://discuss.codechef.com/questions/105334/muldig-for-partial-points
@nanoalpaca さんのガチで回路を合成してるっぽいやつとか
https://www.codechef.com/viewsolution/14464079
@sir_ementaler さんの f(a,b)=(b==0 ? (a-1)%B : a) 解法は何かエレガント(こういうのをやりたかったんだけど思いつかなかった)
https://www.codechef.com/viewsolution/14441233
@liouzhou_101さんは f(a,b)=(max{a,b)+1)%B とな。

Irrational Root (APRPS; 29, 1.55%)

https://www.codechef.com/JULY17/problems/APRPS
√2+√3+√5, とかが解になる多項式を探すやつ
nが小さいやつならWolfram alphaに投げると答えてくれるんだけど

Π x-(±√2±√3±√5) = 0 みたいな事だと思うけど...解が2^n個だから当然2^n次方程式。n=15だと32768次。奇数次の項は係数が打ち消し合って0になる。(これは自明:Π x-(±√2±√3±√5) = Π (x-(√2±√3±√5))(x+(√2±√3±√5)) = Π (x^2 - (√2±√3±√5)^2))
とりあえずn≦3まではパラメータ決め打ちでいいや
→partial AC (10pts)
Solution: 14501002 | CodeChef

n≦5までのパラメータを求めてコードに含めて
→partial AC (30pts)
Solution: 14541243 | CodeChef

n≦15までこの方式で行けるかと思ったけど10まですら出来なかった…(法則性が読めなかった)

終了後

Polynomials For Sums of Square Roots が分かりやすい。この真ん中手前あたりりで挫折してた。(ここに書いてある方法でも60ptsまでしか行けないらしいが)

公式フォーラム https://discuss.codechef.com/questions/105432/how-to-solve-muldig-and-aprps に皆さんのアプローチがあるんだけど
あれだ
FFT... とか一瞬思いながら使えなくて独自DPで求めてたので phben さんのコードを熟読して理解したい。