Future Meets You Contest（抽出版）

茄子与一 @skkytkstexhk

主要submission beta.atcoder.jp/contests/futur… (14:15) beta.atcoder.jp/contests/futur… (14:40) beta.atcoder.jp/contests/futur… (15:40) beta.atcoder.jp/contests/futur… (16:25)

merom686 @merom686

なんか条件がきつくて、AC取るだけでも400点くらいあるんじゃないのと思った。でもきついからってきついところを攻めるのは短絡的。

ちるけーき @xuelei7

ふみこんお疲れ様でした。 はじめてのマラソンでそれなりの愉快な経験をしました(´ω`) 2時間かけて、最適解を見つけようとしたけど、失敗... 諦めて、495Bのクソ解法プログラムを投げたら、通った...

hirokazu @hirokazu1020

貪欲の幅どれくらいまでやればいいんだろう

(nは自然数) @n_vip

幅1以外にするとちょっとしか動かせないしうまくいく気がしない

Risen @risenafis

乱択->区間1で山登りのみ．バグ取れなさすぎた． #ふみこん

olphe @_olphe

数列がランダムなので幅が5000とか10000の区間は考える必要がなさそうであることが分かる。 幅が22以下の全ての区間についてその区間のスコアを最大にするvと得られるスコアを求める。 区間幅について全探索してスコアが1番得られるものを採用する

竹雄 @takeo1116

これなんですけど、最初幅200までを想定してセグ木張ってたのに幅を縮めたせいでセグ木使わないほうが速くなってたけど時間足りずに終了

QCFium @qcfium

Future Meets You Contest 理想からの差をマイナスとプラス側に分けて大きい順のsetに突っ込んでそれぞれ大きいほうからとっていって差を埋めていくと32362574696点取れます 左から順にマイナスとプラス見つけて埋めるやるやりかただと29146245158点です

1.038 @1p038

32.3G解:幅1で貪欲 34.7G解:幅50までで貪欲(コスト=A-Nの正負が同じ区間だけ考える、Vは区間内で絶対値最小をとる) 35.1G解:幅50までで貪欲(コストの正負が同じ区間だけ、Vはmin(区間内の中央値,操作した結果1-Nの範囲を超えない最大値))

まーす @__math

最初の幅を12-k/500にして、時間に応じて幅を1まで短くしていった。最初の幅はスプレッドシートにヒートマップ出してノリで決めた

ODA @oda_doa

問題を読み間違えまくって、結局区間1の解答から進歩出来ず #ふみこん pic.twitter.com/cRmwtPaDlo

拡大

竹雄 @takeo1116

最初から乱択と決め込んでたのはよくなかったね

茄子与一 @skkytkstexhk

最後の解法,kの境界値変えるだけでどんどん点数が上がっていくのでおもろい

togatoga @togatoga_

全然だめだった。。。 #ふみこん

face4 @4ecaface4

区間幅2の乱択で3333～点、そこから区間幅3にしてみるもスコア伸びず #ふみこん

夕叢霧香@競プロ @kirika_comp

似たようなことをやったけど、私の方針では |i-A[i]| の v<=i<v+len での最小値を最大にする v を毎回計算した。もっと直接スコアに絡む要素を計算すればよかったわ……。

chokudai(高橋 直大)@AtCoder社長 @chokudai

@e869120 @kirika_comp 貪欲でやったあとに、過去の履歴のvを改竄する動きをすればだいぶのびるよ！ （最前はdiffの中央値だし、各数の変化のmin,maxとかを持っておけば改竄可能範囲は求まります）

茄子与一 @skkytkstexhk

@chokudai マラソン初心者の私でもある程度方針が経ち,しかも考察しがいもある良問だと思いました! (まああまりマラソンらしい解法は取れていないのですが...)

YujiSoftware @YujiSoftware

最初にガーッと動かして、徐々に範囲を狭めていって、最後は範囲1で調整するっていうアルゴリズムにしたんですが、1 ≦ A[i] ≦ N という成約に触れてしまうのであまりうまく行かなかったです。うーん。。。 #ふみこん

yowa @yowa

#ふみこん スコア 33,724M で20位。 やったこと: 全体をK分割、各区間について最適増減量を求め、最大・最小ペアを動かす。 (範囲の大きさ)x(移動量)が閾値以下になったら、Kを2倍に。 最適増減量は、区間内の(現在値-目的値)のmedianで合ってる？（範囲外に出る要素があるなら、そこに丸める感じで）

ふみふみ🐮 @fmhr__

gist.github.com/fmhr/8c950303e… 404してたのでgist

olphe @_olphe

オープンのジャッジ終わった、ふみこんオープン優勝！

chokudai(高橋 直大)@AtCoder社長 @chokudai

@kirika_comp @e869120 それやるだけで多分1位だとおもうよー。（行かなかったらごめんなさい＞＜）

sumoru @sumoooru

#ふみこん オープン4位でした。 やったこと 適当な幅以下の全ての区間について、f(x) = x の線を超えないような最大値を求めて、ソートして、値 * 幅　が大きい順に採用する 「適当な幅」を3~10で全探索して一番良い幅を選ぶ K個の区間について、スコアが一番よくなるようにvを増やす