競技プログラミングにハマるプログラマのスレ 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/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
数え上げ人材育成コンテストだな
276仕様書無しさん
垢版 |
2020/05/17(日) 23:12:29.35
E，arccosの場合分けが辛すぎと思ったら全然違う方法だった・・・
2020/05/17(日) 23:12:54.80
E難しかったな
2020/05/17(日) 23:13:33.99
今日ので数学コンって言われるのは草
2020/05/17(日) 23:16:42.93
EってABC166Eと同じ方法で溶ける？
2020/05/17(日) 23:16:47.42
Atcoder 中学受験 Contest
281仕様書無しさん
垢版 |
2020/05/17(日) 23:21:04.84
D,幅探索で最初にオープンした所の親という方針でなぜ駄目だったのかわからない・・・・
2020/05/17(日) 23:22:54.37
E pairsみたいだな
考慮することが多くて本番で解くのは難しいわ
2020/05/17(日) 23:47:00.08
C問題、間の角度を求めてsqrt(a^2 + b^2 - 2a*b*cos(theta*PI/180.0))ではダメなんでしょうか？
最後の2つのケースだけWAになります

分刻みで時針も動かしてるし変数も全部倍精度で取ってるのですが・・・
2020/05/17(日) 23:48:36.16
>>283
間の角度が間違ってそう
2020/05/17(日) 23:49:30.97
theta=min(2pi-theta,theta)したらなおりそう
2020/05/17(日) 23:55:49.06
>>285
その式のpiとかthetaの単位はなんでしょうか？
>>283はPIが3.14…でthetaは角度（0≦theta＜180）なのですが
287仕様書無しさん
垢版 |
2020/05/18(月) 00:00:04.09
theta桁落ちしてそう
288仕様書無しさん
垢版 |
2020/05/18(月) 00:03:55.19
Eは直行したり、近いベクトルを高速に探索するみたいなのがCS的に普通ちゃ
2020/05/18(月) 04:31:56.31
競プロは仕事の役に立つと考える人、、
MBAは起業の役に立つとも考えてそう
2020/05/18(月) 06:35:25.25
>>281
それで平気だったよ
2020/05/18(月) 07:34:56.21
>>290
有難うございます。式はあってそうなのでテストケース公開を待ってみます
292仕様書無しさん
垢版 |
2020/05/18(月) 08:07:22.52
多重派遣偽装請負損害を助長して
稼働増やして収入減らした
安売り貯金なしドカタは
コロナ恐慌で制裁を受けるべき
2020/05/18(月) 08:27:48.48
>>291
ちなみに出力例は複数あるからテストケースのoutのみが正解ではないからね。
2020/05/18(月) 09:11:00.48
昨日のdiffはよ
2020/05/18(月) 11:33:07.97
経験上、x問目のdiffはx完最遅のパフォ-100〜200くらいのことが多いから
D600
E1600
F2400
くらいっぽそう
2020/05/18(月) 11:44:38.21
過去のBFSって1000くらい無かったっけ。
2020/05/18(月) 12:08:12.26
dfsするだけ、bfsするだけみたいなのは競プロの基本中の基本だから
もっと前のほうで出したらいい
2020/05/18(月) 12:11:04.13
295は適当だったな、D700E1700F2400くらいかな
2020/05/18(月) 12:13:46.01
きたぞ。
750、1800、2500くらい。
2020/05/18(月) 12:36:38.30
DいぇすだけじゃなくＮＯも作って欲しかった
連結成分がひとつじゃないやつ
301仕様書無しさん
垢版 |
2020/05/18(月) 12:48:55.23
昨日のEについて、解説にある連想配列までは作れたのですが、その後の『基礎的な数え上げ』ができませんでした…
数え上げって何か勉強の仕方ありますか？あまり競プロの解説記事もない気がするのですが…
高校数学からやり直せ、という話でしょうか？

>したがって，”仲の悪いつがい” になる傾きのペア (高々 N 通り) 全てについて，連想配列などを 使って各傾きになるイワシの個数が求まれば，その後は基礎的な数え上げの範疇です.
302仕様書無しさん
垢版 |
2020/05/18(月) 12:56:08.70
ここはwriterも説明足りなかったかなって反省してたとこだね
ある集合から自由に選べるのが2^n通りなのがわかれば
集合(S,T)から取り出したとき、すべてが片方の集合に属する場合の数は
Sのみ: (2^s)*1 (sはSの要素数)
Tのみ: (2^t)*1 (tはTの要素数)
になって、ここから両方空集合になる1通りを除いて
(2^s)+(2^t)-1になる
2020/05/18(月) 12:58:49.77
Dで非連結を判定するのは考察の量に比べて実装が重いからなあ
304仕様書無しさん
垢版 |
2020/05/18(月) 13:03:11.66
そんなに重いか？
1からBFSし終わって訪れてない点があればNoで終わりじゃない？
2020/05/18(月) 13:08:49.39
UnionFindでやっても良さそう
2020/05/18(月) 13:36:02.58
BFS だけで連結性判定終わってるのに Union Find 持ち出す理由がなくね
2020/05/18(月) 13:38:59.50
連結リストに出てこなかった数字は非連結（嘘解法）
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況