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

■ このスレッドは過去ログ倉庫に格納されています
1仕様書無しさん
垢版 |
2020/05/09(土) 00:48:33.62
プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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
※前スレ
競技プログラミングにハマるプログラマのスレ 24
https://medaka.5ch.net/test/read.cgi/prog/1585409967/
2020/05/13(水) 12:14:34.72
提出時間でソートすると、
謎の自作ライブラリがたくさん出てきて圧倒されるわ
2020/05/13(水) 12:19:58.80
テンプレ最小限な人もいるから探せ
2020/05/13(水) 12:39:04.38
>>171
>>175
そうなんですか・・
ありがとうございます
2020/05/13(水) 12:43:46.72
嘘をなくすためにT Q1 Q2...という複数テストケースにすればいいのにね
AtCoderの中の人は特にこの形式を嫌ってる気がする
2020/05/13(水) 12:49:57.61
複数テストケースはデバッグが面倒になるから嫌だな
2020/05/13(水) 12:50:50.43
むやみにテストケース増やしてもそんなに落とせる解法が増えるわけではないしコストに見合わないと思う
2020/05/13(水) 12:51:02.12
マルチテストケースを捌くのだけでAより難しそう
2020/05/13(水) 13:31:09.04
>>174
そういう遊びがあるんですね
勉強になりました
2020/05/13(水) 14:11:16.96
コドフォのdiv2-AはABC-Aほど虚無じゃないからねえ
マルチテストケースに対応するコード書く方が問題自体より難しいということにはならない
2020/05/13(水) 14:36:45.74
なにいってだこいつ
186仕様書無しさん
垢版 |
2020/05/13(水) 16:50:04.60
2<=N<=20000とか書いてあったら20000行のテストケースを作る
もちろんperlで
187仕様書無しさん
垢版 |
2020/05/13(水) 16:53:08.14
handmadeの厭らしいテストケースを100分の間に思い付くのは常人には無理
2020/05/13(水) 18:45:56.72
社長にDMして聞くっていう発想が凄いよなあ。
このスレとかの方がまだレスポンス返ってきそうだし、ソースコード匿名でpastebinにでも貼って質問して欲しいわ。
2020/05/13(水) 21:18:43.41
なんの話？
2020/05/13(水) 21:45:14.19
ソースコード　デバッグ依頼の話。
https://twitter.com/chokudai/status/1260496636788293632
https://twitter.com/5chan_nel (5ch newer account)
2020/05/13(水) 22:20:01.37
みんな積極的だなぁ
2020/05/13(水) 22:25:13.04
【お知らせ】ほぼ全ての過去問について言語のアップデートが行われました。最新の環境で過去問に挑戦いただけるようになっております。
2020/05/13(水) 22:31:05.22
アプデされてない過去問ってなんだろう
2020/05/13(水) 22:33:28.49
WJから変わらない…
2020/05/13(水) 22:58:10.33
質問の話はわかる、まあわかるんだけど、そこまで至ってない初心者を切り捨てそう。大体質問するのって初心者な気がする
2020/05/13(水) 23:13:54.95
初心者だろうと一括で切り捨てるしかなくね
2020/05/13(水) 23:16:23.79
社長にDM送っちゃうような人は能力の偏り的に素質を感じる
2020/05/14(木) 00:20:41.53
>>197
さすがにどうかと思うよ……？（chokudai）
2020/05/14(木) 01:11:46.90
いい意味の素質か悪い意味の素質か
2020/05/14(木) 13:40:51.45
まともにテストもできないAtCoder社
2020/05/14(木) 14:40:11.49
CODEFORCESのdiv3ってどのくらいの難易度ですか？div4よりかなり難しいですか？
2020/05/14(木) 16:03:47.02
こどふぉはPROBLEMSETというところで問題の難易度が見れるので参考にしてください
2020/05/14(木) 16:33:34.54
ありがとう
2020/05/14(木) 20:37:46.12
正の整数からなる長さN(<=10^5)の数列があります
これを二分割し、左の要素の和と右の要素の和が最小となる位置を求めてください
ただし、最小となる位置が2つ以上あるときは、最も左のものを求めてください
制約：前計算量O(N)、クエリ計算量O(logN)

上記の問題を解くときは、三分探索を使うのでしょうか？
それとも、二分探索でも解けるのでしょうか？
そもそも、数列で三分探索なんてできるのでしょうか？
一応実装しようとしたのですが、考えている最中にどうしても頭が壊れてしまいます

回答よろしくお願いします
2020/05/14(木) 20:47:11.66
二要素の最小化は意味不明なんだけど、「左の要素の和と右の要素の和が最小」って具体的にどんな操作がさせたいの？左の要素の和と右の要素の和の差を最小にするとか？
2020/05/14(木) 20:50:08.42
文字通り捉えるならどこで切っても左右の和は同じなので答えは常に0ですね
左右の差にしてもクエリがなんなのかよくわからん…
Absolute Minimaのことなんかな
2020/05/14(木) 20:51:39.17
小さくない方を最小化 や 差を最小化 なら二分探索で可能 単峰性があるから三分探索でも可能
2020/05/14(木) 20:59:56.88
>>205
言葉足らずでした。すみません
左の要素の和と右の要素の和の差を最小、が正しいです

>>207
数列は離散量ですが、三分探索は可能なのでしょうか？
自力で実装しようとしても、どうしてもバグが発生してしまいます…
めぐる式にぶたんみたいに簡単に実装できないものでしょうか？
2020/05/14(木) 21:05:23.42
三分探索は「その区間の中では単調増加でも単調減少でもない」ような区間を探索によって狭めていくことと考えることができる
二分探索が「その区間の中にYesとNoの境界がある」ような区間を狭めるのと同様に区間を狭めるだけだから離散でも三分探索はできる
2020/05/14(木) 21:07:05.59
二分探索だと、(左の和)-(右の和)の符号が変わる前後を見る
三分探索だと|(左の和)-(右の和)|について三分探索する

で解けるはず
2020/05/14(木) 21:17:00.04
離散値で三分探索したくなったら差分を二分探索(素振り)
2020/05/14(木) 21:17:45.97
値が離散なら誤差を気にしなくていいから差分で二分探索安定なんだよなあ
2020/05/14(木) 21:34:35.67
int L, R; で L がマイナスの位置とすると、答えは L か L+1 になるということですかね…
確かにこれだとかなり楽になりそうです
みなさま回答ありがとうございました！
2020/05/14(木) 21:53:33.94
クエリとはなんだったのか
2020/05/14(木) 21:58:18.50
https://pastebin.pl/view/1ca00f44
とても書きやすかったです
ありがとうございます

>>214
色々言葉を端折ってしまい申し訳ないです
最初に10^5の長さの数列が与えられ、
そのあと(L, R)というクエリが10^5個与えられる、という意味です
216仕様書無しさん
垢版 |
2020/05/14(木) 21:58:58.35
こどふぉ、タグ付け機能のおかげで
自分が解きたい難易度やジャンルの問題を簡単に探せて超便利

おまえら AtCoder なんかよりこっちやったほうが良いぞ
2020/05/14(木) 22:05:20.88
>>215 absつけ忘れた
2020/05/14(木) 23:51:17.53
コドフォは問題数の多さはとても魅力的なんだけど青くらいからPythonじゃ絶対無理な問題がそこそこの頻度で出てくるんだよなー
numbaとは言わんからせめてnumpy,scipyをくれよ
219仕様書無しさん
垢版 |
2020/05/15(金) 00:40:03.74
N個の整数と整数Xが与えられる。
N個の整数の中からいくつか選び、その和(sumとする)とXの差の絶対値が最も小さくなるsumを求めよ。

これどれくらいの計算量で解ける?
2020/05/15(金) 00:42:10.85
2^N とか NX とか
2020/05/15(金) 00:43:45.10
部分和問題を含むから NP-hard っぽく見える
222仕様書無しさん
垢版 |
2020/05/15(金) 01:12:52.38
想定だった 感謝
2020/05/15(金) 09:52:56.49
AtCoder社,ぜひ覇権プロダクトを生み出して
競プロの有用性を自ら証明して欲しい
2020/05/15(金) 11:55:10.30
コドフォ vovuhって人がかなり問題たくさん作っているのか。
逆に作問ばかりでコンテストには最近参加してなさそうだが。

作問どれくらい稼げるんだろうか。
2020/05/15(金) 12:37:21.84
AtCoderとCodeforcesでよく見るvjudge1やvjudge2ってどなた？
なんかよくわからないけどめっちゃ目に付く
2020/05/15(金) 12:40:49.84
https://vjudge.net
ここから提出するとvjudge数字になる
2020/05/15(金) 12:59:00.12
>>226
なるほど…。ありがとうございます
2020/05/15(金) 19:00:10.85
明日はGCJか 昼までにおきれたらいいな
2020/05/15(金) 19:38:18.13
今日
yukicoder SRM
明日
GCJ CFdiv2
明後日
CFdiv2 ABC

全部出ような
2020/05/15(金) 20:25:34.21
SRMへの参加についてですが、
ContestAppletProod.jnlpをダウンロードするしか方法はないのでしょうか？
Javaアプレットと聞くと古いイメージがあり、あまりこの方法を取りたくありません
2020/05/15(金) 20:46:17.96
コドフォ1回でただけで青になってたんだがAtcoderで言うと何色なんだ？
2020/05/15(金) 20:48:58.92
水くらい
2020/05/15(金) 21:00:44.88
こどふぉの初期ratingは1500定期
234仕様書無しさん
垢版 |
2020/05/15(金) 21:35:13.69
コドフォ一回だけ出て履歴書に青ですって書くの良さそう
2020/05/15(金) 21:57:02.64
こどふぉの初期レート下げるらしいぞ
https://codeforces.com/blog/entry/77130#comment-618402
2020/05/16(土) 00:25:26.80
>>235
ワンチャン900まで初期レート下げるのか
まだ登録してない人は今のうちに初期レート1500貰っとくのが得っぽいな
2020/05/16(土) 03:32:11.19
5/23 AGC044
5/30 NOMURAコン
6/7 AGC045 ←New!!
6/20 AGC046 ←New!!

ここにきて怒涛のAGC連打は草
これで延期になった042と合わせて目標の年6回に対して5回を既に消化することになるのか
2020/05/16(土) 05:14:16.14
起きたらAGC生えてて草
予定通りAGC6回ならペース悪すぎるなあ
俺はABCratedだから関係ないけど
239仕様書無しさん
垢版 |
2020/05/16(土) 10:11:15.80
ARCはもう開催されないのか
2020/05/16(土) 10:19:25.83
ARCは企業コンと統合するとか言ってなかったっけ
2020/05/16(土) 10:38:10.15
累積和で解ける問題をセグ木で解いたり、
オイラーツアーで解ける問題をHL分解で解いたりと、
オーバースペック気味に解いてしまいます
これは、問題をたくさん解くことで徐々に改善されていくものでしょうか？
2020/05/16(土) 10:47:59.35
パソコン甲子園、何故解説を公開しない?
作る時間はいくらでもあるよね?
参加者のことを何だと思ってるんだろうね
2020/05/16(土) 12:00:06.44
>>241
どのデータ構造を使うかの慣れの問題なので，たくさんといてれば思いつくようになる
解けるなら別になんでもいいと思うけどな
244仕様書無しさん
垢版 |
2020/05/16(土) 12:11:45.14
>たくさんといてれば思いつくようになる
ってのは認知バイアスじゃねえか？

たくさんやって最適なものを思い付くようになった上位者は必ずそう言う
が、たくさんやったが思い付くようにはならなかった……みたいなヤツもいる
2020/05/16(土) 13:00:42.83
こんなアドバイスは自分の経験で言うしかないでしょ・・・
データなんかないんだから
2020/05/16(土) 13:21:05.27
解けるならいいんじゃないの(適当)
2020/05/16(土) 13:50:20.74
コンテスト中はACさえとれりゃok
殴ったと思ったらちゃんと復習すればよし
2020/05/16(土) 15:48:22.92
オーバースペックで解くのは定数倍以外は何も問題がないし、定数倍のいいライブラリを整備していればそこで詰まることは滅多にない
2020/05/16(土) 16:40:20.71
まあ累積和→セグ木はオーダーレベルで悪くなってるから実害がなくはなさそう
log2つ乗っけてTLEは普通にありうるからなあ
2020/05/16(土) 22:39:18.88
Code Jam Round2ってAtCoder黄色ぐらい？
2020/05/16(土) 23:14:26.33
Code Jam Round2とは
2020/05/17(日) 01:15:30.59
google code jam
2020/05/17(日) 01:32:44.08
2問完答だけじゃ1000番以内無理だった
悔しい
2020/05/17(日) 02:34:57.89
>>252
Code Jam Round2レベルの実力とは
255仕様書無しさん
垢版 |
2020/05/17(日) 04:25:19.74
突破ボーダーでしょ
黄色中位くらいかね
2020/05/17(日) 19:32:40.22
>>230
https://arena.topcoder.com/
2020/05/17(日) 20:09:24.51
社会人になった競プロerが学生時代より弱くなるの、
競プロの能力が実務とは別物であることの、何よりの証明だと思うんだが...
ベテランが無精進で暖色になれるような問題内容でなければ、
レート≒エンジニアリング能力とは言えなくね?
2020/05/17(日) 20:13:26.57
時間が必要なのはなんでもそうなのでそれだけではなんとも
2020/05/17(日) 20:19:05.39
楽しいゲームをやってるのに実務実務うるさいな
2020/05/17(日) 20:30:11.55
実務に有利だエンジニア能力だって言ってるのは運営側なんだよなぁ
2020/05/17(日) 20:34:06.16
実際に必要なのはプログラミングより数学だしな
しょうがない
2020/05/17(日) 20:37:50.53
所詮数学コンテストだもん
2020/05/17(日) 20:55:01.56
数学速ときコンテストたのしー！
2020/05/17(日) 20:55:32.60
パズルたのしー
2020/05/17(日) 20:56:39.67
競プロが強ければ得する会社もあるけどそこに入るのに必要なのは競プロ力じゃなくて学歴だからね
競プロやる前に勉強しなさい学生よ
競プロは高学歴が打ち込む遊びだぞ
2020/05/17(日) 20:59:15.98
まあでも形式に慣れてないとか以外で緑にもなれないような人が同じような分野のコーディングバリバリできます！ってことはあまりなさそう
2020/05/17(日) 22:42:53.17
HとM勘違いして10分とかしてワロタ
2020/05/17(日) 22:44:58.07
言ったそばから数学コンだった
つまんね
2020/05/17(日) 22:48:30.32
まさか余弦定理が出ると思わなくてびっくりした
2020/05/17(日) 22:50:42.90
BFS勉強したばかりで良かった
2020/05/17(日) 22:57:01.46
三角関数くらいこれまでも散々出しただろ？と思われてるな
2020/05/17(日) 22:58:54.72
複素数を使えば頭を使う必要なし
2020/05/17(日) 23:02:50.40
むしろ余弦定理の方がややこしくねえか
わざとややこしく書いてる解説かこれ
2020/05/17(日) 23:08:52.75
余弦定理だと脳死でできるから楽
2020/05/17(日) 23:09:06.12
数え上げ人材育成コンテストだな
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況