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

■ このスレッドは過去ログ倉庫に格納されています
2020/11/04(水) 07:10:33.92
競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ

・次スレは>>950

# オンラインジャッジ・コンテストサイト
## 日本語
AtCoder https://atcoder.jp/
yukicoder https://yukicoder.me/
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

Codeforces http://codeforces.com/
CS Academy https://csacademy.com/
Project Euler https://projecteuler.net/

※前スレ
競技プログラミングにハマるプログラマのスレ　32
https://medaka.5ch.net/test/read.cgi/prog/1602443009/
2020/11/26(木) 22:36:19.61
まず>>487から、どうぞ
489仕様書無しさん
垢版 |
2020/11/26(木) 22:37:02.67
「競技プログラミングにハマるプログラマのスレ」であって「競技プログラミングについて語るスレ」ではない
2020/11/26(木) 22:43:22.57
>>460
該当者多すぎる
寒色で寒いより救いがあるけど
2020/11/26(木) 22:46:38.84
きも
2020/11/26(木) 22:52:57.50
厨房は知らんが自治厨はいるようだ
2020/11/26(木) 22:56:44.64
ヲチよりはよっぽど健全だと思う
2020/11/26(木) 23:03:56.68
競プロラノベ更新してくれ
2020/11/26(木) 23:06:27.19
フッフッフ、の元ネタってなんですか？
2020/11/26(木) 23:06:39.96
競プロの話をします
AtCoderにおける潜伏の是非について
・ルールもおかしいし潜伏する人も許せない
・ルールはおかしいが潜伏する人はルールに則っているだけなので責める気はない
・ルールとして問題ない
のどれがボリューム層なんだろう
2020/11/26(木) 23:07:16.40
わかる
2020/11/26(木) 23:08:25.39
>>495
某橙コーダー
2020/11/26(木) 23:20:31.42
Twitterでやってもいいような話題はみんなTwitterでやるに決まってるからなあ
しょうもない話しばかりなのは覇権奪われたSNSのさだめや
2020/11/26(木) 23:34:26.24
某橙って誰だよ
2020/11/26(木) 23:43:23.61
ルールで縛ってないんだから責める方が異常
2020/11/26(木) 23:48:05.02
Nosubするのは自由。Nosubを責めるのも自由
2020/11/27(金) 00:03:46.95
Nosubは内心見下してる
2020/11/27(金) 00:06:43.61
ルール上問題ない行為してる人に文句言う筋合いはない
見下すのは勝手にやってくれ
2020/11/27(金) 00:10:31.93
Nosubバカにしてた奴がレート抜かれて大人しくなるのいいよね
2020/11/27(金) 00:20:09.48
ルール自体に問題があるか否かに言及しろよ
自分は問題あると思うけど良い代替案が思いつかない
2020/11/27(金) 00:23:16.51
問題ないと思ってる
2020/11/27(金) 00:26:27.44
本来吸い取れるレートが吸い取れないから俺より上のやつはノーサブやめて欲しいわ
2020/11/27(金) 00:26:51.29
俺以外のNoSubは禁止しろ
2020/11/27(金) 00:29:05.66
正直でよろしい
2020/11/27(金) 00:30:09.13
言うほど俺ら尊いか？
2020/11/27(金) 00:34:50.02
急になんだよ
2020/11/27(金) 00:51:09.26
尊い(≧∀≦)
2020/11/27(金) 00:54:05.71
よっしゃーー！！！٩(๑❛ᴗ❛๑)۶
2020/11/27(金) 01:05:01.29
Nosubを責めることはルールで禁止されてないから責めて良い
2020/11/27(金) 01:53:28.79
普通に問題のページ開いた瞬間にレジってゲームが始まるシステムじゃだめなのか？
鯖が耐えられない？
2020/11/27(金) 02:47:10.40
複垢で開きます(N回目)
2020/11/27(金) 02:50:13.18
複垢はルールで禁止されてるじゃん
お得意の損害賠償でなんとかするやろ
2020/11/27(金) 02:54:29.16
どう判別すんねん
双子みたいなのもいるし
2020/11/27(金) 03:55:02.81
Codeforces方式でいいじゃん
2020/11/27(金) 03:56:25.52
atcoderのレートがただの数字ならなんでも良かったんだけど
jobsとかで趣味の範囲超えて紐づけようとしているなら会社として対策すべきではあるよね
2020/11/27(金) 04:24:39.28
レートの価値うんたんいうなら替え玉とかの方が深刻じゃね？
コンテストじゃ判定しようがないと思う
2020/11/27(金) 06:46:30.07
替え玉・相談が弾けないのに就活に紐づける自体がなんだかな
実力＋2色差くらいなら面接してもバレなそう
2020/11/27(金) 07:31:23.95
レートが収束するのには時間がかかるからそれまで付き合ってくれるかつ優秀な友達がいたら可能だね
2020/11/27(金) 07:37:36.07
touristにNoSubやめろって言って
2020/11/27(金) 11:08:32.86
Aのサンプルすら通らなくてNoSubしたことならあります・・・
2020/11/27(金) 11:09:53.43
Xor Battleかな
2020/11/27(金) 11:12:50.49
Codeforces方式だと(Aすら解けない場合を除けば)Nosub戦略が取りづらいからあっちのレートの方が実力を正しく反映できてると思う
2020/11/27(金) 11:41:41.38
div1,div2方式ならいいけどdiv3方式は嫌い
2020/11/27(金) 12:09:57.55
レート重視している企業ならそれ相応の面接あるだろうし別に問題ないだろ
就活のweb試験時代別に替え玉もできるし、AtCoderだけの問題ではない
2020/11/27(金) 16:59:02.00
今週はabcなしかぁ
2020/11/27(金) 17:36:28.64
おれたちは尊くないけどABCは尊いよな
2020/11/27(金) 17:40:55.33
ARCも尊いだろ
2020/11/27(金) 18:01:22.58
尊いってそんな意味だっけ
535仕様書無しさん
垢版 |
2020/11/27(金) 18:10:27.56
今週日曜はabcないけどcodeforcesがあるから出よう
茶色でもdiv2 Bくらいまで解けて楽しいと思うよ
2020/11/27(金) 18:27:41.21
(≧д≦)
2020/11/27(金) 18:31:33.17
codeforcesはロシア語分からないから無理だわ
2020/11/27(金) 18:37:01.19
サンプル見て問題推測しろ
数字くらいは読めるだろ
2020/11/27(金) 18:42:06.14
>>537
これ絶妙にネタなのかわからんな
2020/11/27(金) 20:21:04.07
まったく絶妙ではないが
2020/11/27(金) 20:31:54.23
こどふぉの言語切り替えよくわかってなくていつの間にかロシア語onlyになった時どこ押せば元に戻るかわからなかったことがある
2020/11/27(金) 20:56:51.61
パナソニックコンテストがabc186ってことは、それまでにもう一週abcのない週があるのか
2020/11/27(金) 21:09:02.14
来週ABC入ってで再来週ABCなしとかじゃないか
2020/11/27(金) 21:24:19.78
パナソニックコンテストの参加者を増やすためにabc民を飢えさせる作戦か
2020/11/27(金) 21:28:01.73
おれが！おれこれがABCだ！！！
2020/11/27(金) 23:05:15.35
ABC、ARC、AGCの中でRated対象者が一番多いのはARCなんだからARCを欲しがれ
2020/11/27(金) 23:12:50.53
>>546
でもおまえABCより参加者少ないじゃん(　´・ω・｀　)
2020/11/27(金) 23:12:55.42
なおARCの参加者数
2020/11/28(土) 02:31:12.27
長さNの数列のLISの中で辞書順最小のものを復元したいときってO(N*logN)解ある？
O(N^2)しか思いつかん
2020/11/28(土) 02:57:19.68
適切に摂動すれば全要素異なることにしていい
符号反転して逆から見たときのLISを求める
LIS を求める dp をやる時に各要素が配列の何番目を更新したかを覚えておく
あとは LIS になりうる要素で最も大きい奴を貪欲に採用していけばいい
結果を戻せば元の列の辞書順最小のLISが得られる

はず
2020/11/28(土) 03:39:53.26
単に定数を加えることを「摂動」って呼ぶのクソ違和感あるな
力学系以外で使うなとまでは言わないが、相互作用なり何らかの運動なりの源が加わるのが「摂動」であって、対象のモノ自体を手でちょっと動かすのは全く違うよね
元は物理で使われてた言葉のはずだけど、なぜ何のアナロジーもないのにわざわざ同じ言葉を使いたがるのか
2020/11/28(土) 03:49:52.01
誰かが使ってたから使った
微少項を足すといった方が適切？
2020/11/28(土) 09:08:50.60
普通にO(NlogN)のLIS求めたらそれが辞書順最小になるのでは？？

辞書順最小と関係あるか知らんけどLIS戻すやつABCにあったな
2020/11/28(土) 09:28:54.51
>>553
いやそれはならんでしょ
>>550は理解できないが
2020/11/28(土) 09:30:45.46
>>554
ならんわ…
俺がアホだった
2020/11/28(土) 09:47:53.05
あー嘘解法かもしれんが
一旦普通にLISを求めて、それぞれLISのどこを更新したか記録する、LISの長さをxとおく
後ろから見て、最後にLIS[x]を更新したところ、それより手前で最後にLIS[x-1]を更新したところ、…とやって最初まで戻る
とすると復元できてそう？>>550と本質的に同じ気がしてきた
2020/11/28(土) 09:53:10.90
類題みたいなのどっかでなかったっけ、勘違いかもしれん
2020/11/28(土) 10:02:59.93
>>557
K番目のLISを求めるやつならアットコーダーで前出た
普通に難問だから今それを実装するのはオーバーキルだと思うが
2020/11/28(土) 10:58:53.98
グラフ問題を作問するとき、グラフ性を隠すにはどうすればいい？
560仕様書無しさん
垢版 |
2020/11/28(土) 12:15:10.62
>>551
幾何のアルゴリズムのコーナーケースを消すための記号摂動法 (symbolic perturbation) という技法があって、そこから取ったのでは
Yap, C. K. (1990). A geometric consistency theorem for a symbolic perturbation scheme. Journal of Computer and System Sciences, 40(1), 2-18.
値の主要な部分と比べてとても小さな変化がある、という部分が似ている
2020/11/28(土) 13:54:39.97
>>556
それって普通のLIS復元であって辞書順最小のものができる保証なくね？
2020/11/28(土) 13:59:09.08
>>551
お前、さては"面倒臭いヤツ"だな？
2020/11/28(土) 14:08:02.75
>>561
そうかな？
立証も反証もできないから反例あげてくれると助かる
2020/11/28(土) 19:58:48.94
chokudaiまた余計な発言してるな
障碍者を引き合いに出すのは流石にやめとけよ
2020/11/28(土) 20:06:02.36
灰色は池沼、了解
2020/11/28(土) 20:23:20.74
>>563
数列の一番後ろにあるLISが復元されない？
読めてなかったらごめんね
2020/11/28(土) 20:50:32.90
chokudai(高橋 直大) @chokudai
AtCoderでもよく「何色までなら誰でも行けるんですか？」って言われるんだけど、例えば知的障害とかの人がAtCoderで茶色にたどり着くのはほぼ不可能だろうし、それに対して「極端な場合を除く」って言い出したら、どこまでを「極端な場合」として扱うかってだけの話になっちゃうのよね。



知的障害でなければ茶色になれる→茶色になれないのは知的障害と解釈できるな
また曲解だとか言いそうだけど誤解を招かないように書いた文章がこれなら書いたほうが悪いよ
2020/11/28(土) 20:51:52.81
言いたいことはわかるけど言い方が下手だな
2020/11/28(土) 20:52:42.45
知的障害者→茶色になれない
茶色になれる→知的障害者ではない
2020/11/28(土) 20:52:46.99
障害の話ってセンシティブだから触りたくねえ
2020/11/28(土) 20:53:38.82
政治家や有名企業のお偉いさんが言ったら大バッシング確実
AtCoderが無名で良かったな
2020/11/28(土) 20:53:58.95
必要条件十分条件分かってないやつがよく競プロできるな
2020/11/28(土) 20:54:32.73
chokudai本人の思想が露呈してて草
2020/11/28(土) 20:59:23.13
コンテスト中にヲチ的な意味で面白いこと起きませんように
2020/11/28(土) 21:01:21.20
頭の良い人はここで知的障害は持ち出さないでしょってお話
2020/11/28(土) 22:08:08.32
d以降のAC数少なすぎて絶望
おやすみ
2020/11/28(土) 22:11:14.37
3歳児とかにしておけばなあ
2020/11/28(土) 22:12:01.00
touristF通しててさすがだけど先越されてるし3WAだしで微妙にかっちょわるい
2020/11/28(土) 22:18:49.21
捨てセリフ残してツイ消しするかは微妙なラインだな
有名人じゃなくてよかった
2020/11/28(土) 22:22:50.57
知的障害者にもいろいろあるだろ
自閉症ならレッドコーダーにもなれそう
2020/11/28(土) 22:25:52.12
>>567
曲解どころじゃないのですが・・・
2020/11/28(土) 22:33:59.38
一企業の代表がするツイートではないのは確か
2020/11/28(土) 22:42:29.00
>>580
知的障害だとどう考えても無理
高機能自閉症(知的障害のない自閉症)なら一般人と同じくらいには可能性あるかもしれない
584仕様書無しさん
垢版 |
2020/11/28(土) 22:51:40.09
現役アスペだけど緑停滞ですわ・・・
人間力低すぎて無職
2020/11/28(土) 22:53:15.32
緑停滞とか言ってないでARC解け
2020/11/28(土) 22:59:07.63
tourist負けとる
2020/11/28(土) 23:02:30.35
C、WA1つ取れんかった
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。