競技プログラミングにハマるプログラマのスレ　29

**仕様書無しさん** · 2020/08/22(土) 23:53:04.70

プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)やCTFなどを楽しんでる競技プログラマ(競プロer)の雑談スレ
競プロイベントや競プロ問題や有名競プロerや競プロでよく使うアルゴリズム等について語りあったり、競プロ関連の質問相談なんでもおｋ
競プロ初心者でググっても解説読んでも分からないことがあったらスレの競プロの先輩方に訊いてみるのも手だよ(‮よいなれしもかるれくてえ教かと籍書かとトイサ説解いすやりか分‬)
次スレは>>950

# オンラインジャッジ・コンテストサイト
## 日本語
yukicoder https://yukicoder.me/
AtCoder https://atcoder.jp/
AIZU ONLINE JUDGE (AOJ) http://judge.u-aizu.ac.jp/onlinejudge/
## 英語
TopCoder
Single Round Match (SRM) 関係リンク集 http://codeforces.com/blog/entry/21879
Marathon Match (MM) https://community.topcoder.com/longcontest/?module=ViewPractice
※TopCoderは初参加までの手順が煩雑です。まずはググってみて、それでも分からなかったらスレで聞こう！
Codeforces http://codeforces.com/
CS Academy https://csacademy.com/
Project Euler https://projecteuler.net/ 和訳 http://odz.sakura\.ne.jp/proj
※前スレ
競技プログラミングにハマるプログラマのスレ 28
https://medaka.5ch.net/test/read.cgi/prog/1595677935/l50

**仕様書無しさん** · 2020/08/22(土) 23:54:12.74

テンプレ続き

# 高校生・大学生対象コンテスト
情報オリンピック https://www.ioi-jp.org/
ACM-ICPC http://icpc.iisf.or.jp/

# その他便利なサイト
コンテスト・カレンダー
https://competitiveprogramming.info/calendar
http://clist.by/
AtCoder Problems http://kenkoooo.com/atcoder/
オンライン整数列大辞典 https://oeis.org/?language=japanese
WolframAlpha https://www.wolframalpha.com/
Spaghetti Source
旧: http://www.prefield.com/algorithm/
新: https://github.com/spaghetti-source/algorithm
競技プログラミングwiki http://wikiwiki.jp/kyopro/
AOJ-ICPC http://aoj-icpc.ichyo.jp/
competitiveprogramming.info https://competitiveprogramming.info/
競プロSlack https://competitiveprogramming.info/slack
OnlineJudgeHelper (オンラインジャッジ補助スクリプト) https://github.com/nodchip/OnlineJudgeHelper
Google翻訳 https://translate.google.co.jp/

**仕様書無しさん** · 2020/08/22(土) 23:54:32.26

テンプレ続き

# 書籍
プログラミングコンテストチャレンジブック (蟻本)
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (AOJ本, TLE本, 渦巻本)
最強最速アルゴリズマー養成講座 (チーター本)

# 日本人競技プログラマ
Twitter 競技プログラマリスト
https://twitter.com/kinaba/lists/topcoder-jp
https://twitter.com/kobae964/lists/atcoder
TopCoder Single Round Match (SRM) のランキング
https://community.topcoder.com/tc?cc=392&;sc=&sd=&cc=392&module=AlgoRank&nr=200&sr=
TopCoder Marathon Match (MM) ランキング
https://community.topcoder.com/longcontest/stats/?module=CoderRank&;cc=392
Codeforces ランキング
http://codeforces.com/ratings/country/Japan
https://twitter.com/5chan_nel (5ch newer account)
https://twitter.com/5chan_nel (5ch newer account)

**仕様書無しさん** · 2020/08/22(土) 23:55:11.61

**仕様書無しさん** · 2020/08/22(土) 23:55:45.28

テンプレ続き

# 関連スレ
【したらば】プロコン・競プロ・ハッカソン・CTFなどについて語り合う掲示板
https://jbbs.shitaraba.net/internet/13109/
TopCoder
https://mevius.5ch.net/test/read.cgi/tech/1333159918/l50
プログラミングのお題スレ Part9 [無断転載禁止]c2ch.net
https://mevius.5ch.net/test/read.cgi/tech/1480579110/
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3c2ch.net
https://mevius.5ch.net/test/read.cgi/tech/1466315249/l50
【会津】パソコン甲子園2004【若松】
https://mevius.5ch.net/test/read.cgi/tech/1094308951/l50
CTFについて語るスレ [無断転載禁止]c2ch.net
https://medaka.5ch.net/test/read.cgi/sec/1476430177/l50

>>1からここまでテンプレ

**仕様書無しさん** · 2020/08/22(土) 23:56:30.96

スレ立て始めてなので間違ってたらすまん
昨日のyukicoderみたいに怒らないで

**仕様書無しさん** · 2020/08/23(日) 00:14:59.59

>>6
スレ建てACおつ

**仕様書無しさん** · 2020/08/23(日) 00:24:08.00

>>6
スレ立て乙
ここにはガチギレ赤コーダーはいないから安心して

**仕様書無しさん** · 2020/08/23(日) 00:28:27.96

>>6
立て乙

**仕様書無しさん** · 2020/08/23(日) 00:42:36.48

次から>>1の
(‮よいなれしもかるれくてえ教かと籍書かとトイサ説解いすやりか分‬)
を
(分かりやすい解説サイトとか書籍とか教えてくれるかもしれないよ)
に直してくれ

**仕様書無しさん** · 2020/08/23(日) 00:50:36.09

5ch民思ったより優しかった
>>10 確かにおかしいな、了解

**仕様書無しさん** · 2020/08/23(日) 00:52:41.28

>>1 乙

**仕様書無しさん** · 2020/08/23(日) 00:56:07.97

>>950
テンプレにある関連スレもほとんど落ちてるから次スレからなくていいと思われ

**仕様書無しさん** · 2020/08/23(日) 02:05:17.03

お気持ち表明垢作ったそばから非公開にしてるのな
マジで情緒不安定じゃないか？

**仕様書無しさん** · 2020/08/23(日) 03:12:12.47

人間としても成長できるようにAtCoderはギルド機能を実装すべきでは？

**仕様書無しさん** · 2020/08/23(日) 04:55:31.84

ギルマスが病むからやめろ

**仕様書無しさん** · 2020/08/23(日) 05:39:58.50

ギルド入団条件
1週間で最低10問、できれば20問AC
ratismをしない
分からないことがあったら教え合う

**仕様書無しさん** · 2020/08/23(日) 06:48:09.57

入団条件がratism

**仕様書無しさん** · 2020/08/23(日) 07:31:10.87

暖色以外お断りギルド

**仕様書無しさん** · 2020/08/23(日) 08:19:20.20

そういえば橙色経験者リストを作った人がいたな

**仕様書無しさん** · 2020/08/23(日) 10:23:15.10

ちょっと草

**仕様書無しさん** · 2020/08/23(日) 10:58:34.68

5chの方が初心者への対応マトモとか大丈夫かこの界隈

**仕様書無しさん** · 2020/08/23(日) 11:03:33.80

snukeさんは聖人君子

**仕様書無しさん** · 2020/08/23(日) 12:37:02.25

前スレ、制限時間の間際にa問題の解法クレクレするヤベー奴にもちゃんと対応してるしほんと民度高いなここ
初心者リスペクト0のTwitterでやってたら内輪ネタ大好きな奴らに年単位で晒されてるだろうに

**仕様書無しさん** · 2020/08/23(日) 12:48:46.27

ここの住民わりと優しいよな

**仕様書無しさん** · 2020/08/23(日) 12:55:55.45

twitterだと「見てないけど誰かがコンテスト中にコード晒したんですか」みたいなのが時間差で沸いてきて陰湿な集団イジメが繰り広げられる

**仕様書無しさん** · 2020/08/23(日) 13:00:46.73

そういえば昨日のスクショの人は整数型同士でN/Xすると整数になって切り上げもクソもないから(double)N/Xとかにしないとダメなんだよ
もう解決したと思うけど

**仕様書無しさん** · 2020/08/23(日) 13:33:46.49

ceil((double)N/X) = (N+X-1)/Xって多分有名なイディオムなので覚えておいた方がいい
あとround((double)N/X) = (N+(X+1)/2)/X（たぶん）

**仕様書無しさん** · 2020/08/23(日) 13:37:05.92

今のroundは間違い
round((double)N/X) = (N+X/2)/Xです

**仕様書無しさん** · 2020/08/23(日) 13:53:19.30

まあ5chにも変な人は結構湧くけどちゃんと叩かれるからな
なんだかんだで一部の人除いてまともなコミュニティだと思うわ、競プロ界隈

**仕様書無しさん** · 2020/08/23(日) 14:17:57.60

>>26
ちょっと前に運営の人がそれやってなかったっけ

**仕様書無しさん** · 2020/08/23(日) 14:52:03.10

匿名だと目立とう精神でわざと過激なこと言うモチベ薄れるからな

**仕様書無しさん** · 2020/08/23(日) 14:59:08.23

>>26
qiitaさんがこれで、後から参戦してご意見番みたいなコメントしてて草生やしてる

**仕様書無しさん** · 2020/08/23(日) 15:00:49.89

5chと違って一元化されてなくて見えにくいだけでtwitterでもよく解法晒し→指摘は起こってる

**仕様書無しさん** · 2020/08/23(日) 15:10:46.38

帰属意識が異常に高いから話題に入りたいアピールなんだろう

**仕様書無しさん** · 2020/08/23(日) 15:15:11.32

>>34
幾つかは運営も気付いてるだろうけど損害賠償の件で評判下げまくったのでスルーしてるな

**仕様書無しさん** · 2020/08/23(日) 15:22:19.08

>>36
裏で指摘してるとは考えないのか

**仕様書無しさん** · 2020/08/23(日) 16:04:06.50

最近このスレでsnukeさん信者よく見るけどあれ個人的にかなり気持ち悪い

**仕様書無しさん** · 2020/08/23(日) 16:05:46.15

よく見るか？

**仕様書無しさん** · 2020/08/23(日) 16:06:07.42

0と1からなる文字列とNが与えられる。
「連続する区間のbitを反転させる」という操作をN回までできるとき、
操作後の0の数をなるべく大きくするといくつになるか。
文字列長は10^5以下
この問題わかりますか？某質問サイトに競プロの問題の例として載ってて答えがなかったので

**仕様書無しさん** · 2020/08/23(日) 16:16:12.75

ABC124-Dかな

**仕様書無しさん** · 2020/08/23(日) 16:18:23.78

>>41
今見ましたが、ABCは「連続で」なので少し違う気がします。

**仕様書無しさん** · 2020/08/23(日) 16:20:08.11

>>42
今回は連続する個数の最大ではなく、全体の個数の最大なので
（わかりにくいと思ったので捕捉しました)

**仕様書無しさん** · 2020/08/23(日) 16:21:05.02

1が連続する区間を大きい方から最大N個反転させる？

**仕様書無しさん** · 2020/08/23(日) 16:24:34.94

>>44
それも考えたのですが、
11011で1回の場合、00100にできてしまうので違うと思います。

**仕様書無しさん** · 2020/08/23(日) 16:25:17.92

>>44
S=11011, N=1が反例(最適は全体を反転して00100)

**仕様書無しさん** · 2020/08/23(日) 16:26:14.92

あーそっか・・・

**仕様書無しさん** · 2020/08/23(日) 16:44:40.82

11011→2,-1,2と圧縮して累積和取ってソートして後ろからN個足して前からN個引くみたいな感じでいけたらいいなぁという希望

**仕様書無しさん** · 2020/08/23(日) 16:45:45.06

Kadane's algorithmでできそう

**仕様書無しさん** · 2020/08/23(日) 17:06:14.25

Nの制約は？

**仕様書無しさん** · 2020/08/23(日) 17:14:03.44

>>50
書いてなかったです。
勝手に10^5くらいだと思いました。
このサイトです。連続区間の反転とは書いてなかったですが、そうでないとあまりに簡単すぎるため連続区間だと解釈しました。
https://jp.quora.com/%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%8C%E3%81%A7%E3%81%8D%E3%82%8B%E3%81%93%E3%81%A8%E3%81%AF%E3%82%BD%E3%83%95%E3%83%88%E3%82%A6%E3%82%A7%E3%82%A2%E3%82%A8

**仕様書無しさん** · 2020/08/23(日) 17:26:13.95

なんかそういう制約の確認とかのコミュニケーション含めた面接っぽいな
とりあえずdpでO(N|S|^2)ならできた

**仕様書無しさん** · 2020/08/23(日) 17:40:30.64

>>52
こういう面接系でdpはあまり出ないと思い込んでました
その方向性でも考えてみます

**仕様書無しさん** · 2020/08/23(日) 17:44:58.42

O(n + k log n) で解けるかな。maximum k-segment sum っていう有名問題に帰着すると思う。

**仕様書無しさん** · 2020/08/23(日) 17:54:27.32

maximum segment sumならネットで出てきたのですが...
もしよろしければ詳しく教えていただきたいです

**仕様書無しさん** · 2020/08/23(日) 18:58:21.53

>>33
治安活動かな
学生を育てる変なムーブメントがある

**仕様書無しさん** · 2020/08/23(日) 19:15:47.50

俺が奴を育てたのじゃ

**仕様書無しさん** · 2020/08/23(日) 19:17:49.03

tourist「全人類を育てた」

**仕様書無しさん** · 2020/08/23(日) 19:43:15.04

tourist教徒じゃん

**仕様書無しさん** · 2020/08/23(日) 19:45:56.42

橙「ワシがレッドコーダーを育てたのじゃ」

**仕様書無しさん** · 2020/08/23(日) 19:50:05.80

俺のオカンとオトンは無色

**仕様書無しさん** · 2020/08/23(日) 20:15:59.40

>>40
これに似とるな Alien DPっていう界隈内でもマイナーな知識使うやつ
https://codeforces.com/contest/1279/problem/F

**仕様書無しさん** · 2020/08/23(日) 20:54:08.02

>55
https://en.wikipedia.org/wiki/Maximum_subarray_problem#Generalizations O(n + k)

**仕様書無しさん** · 2020/08/23(日) 21:58:34.23

>>62 >>63
ありがとうございます。みてみます。

**仕様書無しさん** · 2020/08/23(日) 22:48:02.85

愚直にやって問題の入力例と出力例は正解なのにいざ提出するとTLEになる
その愚直な部分をアルゴリズム適用するやり方がさっぱりわからない
他人のAC済みコード見てもさっぱりわからない
全然楽しくない
死にたい

**仕様書無しさん** · 2020/08/23(日) 22:51:40.60

>>65
ちゃんと制約見てる？

**仕様書無しさん** · 2020/08/23(日) 23:09:47.78

アルゴリズム適用するやり方がわからんって言ってる人に制約見てるか聞いてどうすんの

**仕様書無しさん** · 2020/08/23(日) 23:12:08.50

愚直が想定解じゃないならTLEするのは当たり前では
さっぱり分からないなら身の丈にあってない問題解いてる可能性はある

**仕様書無しさん** · 2020/08/23(日) 23:12:18.39

そこらへんは解説記事読むなりしてちょっとずつ積み上げていくしかない気がしますねえ

**仕様書無しさん** · 2020/08/23(日) 23:19:40.82

やっぱり大きめのサンプルは必要なんやなって…

**仕様書無しさん** · 2020/08/23(日) 23:20:58.82

適用する方法って結構抽象的な気がする
わからない問題の解説一つ一つ消化して身につけるしか無い気がするな

**仕様書無しさん** · 2020/08/23(日) 23:49:16.79

>>65は愚直でTLEになるのは百も承知で、それを想定解に当てはめるのが難しいって事だよね
その想定解の典型問題をやって見に付ければ適用の仕方もわかってくるんじゃないか

**仕様書無しさん** · 2020/08/24(月) 00:02:28.31

たかが趣味で分からない、楽しくない、死にたいだなんて、ただの構ってちゃんじゃないの？

**仕様書無しさん** · 2020/08/24(月) 00:16:16.88

5chでの軽口にそんな真剣に突っ込まんでも

**仕様書無しさん** · 2020/08/24(月) 00:17:58.49

突っ込んでる人、人生に余裕なさそう

**仕様書無しさん** · 2020/08/24(月) 00:34:14.69

>>25とはなんだったのか…

**仕様書無しさん** · 2020/08/24(月) 00:35:48.51

そもそも5chの民度がどのSNSよりも悪いことなんて世界中の誰でも知ってるから

**仕様書無しさん** · 2020/08/24(月) 00:37:32.71

発言小町とガールズちゃんねるよりはマシだと思ってる。見たことないけど。

**仕様書無しさん** · 2020/08/24(月) 00:46:34.34

>>67
どのアルゴリズム使うかなんて制約次第でしょ
いざ提出するとTLEになるっていってるから制約見てないんじゃないの

**仕様書無しさん** · 2020/08/24(月) 00:50:35.43

全探索から最後の1つは見なくていいみたいな問題はそもそも"適用する"みたいな考え方がそぐわないかもね
具体的な問題をあげて質問したらなんだかんだここの人は答えてくれると思うから活用してみては

**仕様書無しさん** · 2020/08/24(月) 00:52:39.81

今時ガールズちゃんねるとかを引き合いに出してるの価値観が古すぎてなんかウケるな

**仕様書無しさん** · 2020/08/24(月) 00:54:51.27

価値観が古いのは句点使ってる時点で一目瞭然

**仕様書無しさん** · 2020/08/24(月) 00:55:29.98

競プロer専門ガールズちゃんねるを作ろう（提案）
ネカマだらけになりそうなんですが……

**仕様書無しさん** · 2020/08/24(月) 01:01:40.74

>>65
所詮競プロなんて実務にあんまり役立たないし、私や君は競プロ界で名を馳せる有名人になんて絶対になれないんだから、理解できない問題があってもそんなもんだと受け入れるしかないね
将棋界における藤井や羽生にならなきゃいけないわけじゃないんだからさ

ところでその問題を教えてくれたら、なにかアドバイスできるかもしれないよ

**仕様書無しさん** · 2020/08/24(月) 01:11:17.45

いうてのいみさんとかも背中のチャック開けたらおっさん出てきそうやし

**仕様書無しさん** · 2020/08/24(月) 01:17:37.10

アイドルか何かのアイコンの人？

**仕様書無しさん** · 2020/08/24(月) 01:23:54.93

https://i.imgur.com/7hZEVg8.jpg

chokudaiの中の人が美少女ってマジですの？

**仕様書無しさん** · 2020/08/24(月) 01:24:44.57

>>86
多分そんな感じやわ、やわやわ
1時間でアルコールを200㍉㍑摂取できる人なんだわ、こえー

**仕様書無しさん** · 2020/08/24(月) 01:25:07.80

マジだよ

**仕様書無しさん** · 2020/08/24(月) 01:25:31.43

chokudaiさん普通に声たかくないですか？中身女の子では

**仕様書無しさん** · 2020/08/24(月) 01:27:59.39

すぐレスバトルしちゃう女の子やだな

**仕様書無しさん** · 2020/08/24(月) 01:31:05.88

女の子だからレスバトルくらいするだろ

**仕様書無しさん** · 2020/08/24(月) 01:31:46.48

chokudaiさんも女の子だなんて、わたし興奮で勃起してしまいましたわ

**仕様書無しさん** · 2020/08/24(月) 01:35:43.43

>>92
好きと嫌いだけで普通がないからな

**仕様書無しさん** · 2020/08/24(月) 01:38:12.03

chokudai女の子説
・声が高い
・すぐレスバする
・枕がでかい

**仕様書無しさん** · 2020/08/24(月) 01:48:24.05

（^o^三^o^）イェーイのいみbeetけんちょんこるとん見てるぅ？wwwwww

**仕様書無しさん** · 2020/08/24(月) 01:48:30.16

某赤コーダーがキレてたの生理だからってマ？

**仕様書無しさん** · 2020/08/24(月) 01:51:44.48

彼は野菜だから生理なんてないよ（マジレス）

**仕様書無しさん** · 2020/08/24(月) 01:52:22.03

酷い飛び火させるのやめ

**仕様書無しさん** · 2020/08/24(月) 01:53:45.65

スレの流れが気持ち悪すぎる
個人名出すわわけわからん下ネタに持っていくわで見てられん

**仕様書無しさん** · 2020/08/24(月) 01:55:19.80

競プロerは全員女の子ってそれ一番言われてるから

競技プログラミングにハマるプログラマのスレ 29

競技プログラミングにハマるプログラマのスレ　29