Google Code Jam 2017 Qualification Round
-
masashinakata
- 3358
- 0
- 0
- 0
-
- いいね！0
JetBrains製IDEのパフォーマンスに生産性を握られている
@konjo_p
A-large貪欲といえば貪欲なんだけど，あまり貪欲っぽさはない．どちらかというとDP臭がぷんぷんする感じのやつ．
2017-04-09 21:43:25
無限猿(id:sucrose)@120月病
@Scaled_Wurm
そういえばGoogle Code JamのQualification RoundはA, Bだけlargeまで提出して通ってました
2017-04-09 22:25:43
有為
@uwitenpen
@nico_shindannin 同じ区間への適用は最大1回で、そうすると一番左の要素がひっくりかえっていたときにもとに戻すために使える区間は1個しかない。これを繰り返す感じ。1回以下に限定すると解は1通りしかないっすね
2017-04-09 23:35:52
nico_shindannin（診断人）
@nico_shindannin
@uwitenpen ありがとうございます！「(1)同じ場所へ2回やるのは意味がない」「(2)順番関係はない」「(3)一番左を直すのは１個しかない」そうすると、「(4)解は１通りしかない」 (2)(4)を言い忘れた気がします…。
2017-04-10 07:34:38
ＳＫＹ/sky58🍊
@skyaozora
GCJQualのD、やっと理解した。解法を聞いたらそれで正しそうなのは分かるけど、これ縦横と斜めを独立にできるって思いつくの結構非自明な気がするんだよなぁ。確かに前にもこういうの1問くらいは見てる気がするけど
2017-04-10 23:43:02
kmjp
@kmjp_pc
はてなブログに投稿しました #はてなブログ Google Code Jam 2017 Qualification Round ： A. Oversized Pancake Flipper、B. Tidy Numbers、C. Ba… kmjp.hatenablog.jp/entry/2017/04/…
2017-04-11 00:22:19
きひろちゃん（9歳幼女）
@aki33524
gccのc-large、解いた時はノリだったからなんで解けるか分からんかったんだけどこれ常にrangeが高々2なんですね、面白い
2017-04-11 00:26:04
きひろちゃん（9歳幼女）
@aki33524
直感的に十分よく重複しそうだからテキトーにdictで持ってcount計算していったけど定数なんすねぇ（log n程度にはなるかな〜とか考えてた）
2017-04-11 00:26:44
きひろちゃん（9歳幼女）
@aki33524
最初に2種に別れる区間の長さは一般性を失わずに2b, 2b+1とすることが出来て、2bはb-1, b、2b+1はb, bに分解されるので結局b-1, bとなる。これはdiffが1なので先と同様の議論が出来て常に高々2となる
2017-04-11 00:28:42
kmjp
@kmjp_pc
はてなブログに投稿しました #はてなブログ Google Code Jam 2017 Qualification Round ： D. Fashion Show - kmjp's blog kmjp.hatenablog.jp/entry/2017/04/…
2017-04-11 00:28:50
きひろちゃん（9歳幼女）
@aki33524
はてなブログに投稿しました #はてなブログ GCJ2017qual AをO(N)で解く - aki33524’s blog aki33524.hatenablog.com/entry/2017/04/… pic.twitter.com/RF1GjNXneE
2017-04-11 10:45:51
拡大
きひろちゃん（9歳幼女）
@aki33524
imos法の累積和が重いなら累積しなけりゃ良いじゃない！って発想結構面白い気がしたけどよく考えなくても自明 & 自明
2017-04-11 10:50:01
iwashi31
@iwashi31
めっちゃ今さらなんだけど、GCJQualのCのsmall2、愚直解でもO(NlogN)になっておそらく間に合いそうということに気付いた pic.twitter.com/bNntxl7qoc
2017-04-12 00:05:08
拡大