競技プログラミングにハマるプログラマのスレ 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/
813仕様書無しさん
垢版 |
2020/06/07(日) 06:09:47.14
日本人は2人進出、おめでとう！
2020/06/07(日) 07:17:12.88
ビ〇ビンに勃起したア〇ル
2020/06/07(日) 07:19:32.09
くちゅくちゅ、くちゅくちゅ
ぢゅぽっ、ぢゅぽっ
2020/06/07(日) 08:05:58.61
rng_58さんgcjも引退したのか
2020/06/07(日) 10:26:58.40
そろそろ蟻本2を発売してくれ
2020/06/07(日) 10:42:16.17
最近競プロ始めたから知らなかったけどrng_58さんて去年GCJ2位なのか
めちゃめちゃ強い人やんけ
何で今年出なかったんだろう
2020/06/07(日) 10:56:35.81
https://twitter.com/rng_58/status/1195098141030260740
https://twitter.com/5chan_nel (5ch newer account)
820仕様書無しさん
垢版 |
2020/06/07(日) 11:32:41.79
運営側の人間がratedなのおかしくね？いくでもズルできるじゃん
2020/06/07(日) 12:03:16.88
4-8-8-12-12-18
毎回これなら2000-ratedでよかったな
2020/06/07(日) 12:12:21.46
4-8-8は草
rated下限設けて容赦しなくなった感じある
2020/06/07(日) 14:29:09.41
りんごやすぬけやはたまたけんちょんが
誰かがAtcoder本出してくれると信じてるんだけどなぁ
2020/06/07(日) 15:15:41.37
ある程度まではアルゴリズムロジックってサイトで十分な気もしてる
2020/06/07(日) 18:00:29.14
日本の大学生もCode Chefという国際プログラミングコンテストで活躍してみせろ！そしてニューズになれ！

https://mevius.5ch.net/test/read.cgi/tech/1493091609/71

https://www.codechef.com/JUNE20
コンテスト15日まで開催中だ！
2020/06/07(日) 20:36:54.09
>>823
初見でこの文章の1行目の単語分けられたら凄いな
2020/06/07(日) 22:06:19.18
tozangezanさんってケモナーなの？
2020/06/07(日) 23:12:33.50
touristの出遅れからの追い込みがすごい
2020/06/07(日) 23:15:53.48
水色下位は出得コンだ
2020/06/07(日) 23:27:35.76
順位表ちらちら観戦してたけど面白いな
touristかっこいい
2020/06/07(日) 23:33:49.07
maroonrkやばくね？
2020/06/07(日) 23:33:58.52
touristがラスト30秒で2つか3つsubしてて、ジャッジ待ち見てて燃えたわ
2020/06/08(月) 00:00:50.84
AがAGC-A最難、BもCもAC2桁、EF合わせてAC1人は草
今日のACEとBDFで分けて簡単な問題追加すれば043までの難易度のAGC2セット分作れそう
2020/06/08(月) 00:24:59.45
Writerはもっと解かれる想定だったってことか
しかし勿体ないな
2020/06/08(月) 00:33:34.97
AGCは順位表実況がメインコンテンツ
2020/06/08(月) 00:56:13.29
難しすぎるお
2020/06/08(月) 01:10:37.21
AはABC-Fにも良さそう
2020/06/08(月) 01:25:43.24
writerって簡単な問題を出すのは格好悪い みたいな考えあったりするんだろうか。
yukikoとかでも難易度と問題難易度合っていないことが多かったりする。

もしくは天才すぎると最早難易度が分からなくなってしまうのか?
2020/06/08(月) 01:34:54.65
作問者は作った問題について長い時間考えるから簡単に見えるようになってしまう、と誰かが言ってた記憶がある
2020/06/08(月) 01:37:38.75
なるほどねえ。
個人じゃなくて会社としてコンテスト開いてるんだし、ブレを少なくして欲しいわ
2020/06/08(月) 02:04:21.61
最近は不可能ばっかで安定してる
2020/06/08(月) 02:31:34.04
diff青赤赤銅？金は草すぎる
Twitterとか見た感じ今日の適正配点って600-1000-900-1200-2000-2000くらいだったんかな
2020/06/08(月) 02:32:44.91
D銀だったわ
600-1000-900-1400-2000-2000くらいか
2020/06/08(月) 07:53:24.04
Fのdiff5000超えかよ
2000点だと少なくないか
2020/06/08(月) 08:15:16.86
AGC怖
Diffがインフレしている
2020/06/08(月) 10:21:53.13
>>844
それ言うとEはAC0人なんだが…
2000点だろうが2500点だろうが変わらなくないか
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]から遷移）のどちらか
レス数が900を超えています。1000を超えると表示できなくなるよ。
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況