灰色コーダーの集い - 1468745695

1：名無しさん：2016/07/17(日) 17:54:55 ID:jbNr.Lyk: あつまれ～
2：名無しさん：2016/07/18(月) 00:14:10 ID:jbNr.Lyk: 集まらなかった(´・ω・｀)
3：名無しさん：2016/07/22(金) 21:59:08 ID:rmm7o.ok: 議題は？
4：名無しさん：2016/07/23(土) 03:32:41 ID:L2ceMYK.: 課題って？解けなかった問題を出し合うとか？
5：名無しさん：2016/07/23(土) 15:48:26 ID:Rbt4qAgk: int の100000個の配列をグローバルに抱えてるくせにメモリ使用量20KBとかの奴いるんだけどなんなの？この時点で3MB使ってんじゃないの？
6：名無しさん：2016/07/23(土) 15:50:57 ID:Rbt4qAgk: 200KBだった
7：名無しさん：2016/07/23(土) 18:41:51 ID:3errpzsw: >>5
どんなコードか見てみたい
8：名無しさん：2016/07/24(日) 03:18:42 ID:g9fENuZo: >>5-6

int型を4byte(32bit)だとして
配列サイズ100,000を単純計算で400,000byte、400KB(約390KiB)になるね

IDEONEで実験してみた

C++14
http://ideone.com/TbdMom 配列なしメモリ 3464KB
http://ideone.com/oSlzc9 配列あり(グローバル) メモリ 3804KB
http://ideone.com/v3l7hh 配列あり(動的確保) メモリ 3416KB
http://ideone.com/TJIncb ベクターメモリ 3464KB

IDEONEのメモリはバイナリのサイズを示してるのかな？
配列ありなしに関わらず3MBくらい使うね
9：名無しさん：2016/07/24(日) 03:20:15 ID:g9fENuZo: 単純計算だと400KBになるはずだけど
コンパイラによる最適化などでぴったり400KBにならないのかな
10：名無しさん：2016/08/01(月) 20:57:31 ID:tbHO0TB2: おい灰色コーダー！俺は茶色コーダー様だぞ！
11：名無しさん：2016/08/02(火) 20:16:40 ID:2LJQLe1Y: SRMで灰色だ俺
12：名無しさん：2016/08/02(火) 20:58:15 ID:2LJQLe1Y: つか灰色コーダ集めて何すんのさ
13：名無しさん：2016/08/04(木) 23:23:49 ID:tQLRIzYI: 傷の舐め合いはいけない。集まったからには高め合わねばならない。ところで、Codeforcesです
14：名無しさん：2016/08/04(木) 23:53:21 ID:qJXJ2PCs: とうの昔にレジったわ
15：名無しさん：2016/08/24(水) 16:28:46 ID:b7NniP3U: 私は茶色だ、道をあけろ！
16：名無しさん：2016/08/24(水) 18:11:22 ID:ur5qbQFk: >>15
偉そうw
17：名無しさん：2016/08/25(木) 16:35:55 ID:O9dg7FVo: 安定灰色
18：名無しさん：2016/08/30(火) 15:53:55 ID:eOmoEe5c: ここに水平線が何行にも渡って存在するとする。

── ──　　────　　──
　──　　──　　　────　　　　　──
　　　　　　　　　　　──　　　　　 ──
:
:

ここで、垂直な直線を引いて、共通してかかる可能性がある水平線同士は重複と呼ぶことにする

長さは関係なく、重複の存在しない水平線の組合わせを考えるとき、その本数を最大化するアルゴリズムを述べよ。（灰色用基本問題）
19：名無しさん：2016/08/30(火) 16:19:10 ID:iyXMj5X6: >>18
わからん(´・ω・｀)
20：名無しさん：2016/08/30(火) 17:25:29 ID:B322nhb6: たぶんＤＰ
21：名無しさん：2016/08/31(水) 06:58:49 ID:yR0mhDgk: 貪欲法区間スケジューリング
22：名無しさん：2016/09/02(金) 21:58:26 ID:eOmoEe5c: そろそろ解ったかな？
23：名無しさん：2016/09/02(金) 22:21:30 ID:7/.JCEwo: 分かったＮの階乗だ
24：名無しさん：2016/09/03(土) 23:52:08 ID:K7KIIfU.: で、答えは？
25：名無しさん：2016/09/04(日) 03:26:36 ID:TvjD.8Lw: ①先ず左から右か、右から左か方向を定める
②その方向に進んだとき、終端がもっとも早く現れる水平線を一本選ぶ
③選んだ水平線と重複するものを全て排除し、何も残らなくなるまで、残った部分に対して②。
26：名無しさん：2016/09/04(日) 04:19:16 ID:K7KIIfU.: 理解した
俺はレベルアップした
27：名無しさん：2016/09/04(日) 04:22:46 ID:K7KIIfU.: 出題と解説に感謝の意を込め盛大な拍手を送る👏
28：名無しさん：2016/09/04(日) 17:23:10 ID:7/.JCEwo: なるほど
29：名無しさん：2016/09/12(月) 09:40:09 ID:C2wELCM.: 理解出来ない(´・ω・｀)
30：名無しさん：2016/09/14(水) 23:19:45 ID:MXhtcGfQ: どんよくほう
31：名無しさん：2016/09/21(水) 20:45:25 ID:3RfOILbc: 最近覚えたアルゴリズムは？
32：名無しさん：2016/09/21(水) 22:20:38 ID:yR0mhDgk: >>18 に便乗して出題してみる
同じ設定で、今度は水平線をいくつかのグループに分ける
各水平線は必ずどれか一つのグループに含まれ、抜けやダブりはないものとする
同じグループ内の水平線は重複しないように分けるとき、グループ数を最小化するためのアルゴリズムを述べよ
33：名無しさん：2016/09/22(木) 02:14:05 ID:0qa0equ.: >>31 まだ使いこなせてはいないが union find
>>32 難易度上がりすぎぃ！
34：名無しさん：2016/09/22(木) 07:09:59 ID:tQLRIzYI: >>32
最初のをメタに適用するヒューリスティックをすぐに思いつく。
あとは、これが最小か論証せねば…

グループが合体可能とは、ある二つのグループの水平線を全て並べたとき、重複する水平線がないことをいう。
グループが合体可能であれば、それらは一つのグループにまとめて、グループ数を減らすことができる。

ところで、一つグループを選び、それを除外した残りを見ると、そこからどんな水平線を選んだとしても今選んだグループに加えられない。グループのどの水平線とも重複しない水平線があるなら、そもそもそれはグループに含まれ済みの筈だからだ。
ということは、これら残りの水平線群からいかなるグループを作ったとしても、先のグループとは重複するので合体可能でない。

ということは、この作業を再帰的に繰り返してできたグループ群は、どの二つをとってもグループが合体可能でない。これはつまり、これ以上グループ数を減らせないので最小であることを意味する
35：名無しさん：2016/09/22(木) 10:45:53 ID:yR0mhDgk: >>34
惜しい　方向性は合ってるが、最初のと同じ方法だと駄目
とりあえず水平線を{左, 右}と表記すると、例えば{{0, 7}, {1, 5}, {6, 10}, {8, 9}}の4つを{{1, 5}, {8, 9}}, {{0, 7}}, {{6, 10}}の3グループに分けたとき、どの2つのグループも合体可能ではないが、最適解は{{1, 5}, {6, 10}}, {{0, 7}, {8, 9}}の2グループ
36：名無しさん：2016/10/03(月) 00:48:33 ID:G./kyfsc: バンディット問題ってどんな問題？CodeforcesかAtCoderの過去問紹介して
37：名無しさん：2016/10/03(月) 18:35:50 ID:IhtALLz6: 名前からして難しそう
38：名無しさん：2016/12/12(月) 15:34:33 ID:FrE49OJ.: みんなもう灰色は卒業したかな？
39：名無しさん：2016/12/12(月) 15:37:28 ID:IC4fAi0k: >>38
茶色でし(´・ω・｀)
40：名無しさん：2016/12/13(火) 03:42:08 ID:R67nSYYw: SRM灰だし
41：名無しさん：2016/12/20(火) 13:26:24 ID:9SFdNjCg: 最近Codeforcesで色がつきました。みなさんも早く俺のとこまで登ってこいよ
42：名無しさん：2016/12/21(水) 04:18:43 ID:DYSZk1Ko: 文章力のない英語ネイティブな人が問題書いたら、そりゃ読みにくいし
英語ネイティブでない人が問題書いたら、ちょっと変な英語になったり、自国語から自動翻訳で英語に変換した手抜き問題文だともっと酷いし、その上に文章力の無い人だったらもっと酷くなるし

英語競プロはハードルが高い
43：名無しさん：2017/02/10(金) 03:25:06 ID:okadUWnc: 2chのスレ、潜伏div1勢がいるぽい気がしなくもない