競技プログラミングにハマるプログラマのスレ 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/
123仕様書無しさん
垢版 |
2020/05/11(月) 14:42:34.50
解説なんて読んでないが二幸係数の定義ってのはちょっと面白解説のたぐいだなw
パスカル三角に定義もくそもないしなそう次々と定義ぶっこんだら数学の理論体系早晩破綻する(´・ω・`)
2020/05/11(月) 14:43:28.07
>>122
>>119 の式を展開したら偶数の項だけ残らない？
2020/05/11(月) 19:46:13.25
青:優秀/黄:スーパー優秀/橙:天才/赤:怪物/冠:スーパースター
AtCoderの難しさに打ちのめされたわ、Chokudaiさんの各色に対する評価は正しかった
黄色で十分過ぎるぐらいに凄いわ,外から見てた時には分からなかった...
2020/05/11(月) 19:47:58.87
緑のぼくは？
2020/05/11(月) 19:51:51.14
頭悪い
2020/05/11(月) 19:53:20.45
酷い
競プロやめます
2020/05/11(月) 20:03:47.62
来週で黄色になるぞー
青でもすげーって言われるし黄色になったらめっちゃすごいと思われるんだろうな
2020/05/11(月) 20:04:22.28
>>128
俺は嫌な思いしてないから
それにお前が嫌な思いをしようが俺の知った事ではないわ
だって全員どうでもいい人間だし
大袈裟に言おうがお前が死んでもなんとも思わん
それはリアルでの繋がりがないから
つまりお前に対しての情などない
2020/05/11(月) 20:07:17.08
>>128
安心しろ
お前は天才だ
2020/05/11(月) 20:45:31.15
こどふぉとあっとこーだーの色の関係ってどれくらいある？
2020/05/11(月) 20:53:00.23
あっとこ赤のchokudaiがこどふぉ橙
2020/05/11(月) 20:58:38.83
それは英語が...
2020/05/11(月) 21:16:34.76
https://codeforces.com/blog/entry/70116
2020/05/11(月) 22:53:34.55
AtCoderは初期内部レート下がった影響あるから7ヶ月前より200くらい低く出るイメージ
2020/05/12(火) 08:05:38.69
ABC167-F,415人も解ける人いるのかよ
全く手がつかなかったんだが
黄色は遥かに遠いなあ(泣)
138仕様書無しさん
垢版 |
2020/05/12(火) 11:25:48.65
開始前に甘酒飲んでるんだけど脳みそに効果あると思う？
2020/05/12(火) 11:35:48.32
ルーティーンレベルの意味ならあるんじゃない
2020/05/12(火) 13:48:41.82
酒飲んだら悪い効果があるだろ
2020/05/12(火) 13:52:21.82
甘酒って酒か？
2020/05/12(火) 14:40:46.65
風呂入ったら高いパフォ出た！とか思ってたけど風呂にも入らず睡眠も十分じゃない状態でそれ以上のパフォ出たわ
コンディションより直前までにどれだけ演習積んでたかのが大事だった(体感)
2020/05/12(火) 15:16:05.54
まず得意問題が出るかがデカくて惑わされがちだけど、同じ問題セットならコンディション良い方が良いに決まってる
144仕様書無しさん
垢版 |
2020/05/12(火) 16:34:28.68
>>130
久々すぎて誰の発言だったかググってしまった
145仕様書無しさん
垢版 |
2020/05/12(火) 16:38:37.27
>>137
俺いつもFまで辿りつかないからなんとも言えないけど
これ単に各Siの(と)の個数を調べて(の数が多いやつから貪欲なんだよね？
解法の証明とか正当性の担保とかは抜きにすると、内容的にはDとかEで出てもおかしくない気もするけど、そんな難しい箇所があるの？
2020/05/12(火) 16:45:41.07
>>145
(
))))))))))))))((((((((((((((((
さあどうなる？
2020/05/12(火) 16:56:06.72
F問題はわかれば簡単だけどわからないと死ぬ
順位表のペナ数が物語る
実装は難しくないからやってみて
2020/05/12(火) 16:56:17.99
>>145
こういうそれっぽい貪欲がいくつも思いつくから証明しないとWAが大量に出るタイプの問題なんだと思う
2020/05/12(火) 17:40:01.15
Fは結構ちゃんと詰めないと駄目なところが多いから難しい
過去に類題あるからやってれば解けるレベルではあるんだろうが
2020/05/12(火) 18:01:26.75
abc167-F
簡単に見える人は↓のケース全部Yesになるコード作ってみてほしい

3
((((
))))(((
)))

3
((((
)(
))))

4
((
))((((((
))))))((((((((
))))))))
2020/05/12(火) 18:11:39.91
2番目のやつどんな貪欲だと落ちるんだ？
１番目は潜るのが少ないやつ、３番目は収支が+のやつからみたいなのが落ちそうだけど
2020/05/12(火) 18:25:16.40
WAを出す前にコーナーケースを教えてあげる聖人
2020/05/12(火) 18:32:15.43
これコーナーケースっていうのか？
2020/05/12(火) 18:48:31.16
>>150
if(true){ std::cout << "Yes" << std::endl; }
2020/05/12(火) 18:59:00.61
あのさあ
2020/05/12(火) 19:09:15.74
1番良く落ちるコーナーは
3
(((
)))(
)
じゃないだろうか、'(' - ')'降順を選べるものから貪欲
>>146や>>150だとこの貪欲は全て通るけど、これが落ちるはず
2020/05/12(火) 19:10:16.90
J( 'ー`)し
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
想定だった 感謝
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況