naoya_t@hatenablog

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

CodeChef October Long Challenge 2017

f:id:n4_t:20171017122525j:plain
https://www.codechef.com/OCT17
最初と最後だけ(=週末参加)
2回めの週末はデバッグで時間を溶かしただけ
617.88214点で241位

長期コンテストだと最初の頃に何やってたか忘れちゃうんだよね
解法を忘れちゃったやつはアとか書いておけばいいのか
ていうかアって何

A Balanced Contest (PERFCONT; 9898, 39.94%)

https://www.codechef.com/OCT17/problems/PERFCONT
1/2とか1/10とか、割り切れない数の場合のボーダーラインに気をつける
→AC https://www.codechef.com/viewsolution/15651835

Max Mex (MEX; 7062; 25.89%)

https://www.codechef.com/OCT17/problems/MEX
MEX: minimal excluded non-negative integer = その集合に出てこない最小の非負整数、みたいなやつ
数をK個追加していいのでこれを最大化したい。未使用の箇所を下から埋めるだけ。
→AC https://www.codechef.com/viewsolution/15651909

Counter Test For CHEFSUM (CHEFCOUN; 3491, 10.82%)

https://www.codechef.com/OCT17/problems/CHEFCOUN
前回の問題
(CHEFSUM) の(誤った)実装例が挙げられて、unsigned intのラップアラウンドを考慮に入れて撃墜ケースを生成するプログラムを書け、というやつ
N=99991〜100000 の範囲で10テストケース、とな。
周期的にそこまでの合計が2^32になるように埋めていくのを考えた。前から合計しても後ろから合計してもその点で0になる、みたいな。0じゃなくても使われてる数より小さければ何でもいいんだけど。後ろから合計しても、ってところで最後の十数個で微調整。
こういうのも面白いけど、なんかみんな割とあっさり解いてない?
→AC https://www.codechef.com/viewsolution/15652412

Chef and a great voluntary Program (CHEFGP; 2453, 10.07%)

https://www.codechef.com/OCT17/problems/CHEFGP
りんご(安い)とバナナ(安い)を配るけど前のk人が連続してたら嫌だからキウイ(高い)を配ってごまかしたい話。
うまく交互に挟んでいくんだけど。少ない方に合わせて、それぞれの区間でa,bを超えないように配っていって、余りを長い方でキウイ処理、かな
キウイは前のk人のフルーツとしてはカウントされないみたいだけど
→20点 https://www.codechef.com/viewsolution/15670461
なんでだろう;問題読み間違えてるかな?
問題文(英文)がわかりにくいので、中国語版の問題を開いてみた。(苹果と芭蕉ぐらいは分かるけど)当然読めないのでGoogle翻訳で。なんかこっちのほうが分かりやすいのは何故だ。
→問題文とテストケースが改訂されたらしいので再挑戦。
キウイも前のk人のフルーツとしてカウントされる、というか、キウイを挟めばカウンタクリアできるようになった。それなら簡単。
→AC https://www.codechef.com/viewsolution/15690209

Chef and Cycled Cycles (CHEFCCYL; 1168, 13.63%)

https://www.codechef.com/OCT17/problems/CHEFCCYL
この問題何か好きだった。
環状線がいくつかあって、それら全てを繋ぐ大環状線(小環状線の2駅が入口、出口みたいになってる)が1つあって、ある駅から(別の小環状線の)ある駅への距離を求める問題。
環状線なので相互間の距離は内回りと外回りで異なるから小さい方。環状線ごとに距離の累積和を出しておけば計算簡単。で、大環状線とのリンク駅のどちらを使うか、で2通りx2通りで4通り求めちゃって最小を返せば良い、かな
環状線を使ってワープ航法みたいなやつができちゃったりしないか不安、大環状線は1本だけなので大丈夫、かな。
→AC https://www.codechef.com/viewsolution/15701269

Chef and Magic Arrays (MARRAYS; 688, 5.43%)

https://www.codechef.com/OCT17/problems/MARRAYS
なんか手頃で良い問題だった。
小皿を並べるときに、隣り合う小皿の隣り合ってる部分の食材同士の美味しさの差の絶対値(にi番目ならiを掛けた)指数を最大化する。
小皿の食材は小皿内でシフトというかローテーションできる。
最初、並び順は自由に変えて良いのか思って問題を難しくしていた(というか別の問題を解いてWA乱発)のだけれど、(permutationではなくrotationなので)左の小皿との接点が定まると、右の小皿との接点も定まる。
ある食材が接点だった場合の指数の最大値、みたいなのを左から右へ持ち回ればDP的に解ける。
→AC https://www.codechef.com/viewsolution/15692493

(Challenge) Connecting computers (POINTCN; 592, 65.86%)

https://www.codechef.com/OCT17/problems/POINTCN
全社を接続するネットワーク(最小全域木でなくて良い)を構築。接続コストと、ハブコスト(接続数によるがランダムな値で、比例関係ではない)が分かっている。
とりあえず最小全域木を作ってから、繋いだ場合に(追加接続コスト+ハブコスト差分)が負になるところを攻めるだけの単純なやつをとりあえず投げた
→9点ぐらい https://www.codechef.com/viewsolution/15696842

Shooting on the array (SHTARR; 173, 3.41%)

https://www.codechef.com/OCT17/problems/SHTARR
CG業界の某氏とかこういうの得意なのでは
ビルが乱立してて、x地点の高度L〜Rから(水平方向に)いくつビルが見えるか、みたいなやつ。但しクエリの最中に時々ビルが伸びる。

あるビルが(x軸上の)どこからどこまでの範囲で見えるかを[区間]として管理・更新していきたい。
(interval treeじゃなくて)segment treeに区間を入れる(vectorを使うのとsetを使うのを試してみた)方式で書いてみる。それぞれの区間はlog(N)箇所に登録される。(登録されているなら間違いなくそこにある)
ビルを右から順に眺めて、大きい順に並んだ数列にビルの高さを挿入していく。新しい高いビルは低いビルを隠すので、挿入というよりは「そこから先を全消去した後にその数字をpush_back」
みたいなシミュレーションをして区間の初期値を求めて、treeに登録する。
何度かの試行錯誤でWAは消えてTLEだけ残った。
(最初のシミュレーションはO(N logN)だし余裕だけど、treeへの登録にほとんどの時間が費やされていた)

2度目の週末に(segment treeではない)interval tree(それぞれの区間は一箇所だけに登録される。登録されているのは区間がそこの最大最小の内側にあって、中点がかぶってることしか保証していないので要チェック)で書いてみたんだけどTLE(最初の構築で2秒前後かかってた)
最終日に部分点狙いのコードを書いた。
→10点 https://www.codechef.com/viewsolution/15866356
2つ目の部分点コードで回すたびに結果が違う…ってのを潰せずに試合終了。(vectorのv[v.size()]に相当する要素を時々参照してた。そういうのはSEGVで落ちてほしい… そこを直したらちゃんと正しい値が出るようになった)

教訓:
・複雑なことをする時には愚直なシミュレーションを書いて答えが一致するか調べる。(正しい答えがわからないテストケースはTLE対策にはなるけどロジックの誤りには無力)
STLコンテナ回りで挙動がおかしい場合。そのコンテナを持ってるクラスがインスタンス化されていなかったり。範囲外を参照していたり。
・ASSERTをがんがん書く。

Lucky Edge (LKYEDGE; 40, 3.87%)

https://www.codechef.com/OCT17/problems/LKYEDGE
問題読んだけど覚えてない

Chef and Horcrux (XORTREEH; 27, 9.02%)

https://www.codechef.com/OCT17/problems/XORTREEH
問題読んだけど
部分点取れるかなと思って一瞬考えたけど後回しにしたまま終了。