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

レス数が950を超えています。1000を超えると書き込みができなくなります。
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/06/09(火) 19:33:50.89
レートついてないユーザはランキングに出てこないからねえ
提出か順位表から飛ぶか、URL直打ちしかない
873仕様書無しさん
垢版 |
2020/06/09(火) 20:37:04.35
すぬけさん独立しないかな
2020/06/09(火) 23:37:10.28
今年のFacebook Hacker Cupのqualは７月下旬？

https://codeforces.com/blog/entry/77952?#comment-630272
2020/06/10(水) 00:10:42.20
>>873
なんで？
2020/06/10(水) 04:17:34.50
意外と問題についてガッツリ議論する場所ってないよね
2020/06/10(水) 04:17:54.12
>>876
2ch内に
2020/06/10(水) 05:38:50.15
ネタバレ回避のためには問題ごとに議論の場所が必要
CodeChefのForumを乗っ取れ
2020/06/10(水) 10:40:35.49
ここでレスしてくれたら可能な限り答えるよ
2020/06/10(水) 19:01:56.82
某大学OBだが、後輩たちの甘ちゃんぶりを見るとマジでイラつく
才能で負けてるのに、東大の学生達より努力しないでどうするんだよ
勝てる訳ないじゃん それで精一杯やりましたとか就活でアピールする気なの?
そんな生ぬるいことやって一体何の意味があるんだよ
2020/06/10(水) 19:10:39.44
本人に言え
2020/06/10(水) 19:45:52.71
趣味に意味を求めるなよ
883仕様書無しさん
垢版 |
2020/06/10(水) 21:27:46.74
がちで努力しても全く勝てないのが才能だろ
凡人が追いつけるようなやつなら一歩先んじた凡人
Bonjinnがどんなに頑張ってもTouristに勝てんだろあうゆう手合が天才な(´・ω・｀)
2020/06/10(水) 21:34:06.20
個人が東大生に勝ちたいなら研究や仕事の方がいいのでは
チーム戦ならまあ分かる
885仕様書無しさん
垢版 |
2020/06/10(水) 21:58:44.82
初心者でも世界チャンピオンと同じ条件で勝負できる！
これだから競プロには人気があって当然！
最高の競技！
2020/06/10(水) 23:05:58.31
俺ももこれから藤井聡太目指すわ！
同じ条件で勝負できる！
2020/06/11(木) 08:22:45.56
藤井聡太もやっとタイトル戦に挑戦できるようになったんだってね
どんなに強くても挑戦権が取れないままずっと

競プロと大違い
2020/06/11(木) 14:14:27.09
なにが言いたいのかさっぱり分からん。競プロを褒めてるのかdisってるのかも分からん
2020/06/11(木) 15:23:54.08
競プロ部があってのOBならわからんでもないが。まずは自分が赤くなって賞品稼いで、母校で講演するとかしないとな
2020/06/11(木) 18:39:21.31
日大アメフト部みたいになってくのか。
OB命令でライバルチームのPC壊しに行ったりｗ
2020/06/11(木) 19:23:35.92
どこからOBの話が出てきた？
2020/06/11(木) 20:37:34.49
OBの話は >>880 だろ
2020/06/12(金) 02:11:29.39
10日後にソートされる数列って何が面白いの
2020/06/12(金) 02:33:32.06
パロすんなら100日でやれよ貧乏くさい

とは思うかな
2020/06/12(金) 03:09:23.06
東京海上日動コン
writer:yutaka1999
配点:100-200-500-700-800-1000
2020/06/12(金) 03:13:02.46
好きな人もいれば嫌いな人もいる
2020/06/12(金) 07:17:16.68
東京海上グループのっ♪
898仕様書無しさん
垢版 |
2020/06/12(金) 11:12:31.44
イーデザイン損保♫
2020/06/12(金) 11:25:30.02
R個の部屋にS人ずつ参加者が割り当てられている。
参加者たちの間であるコンテストが行われた。
タイはなく、各参加者には1位からR*S位までの順位がついた。
ある部屋の中で最も順位が高い者をその部屋のroom winnerとする。
各部屋のroom winnerの順位を並べた数列は何通りあるか。
って問題が分からない。
2020/06/12(金) 11:31:09.21
以下が解法になるらしいのだが、どう読み解いたら良い？
dpはi人をj部屋に割り当ててコンテストを行ったときのroomwinnerの順位を並べた数列の数かなと思うけど、そうすると状態の更新式をどう読めば良いかわからない。
2020/06/12(金) 11:31:41.63
すまん肝心のコードが謎のNGワードにかかって貼れないからちょっと待って
2020/06/12(金) 11:32:08.19
dp[0][0] = 1
for i in [1, R*S]
　for j in [1, R]
　　if i ≦ j*S
　　　dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
return dp[R*S][R] * factorial(R)
2020/06/12(金) 11:33:24.85
行数の規制かと思ってレスを小分けにしてしまったことを先に謝罪しておきます。
すみませんでした。
2020/06/12(金) 12:16:51.71
dp[i][j]の解釈は正しいと思うぞ(より正確に言うとroom winnerの順位でroomをソートすることを考えている)

更新は
- i人目がj部屋目の room winner になる
もしくは
- i人目がj部屋目の room winner にならない
のいずれかで、それぞれ
- i-1人目までをj-1部屋に入れた時の room winner の順列の通り数
と
- i-1人目までをj部屋に入れた時の room winner の順列の通り数
を足せばよい と解釈できる
2020/06/12(金) 12:17:06.32
んー分からん
俺が考えた方針だけ書くか
対称なのでroom winnerの順位を降順に並べてルーム1〜Rとし、最後にR!をかける
dp[i][j]:=i部屋目のroom winnerが全体でj位の場合の数　とする
このときj<=(i-1)*Sが成り立つのでこれで条件分岐
遷移はdp[i][j]=dp[i-1][1]+…+dp[i-1][j-1]
これは累積和で高速に求められるので全体でO(SR^2)

何か間違ってたら言ってくれ
2020/06/12(金) 12:19:24.19
>>905
累積和の部分を整理してi,jを入れ替えたら >>902 のコードと同じになる
2020/06/12(金) 12:28:30.33
>>906
サンクス
言われてみるとそうだな
自分としてはこのdpの持ち方のが自然に見えるな
2020/06/12(金) 14:03:02.76
問題のURLはってくれな
2020/06/12(金) 14:16:38.00
解決したから要らなくね
2020/06/12(金) 14:39:42.06
一般に問題について聞く人はという意味でした
911899
垢版 |
2020/06/12(金) 15:30:06.90
>>904
たとえば「i人目がj-1部屋目のroom winnerになる」は「i人目がj部屋目の room winner にならない」に入ってる？
2020/06/12(金) 15:53:15.84
1位から順に人間を部屋に押し込む
i位目までの人間を部屋に押し込んだとき、j部屋に（部屋の区別は考えない）人がいる場合の数がdp[i][j]
i位目の人は人のいる部屋に入るか（dp[i-1][j]から遷移）誰もいない部屋に入るか（dp[i-1][j-1]から遷移）のどちらか
2020/06/12(金) 16:30:02.18
あとこだのマラソン楽しみ
2020/06/12(金) 16:44:21.65
2時間て短いなあ
自分なりの開発サイクル回してスコア上げてくのが醍醐味だと思ってるから、少なくとも1日くらいくれないとやる気起きない
2020/06/12(金) 16:50:17.94
Introductionなんだから2時間くらいでいいだろ…
数日かけるマラソンマッチが敷居高いと感じる人のためのコンテストだぞ
2020/06/12(金) 23:57:19.01
すぬけさんの解説好き
2020/06/13(土) 00:23:30.38
abcの解説放送見てないマン
2020/06/13(土) 02:02:39.90
すぬけさんは頭悪いとか言わないから好き
2020/06/13(土) 08:52:58.29
速いと噂のjuliaですが、
atcoderの実行時間を見るとpythonより遅い気がしますが
どうですか
2020/06/13(土) 10:53:28.06
ネタが古い
2020/06/13(土) 13:08:09.31
>>26
そういえばこれのソースないの？
ないならid入れてほしいんだけど
2020/06/13(土) 14:47:08.29
https://info.5ch.net/index.php/SETTING.TXT
https://medaka.5ch.net/prog/SETTING.TXT
雑にググったけどもBBS_NO_ID=checkedになってるから強制非表示なんじゃない
2020/06/13(土) 16:30:59.01
>>919
コンパイル時間が必要なのと、コンパイル結果をテストケース毎にジャッジサーバ内でクリアするから、毎ケースコンパイル実行してあまり早くないとチョクダイが言ってた記憶
2020/06/13(土) 16:37:01.53
>>922
板としてのデフォルトであってスレごとに変えられるんじゃないの？
2020/06/13(土) 16:40:27.87
pythonと比べればjavaもc#もpypyも遅いんやで
2020/06/13(土) 17:17:40.63
そうして、C++/Python併用が流行るわけですね
2020/06/13(土) 17:29:30.25
捨てスレでも立ててみたらわかるんでない
2020/06/13(土) 20:23:21.15
入れてほしい奴がスレ立てるなりすれば良いんじゃねえの？
2020/06/13(土) 22:39:55.23
別に落ちるの待たなくてもいつでも建てればいいじゃん
俺は非表示で次スレ立てるけど
2020/06/13(土) 23:19:54.12
ID非表示にしたがるやつなんか後ろめたいことでもあるんか？
2020/06/13(土) 23:26:30.65
今日の難易度で毎週やってくれ
2020/06/13(土) 23:26:35.85
なんで後ろめたいとかそういう話にもってくんだろう。非表示がいい人はこのままで、表示が良い人は新しい方で、で終わるでしょ。
2020/06/13(土) 23:52:27.27
もうすぐこどふぉ
2020/06/14(日) 00:12:32.59
Dがpythonだとかなーり辛かった
新しい言語習得しようかなあ
2020/06/14(日) 00:44:21.61
1位でも海外だと賞金貰えないのかわいそう
2020/06/14(日) 00:46:41.94
まだ初心者も初心者なんだけど、今日のC問題いもす使うところまではわかったんだけど、kの回数を減らせることに気がつかずACできなかった
こういうのって、精進していけば気がつきやすくなるものなんでしょうか？
今はまだ典型的な解法覚えつつABCのC埋めしてる段階です
2020/06/14(日) 01:04:16.82
実験コードを書くようにすればいいんじゃね
2020/06/14(日) 01:50:50.18
>>930
なんで非表示スレに居座ってるんだ？
とっととIDスレに行けよ
2020/06/14(日) 03:06:01.43
今日のCは

それぞれが影響しあって範囲がどんどん広くなるな〜
2つ目のサンプル見るに倍々くらいで増えてもおかしくなさそうだな〜
logだけ見ればいい感じかな？
これ最大ケース書くのすごい楽だな、愚直で試してみよう
やっぱり最大ケースでも100回やる前にカンストするんだな、じゃあ愚直に書けばいいか

みたいな感じで解いた
2020/06/14(日) 04:33:48.83
atcoder3回目でまだimos法まで勉強が及んでなかったんだけど、解説の通りにやってみたらほんとにきれいに揃うので感動した
2020/06/14(日) 05:34:29.61
わかる
imos法は感動したし今でも好き
2020/06/14(日) 06:28:52.69
C問題は
「愚直にやるとO(NK)で間に合わんな、ということは

1. 複数回操作した結果を高速で求める方法がある
2. 実はそのうち収束するから実際にK回操作しなくてもいい

のどっちかやな。」
「1は思いつかんから多分2なんやろ。証明できてないけどええかｗ」
って感じでエスパー気味に解いた
2020/06/14(日) 10:23:20.75
全部Nになるのは分かってたのにいもす法わかんなかった
勉強足りてないな
2020/06/14(日) 10:28:55.98
遅延セグ木でTLEした馬鹿がいたらしい
なんにも理解してなさそう
2020/06/14(日) 10:34:47.51
方針間違えただけでそこまで言うかね
ほぼ晒しじゃん
2020/06/14(日) 10:52:52.85
問題の質チェックの厳しさがWriterのレートに反比例してないか
2020/06/14(日) 11:04:36.06
Dが実装次第でカツカツなこと以外問題あったっけ
2020/06/14(日) 11:06:28.23
ある素数が 25 mod 26 である確率が大体 1/13 くらいっていう主張をよく見るんだけどこれなんで？
2020/06/14(日) 11:09:13.07
素数はほとんど奇数であって、素数を26で割った余りはおそらく一様であることから
2020/06/14(日) 11:14:26.22
>>949
ありがとう
ほとんど奇数っていうの見逃してた(は？)
2020/06/14(日) 11:57:28.17
>>947
Eで論理和と論理積をmapで持つ愚直が通ったらしい
(てかDと若干解法被ってんだな)
2020/06/14(日) 12:04:15.47
>>934
jit使えばどうよ
2020/06/14(日) 12:28:06.63
>> 951
試してみたら確かにっ通った、まあでも通したもん勝ちではあるなこれ
自分の実装だと↓な入力でTLE したがソート とかシャッフルとか挟まされたらどうしようもなさげ
50 50 0 262143
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192
2020/06/14(日) 13:15:18.06
>>953
制約は相異なる整数なのでその入力はinvalid
2020/06/14(日) 13:29:06.74
>> 954
言われて気づいた
なんで相異なる制約にしてるんだこれ
2020/06/14(日) 13:43:01.10
>>955
知らん
相異なる制約じゃないと解けないのかなとか思ってしまったけどそうじゃなくて、なんなんだよとは思った
2020/06/14(日) 15:50:03.13
赤ちゃんライター VS 社会不適合者ライター
2020/06/14(日) 16:45:43.93
SRM710のdiv2-hardをC++でACできる人いる？
C++で通してる人一人もいない
2020/06/14(日) 20:53:00.18
今日のABC、Write的にO(1)問題きそう
2020/06/14(日) 20:59:29.70
教育的とかいいそう
2020/06/14(日) 23:00:44.89
Cの解説、2段落目いらなくねえか
書いた理由がわからんぞこれ
2020/06/14(日) 23:08:27.80
連立方程式解けなくて時間溶かしたｗｗ
2020/06/14(日) 23:13:11.88
何も考えずに二重ループでいい
2020/06/14(日) 23:14:41.18
あの解説は荒れる
2020/06/14(日) 23:14:58.10
chokudaiが解説どこまで手を抜けるか探るなよって言った矢先にこれ
2020/06/14(日) 23:17:59.49
1段落目で解説としては完結してるからなあ
一言多いタイプの人間かこれ
2020/06/14(日) 23:24:11.36
B問題相当ならB問題で出せわかる
2020/06/14(日) 23:24:41.37
C問題解けないレベルの初心者を煽るとかやべえな
何かの病気かな
2020/06/14(日) 23:26:40.58
B,C問題の解説だけわざわざ解説担当の名前まで書いてて、炎上させてくれと言わんばかり。
2020/06/14(日) 23:36:00.59
全探索しましょうって書けばいいのに言い方悪いわ
971仕様書無しさん
垢版 |
2020/06/14(日) 23:38:01.64
E,優先度queだと基本削除できないので違うと思って二分探索と組み合わせて死んだけど、赤黒木みたいな森の奥に生えてる木だと消せるのか・・・
レス数が950を超えています。1000を超えると書き込みができなくなります。
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。