Google Code Jam 2017 Round 1C
- masashinakata
- 1755
- 0
- 0
- 0
@togatoga_ BをDPで解いてる?どうやってまとめるのかいまいちよくわからないのだけど、そもそもどういう形で時間の情報を持ってる?
2017-04-30 21:04:03初めと終わりの部分がどうやら一致しないと1チェンジらしい。そうなると、そのあたりのFreeTimeについての識別が間違っているので、なるほど通らないわけだ。Smallすら通らないのはおかしいなあとは思っていた。
2017-04-30 21:06:06@PnumaSON dp[cameronの使った時間][jamieの使った時間][どっちが世話をしているか] 遷移は、仕事を切り替えるか、そのまま続行するかです。 あとは、最初にcameronなのかjamieなのか両方でメモ化再帰しました。 gist.github.com/16b97e3ddca00b…
2017-04-30 21:08:44GCJは、R1A→新千歳から札幌の移動中に1時間だけ参加して当然ダメ、R1B→ちゃんと参加したけど全然ダメ、R1C→新大阪でラーメン食べてて不参加、ということでR1で敗退でした
2017-04-30 21:15:17GCJみてると人によって得意不得意あるのだなぁと思うので,自分だけ解ける他の人みんな苦手セット来いと思うのは自然な感情だなとおもうなどした←
2017-04-30 21:18:09俺もGCJのTシャツは死ぬまでにはほしいのだけれども、切り替えてTCOのマラソンとCodinGameをがんばろう。もともと俺の習熟度的にはマラソンのほうがまだ勝機があるので、それで取れなきゃSRMはもっととれねえよというやつ。
2017-04-30 21:29:42久しぶりすぎてDPの基本思想を忘れていたということに今気づいた。ああ、確かにこれなら時間内に解けますわ。DPってそういえばこんなふうな解き方する方法でしたわ。うーん、くそ雑魚。でも実行速度は俺のが早いと思っているが、そんなことより、この場合は実装が簡単かどうかだろう。
2017-04-30 21:56:47【ブログ更新】 Google code jam 2017 Round1C B. Parenting Partnering ift.tt/2qi5onj
2017-04-30 22:24:24Bsl: 1) 両端が等しい隙間を合計が720を超えないように、狭い順で埋める 2) それぞれ合計が720になるまで隣接する隙間を埋める 3) 何かの合計が720になっていない場合、埋まってないところをそれで埋める
2017-04-30 22:24:33Cs: 二分探索。mをターゲットの確率、Uを予算として与えられた確率値が小さい要素順に埋める。mに満たない要素がある場合、そのmはターゲットとして大きすぎるということなので棄却、上界を下げて探索。予算が余った場合は上界を上げて再度探索
2017-04-30 22:28:27Asl: ピースを一つ選ぶ。その平面積は全体を上方向から見た場合の面積と等しい。残るピースからK-1個、垂直方向の面積が大きい順に選び総和をとる。先ほどの表面積と合わせて一番大きいものが答え。あらかじめ垂直方向の面積で整列していればO(NK + logN)
2017-04-30 22:34:14GCJの予選,largeを諦めて次のsmallを先に解きに行く選択が必要だったりとか,解のうち一つを出力するような問題では時間を取ってsmallとlargeといっぺんに通しに行く選択が必要だったりで,戦略的な部分も問われるので個人的に好き.
2017-04-30 23:48:53Google Code Jam 2017 - Round 1C - naoya_t@hatenablog naoyat.hatenablog.jp/entry/GCJ2017R…
2017-05-01 01:59:48