したらばTOP ■掲示板に戻る■ 全部 1-100 最新50 | メール | |

灰色コーダーの集い

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
たぶんDP

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
分かったNの階乗だ

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勢がいるぽい気がしなくもない


新着レスの表示


名前: E-mail(省略可)

※書き込む際の注意事項はこちら

※画像アップローダーはこちら

(画像を表示できるのは「画像リンクのサムネイル表示」がオンの掲示板に限ります)

掲示板管理者へ連絡 無料レンタル掲示板