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

レス数が900を超えています。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/08(月) 12:43:36.88
冷静に考えると1200点で0ACが一番外してるのか
2020/06/08(月) 13:02:21.88
100点と300点なら3倍難しいと思うけど400点と1200点ならそれ以上に難しいと思う
849仕様書無しさん
垢版 |
2020/06/08(月) 15:05:47.75
chokudaiってコンテスト毎回出てたら銀冠いけるよな
2020/06/08(月) 15:33:02.03
いくら点数は相対的って言っても昨日のAGC-Aを500点以下にする意味なくないか
2020/06/08(月) 15:37:36.42
Xor Sum 3より難しいよな
2020/06/08(月) 16:41:41.45
AGC基準の点数だから
2020/06/08(月) 18:22:57.05
てか点数って意味あるのかなあ。
コンテスト内でしか意味をなさないものだし、A問題は100点固定にして、そこから他問題調整すれば良い気がするけど。

現状点数がatcoderが考える難易度的な意味もあるってこと？
2020/06/08(月) 20:31:57.57
>>853
AtCoder Problemsに影響する
2020/06/08(月) 21:31:00.50
>>846
F解いてもA〜C3完に負けるって悲しいって思っただけです
AtCoderの配点思想知らないから適当
2020/06/08(月) 22:05:48.84
http://nagoyacoder.web.fc2.com/topcoder/consideration/xor.html
こちらのページに次のように書かれていたのですが、これは本当でしょうか？
自分にはO(NlogN)解法しか見つけられませんでした

> n個の数から2個取り出して排他的論理和がxになるようなペアはいくつか？
> この場合にO(N^2)は必要ありません。O(N)で十分なので注意しましょう。
2020/06/08(月) 22:14:22.40
連想配列はO(1)とすると、各値に対して対になる値の個数はO(1)で求められるので全体O(N)
2020/06/08(月) 22:17:44.85
>>857
ハッシュの存在をすっかり忘れていました…
回答ありがとうございます
2020/06/08(月) 22:21:52.81
apiad氏の京子の頭の上に乗ってるのは何？
2020/06/08(月) 22:36:20.27
>>859
これ俺も気になったｗ
2020/06/08(月) 22:48:19.38
https://www.chineselyrics.org › lvm...
中国で『緑の帽子』を被ってはいけない理由とは？ | 中歌街
2020/06/08(月) 22:59:22.65
意味あったのね
けど、これって男性限定っぽい
京子に被せてるのはまた別の理由がありそう
>>861 ありがとうございます
2020/06/08(月) 23:49:45.75
レートの分布見られるよ
https://clist.by/resource/codeforces.com/
https://clist.by/resource/atcoder.jp/

clist最強のコンテスト支援サービス！
2020/06/09(火) 03:01:04.27
>>863
フィルタで日本だけの分布も見られるんだね
2020/06/09(火) 06:51:28.08
灰色多すぎ
０点多すぎ

アカウント作っただけでしょ
集計から除外したい
2020/06/09(火) 09:35:43.79
言語アプデはまだかの
2020/06/09(火) 10:08:52.08
公式Twitterによると一週間後あたりを予定してるとのこと
2020/06/09(火) 16:48:06.72
>>863
すごいな、色別人数を指数表示で見ると見事に線形っぽく減少してる
869仕様書無しさん
垢版 |
2020/06/09(火) 18:22:15.44
灰色ってことはコンテストには参加したと
870仕様書無しさん
垢版 |
2020/06/09(火) 18:23:39.26
>>865
min ratingに600とか入力するといい感じになるよ
2020/06/09(火) 19:08:33.20
「地頭」君、気を付けろ!雑菌は至る所にいるぞ!
老後のために資産運用を始めなきゃな!
プログラミングは独学だと厳しいから、
スクールに行かなきゃな!
健康のために野菜をしっかり食べて、
たまにはサプリメントとトクホ飲料に頼りつつ、
スキンケアと頭皮ケアに励んでくれよな!
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のレートに反比例してないか
レス数が900を超えています。1000を超えると表示できなくなるよ。
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況