競技プログラミングにハマるプログラマのスレ 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/12(火) 19:13:32.02
この問題トラップ全開で楽しいな
2020/05/12(火) 19:14:41.62
ABCの数え上げ、解法の探求・確率のC問題より難しくね?
2020/05/12(火) 19:17:20.23
んな中高生にしか通じないこと言われても知らんがな
2020/05/12(火) 19:19:08.73
>>156
>>150の1つめとどう違うの？これ
2020/05/12(火) 19:24:06.85
ああわかった、'('-')'の数値が逆転してるのか
2020/05/12(火) 19:35:27.09
>>157
わかる
2020/05/12(火) 20:15:22.62
>>156
良い例だけど、コーナーケースではない
165仕様書無しさん
垢版 |
2020/05/12(火) 20:19:33.47
ところですぬけさんが解説でsublime text使ってるけどこれの入力補完（何かのプラグイン？デフォルト？）強すぎませんか？
これ似たようなのvscodeにもあるんですかね？
166仕様書無しさん
垢版 |
2020/05/12(火) 20:20:28.58
ググれば？
2020/05/12(火) 20:22:07.73
スニペットか？
168仕様書無しさん
垢版 |
2020/05/12(火) 20:33:31.10
>>166
ググったら、これが出てきました

All Autocomplete
Sublime Textのコード補完を補強するプラグインです。自分で定義した定数や関数も自動的に補完してくれるので、導入しておいて間違いなしです。

>>167
たしかに、スニペットなんですかね？
cinの引数まで勝手に補完してくれるならかなりいいですね
2020/05/12(火) 20:40:36.79
人権こどふぉDiv1/2 21:35-
2020/05/13(水) 09:11:21.95
初心者で申し訳ない・・
A問題で詰まったので教えて下さい
ABC061A
https://atcoder.jp/contests/abc062/tasks/abc062_a

python3で print('YNeos'['2' in input()::2])　という回答がACです
これだと入力が「1 4」の場合Yesになりますが、
グループが違うからNoになるのが正しいのではないでしょうか？
2020/05/13(水) 09:15:24.59
そういうケースが入ってないのでACになる
これが競技プログラミングや
2020/05/13(水) 10:08:24.95
ICPC,競技として見て駅伝よりずっと面白いけどなあ
天下の電通さんの力でもっとメジャーにしてくれませんかね
俺みたいなICPCウォッチャーはまだまだ少ない様子

今年のICPCは激熱!
東大の内部争いが見ものだし、京大、東工、阪大、筑波、会津の
世界大戦枠争いも楽しみ!
母校である早稲田にはぜひ頑張って欲しい
2020/05/13(水) 10:14:57.21
>>170
Bugハンターの素質があるね！
2020/05/13(水) 11:26:07.94
>>170
コード長が極端に短いものは、コードゴルフ（可読性や正しさを捨てて回答をできるだけ短くする遊び）
をしてる可能性が高いので参考にしない方がいいぞ
他人の提出を参考にするときは提出時間でソートするのが鉄板
2020/05/13(水) 11:40:15.29
Aは全パターン網羅するほどテストケース置けないので
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が学生時代より弱くなるの、
競プロの能力が実務とは別物であることの、何よりの証明だと思うんだが...
ベテランが無精進で暖色になれるような問題内容でなければ、
レート≒エンジニアリング能力とは言えなくね?
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況