TCO16 Algorithm R1A
-
masashinakata
- 2466
- 1
- 0
- 0
-
- いいね！0
みさわ
@Mi_Sawa
こういう, 「最適解としてこういうのが取れるから」みたいな形のは, 一度証明してみると, 大体感覚でわかるようになる. ideone.com/ZOkr31 ideone.com/ailnv9
2016-03-27 03:30:36
みさわ
@Mi_Sawa
@Mi_Sawa 前者の証明法は, "貪欲に選んでもあとで困らない" を言うタイプで, 後者の証明法は, "小さいケース(4つから2ペア作る場合)に帰着して, ローカルな改善を繰り返す" タイプ. 両方よく使う.
2016-03-27 03:30:55
tubo28
@tubo28
Medはソートして差の上限を決めると o-o-o-o | o-o-o | o-o-o-o-o ( | を超える辺が存在しない) を含むグラフができるので左から貪欲に、と考えた
2016-03-27 03:32:44
くーむ@( o･ω･)ﾉ
@cocodrips
@tsukammo Div1(強い方)では、ガチガチに強い人がもってったりもしますが、Div2なら、自分が嵌りそうだったケース準備してたらそこそこ落とせます
2016-03-27 03:33:51
タッパーをオーブンで焼かない
@DEGwer3456
TCO、お前はR1は通過だけどメールシステムが壊れたから個人的にメールするぞいっていうメールが来てたんだけど本物だろうか
2016-03-27 03:35:53
くーむ@( o･ω･)ﾉ
@cocodrips
@tsukammo おとしたかったらコード見た時に考えるんじゃなくて、先にケースを考えておいて、それに嵌りそうなコードを探すのがよいです〜〜
2016-03-27 03:36:24
みさわ
@Mi_Sawa
ぱっと思いつく嘘かもしれない貪欲を吟味する時は, たいてい "最初の一歩を貪欲で選んだことで後で後悔しないか" か, "この貪欲をするとこういう解しか出来ないけれど, 最適解としてこういう極端なのだけ候補にしてしまっていいのか" とかを考えて, 脳内で大体証明して納得する.
2016-03-27 03:37:22
みさわ
@Mi_Sawa
昔は結構嘘貪欲を提出してたりした気がするけれど, これでそういうのが一気に減った. (ただし, ぱっと証明出来ないと, 「あ, 嘘なんだな」と思ってしまって, 実は正しいのに, 完全に意識の外に捨ててしまったりする)
2016-03-27 03:38:58
nico_shindannin（診断人）
@nico_shindannin
【ニコ生放送中】 TopCoderでプログラムしてみた 第2259回(TCO2016 Round 1A 直後放送3枠目 Hardつづき) nico.ms/lv257500317#00… #co78570 pic.twitter.com/2wytHFhnPX
2016-03-27 03:39:34
拡大
くーむ@( o･ω･)ﾉ
@cocodrips
@tsukammo 1問解けたと思って他人を撃墜->失敗(-25)->解けた1問も落とす(負のレート)とかするとめっちゃレート落ちます笑 英語はちょっと癖があってわかりづらいこともあります・・・。 こればかりは慣れです＞＜
2016-03-27 03:41:02
くーむ@( o･ω･)ﾉ
@cocodrips
@tsukammo 英語っていうか数学的に間違えたり(nを含むのか、含まないのか)、squareとrectangleを勘違いして解いて失敗したり、そういうとこに注意する慣れですかね？
2016-03-27 03:45:21
くーむ@( o･ω･)ﾉ
@cocodrips
@tsukammo コンテスト至上１番ドキドキヒヤヒヤできるコンテストだと思うのでぜひたのしんでください＼(^o^)／
2016-03-27 03:47:13
sigma
@sigma425
締まっていこう通った やり方はわかれば簡単なんだけど,それはそうと結構実装に気を使う問題(細かい部分が結構ややこしい(例えば始点の部分をどう扱うかとか))
2016-03-27 04:05:21