競技プログラミングにハマるプログラマのスレ 33
レス数が1000を超えています。これ以上書き込みはできません。
テンプレ続き
# 書籍
プログラミングコンテストチャレンジブック (蟻本)
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (AOJ本, TLE本, 渦巻本)
最強最速アルゴリズマー養成講座 (チーター本)
問題解決力を鍛える!アルゴリズムとデータ構造（けんちょん本）
# 日本人競技プログラマ
Twitter 競技プログラマリスト
(現在有効なリスト募集中)
TopCoder Single Round Match (SRM) のランキング
https://community.topcoder.com/tc?cc=392&;sc=&sd=&cc=392&module=AlgoRank&nr=200&sr=
TopCoder Marathon Match (MM) ランキング
https://community.topcoder.com/longcontest/stats/?module=CoderRank&;cc=392
Codeforces ランキング
http://codeforces.com/ratings/country/Japan Kingのメンツ豪華スギィ！！いきますよーいくいく… 応援3チーム中1チームしか通過できなかった
競争が熾烈すぎるお… てかyutaka1999まだ大学生なのか…
既に何年競プロ界にいるのか… 流石に優勝するんじゃないか？
こんなレベルのチームなかなか出ないでしょ いつも問題出してる人たちだ！！みたいな感想を抱きました（灰並感） HIR180さんて初めて見た
writerやってる人？ 上位もっと東京大学で占めるかと思ってた
17チームも出てトップ10に2チームしか入ってないんだ chokudai(高橋 直大) @chokudai
「不正選挙」ってTwitterの面白人材を発掘するワードだと思ってたのに、今日は割とマジで語られていてびっくりですよ。 （真偽については知らない）
12:53 PM · Nov 5, 2020·Twitter for Android yutaka1999って1999年生まれなのかな？ 競技プログラミングは数学オリンピック、受験勉強より役立つな yutaka1999
数オリ情オリで一位経験あるからrng_58以来の逸材 今夜のABCに備えて過去問解いてたらこんな時間になってもうた。
今日はもうむりぽ EなんちゃらくんとSQUAREなんちゃらくんはどっちも高3っしょ今 双子の他にもう1人くらい高3に橙いなかったっけ？
みんな東大行くのかな、また最強世代作ってほしいな >>38
tatyamさんは今大学1年か
QCFiumさんは高1？2？で橙だね >>46
それは誤解
藤井君は実はモテるタイプなんやで AtCoder True Beginner Contest Cがテストケース1つだけ通らなかったんですけど何ですか… H行W列の問題でテストケースがH==Wしかなかったら
ちょっとだけ嫌なのは俺だけかい >>51
ワシも最初, 全体の余り求めて, 各桁の余りが1のやつ, 2のやつカウントしてやったら, all_12.txtだけ通らんかった
とりあえずerase総当りで通した
>>52
それは対処したんやけどね >>52
それは対処してるつもりですが…
（全桁取り除くとサンプルの入力例4で引っかかるので）
>>54
自分はrandom_00.txtだけWAでした しかし、なぜこんなにlump類題何回も出すのか…見飽きたよ… グラフならUnion findめっちゃでてるやん
最近迷路出てないからそろそろ出して欲しいな Cを嘘解法で通してしまった
消す桁が連続している必要があると誤読していた
「131」とかで落ちるはずだけど、テストケース弱いのかな >>58
場合分けじゃなくて全探索したので抜けではなさそうです
調べても分からないのでテストケース公開を待ちます… てかEってランプから上下左右にランプ or 壁 or 端まで延ばしてカウントするだけでも
通るよね pastebinゲストアカウント使えば匿名でコード共有できるんじゃないかな >>69
ランプを障害物扱いすれば通る
スルーするとTLE >>73
なるほどPythonとC++の兼ね合いでTLE設定難しかったのかなあ。C++だったら何でもない問題だな >>72
各マスは最大4回しかチェックされないからO(HW)で済む >>66
すみません、まさにこれでした…
レスくれた方有難うございました >>74
そもそもランプを障害物扱いするなら1マスあたり各方向1回ずつしか調べないからO(HW)な感じで済む
多分Pythonでも同じ >>75
なるほど。ってか解説読んでなかったわ。すまん
想定も壁だけじゃなくてライトも障害物とみなせば良いってだけの問題だったのか。。
TLE 2.5secなのも謎だなあ
>>76
取り除いてmodが0になったときの取り除いた数の最小値を持てば多分通りそうだね >>77
Pythonとか関係なかったな。すまん。 >>81
そうだねえ。
各ランプから上下左右に壁 or 端まで延ばしてカウントするだけでC++なら通る >>45
NTTがスポンサーなんだな
コラかと思った そっか、c++とpythonでだいぶdiff変わる問題だったのかな？ 言うてランプとぶつかったら止めても良いという発想はすぐだろうし、そんなに変わらないかも? pythonでN回ループ+ランプで止めるで通る？ rubyではランプで止めてもACが10から12になっただけだった 上の方がどうなってるかは分からないけど
緑のレベル高すぎない けんちゃんはNTT持ち株だからNTTDataじゃないやろ？ 別のやつと勘違いしてたようだ、だれと勘違いしたんだろ 最近のABCはEが簡単だな
Bは難しくなってて良いと思うが Eは1400が目安らしいからちょい簡単に偏ってるかもね AtCoder,いつになったら教育的コースを公開してくれるんですかね
構想を語ってから大分経つけど、結局立ち消えになったのかな? 昨日のEって茶色難易度もありえそう
できなかった人の中にもとりあえず提出していたら通った人も多いんじゃないか EぱいそんだとTLEでC++だと通るコードってどんなん？
単に明かり総当たりだとC++でもTLEしたんすけど けんちゃんdataなんだ
人気企業で強くてすごすぎ
スポンサー活動かなんかやってるの？ こんなところで聞かずにTwitterで本人に聞いてこいよ パソコン甲子園、解説を公開してくれ
たった年に1回の行事じゃん? >>108
明かり総当り https://pastebin.com/mZMZTxGZ
150msとかだから, pythonでもたぶん通る 明かり総当たりっていうのは明かりごとにブロックにぶつかるまで（明かりはブロック扱いせずスルーする）チェックすること
>>114みたいに明かりをブロック扱いするならそりゃPythonでも通るよ高々O(HW+α)だし そんな変わらないように見えて、あかりが増えるほど止めるところが増えるしあかりが少なければ止める必要ないのか。なるほどおもろい こういうのは極端な例を考えると良くて、横一列全てのマスにランプがあるとオーダー変わるでしょ あかりをブロック扱いすると計算量落ちるの思いつかんかったわ ブロックだけでも余分なことしなければギリいける気がする 2secだとO(HW+N+M)がpythonで通らない可能性あったとかじゃない log つけるって何だ？ set で削除していくとかか？ おれlog解法したわ
vector<set<int>> vsh(H) とvector<set<int>> vsw(W)
それぞれにぶたんして、どっかしらに光があればカウント
1400msくらい AtCoder,就職仲介をメインにしないと経営厳しくね?
コロナ禍は少なくともあと5年は続きそうだし、
社員にかなりの給料払ってるっぽいし 10万は流石に安いか
100万でも買う人大量にいそう 買うわけねえだろw
1000円でも買わんわなんの意味もない レートが実力を反映しないなら広告出す企業もいなくなるわけだが レートの信用ってまるで通貨みたいだな
何の取引に使えるんだろう 仮想通貨のマイニング↔ratedコンテストの参加
仮想通貨での取引↔自己アピール、就職 LINEでアドバイスもらったり、学生はフツーにやってそう 10万でビジネスホテルに連泊して家事を忘れることで精進に集中する ハル研プロコンはもう終わりそうだからパスするとして
11/13からのCodinGameに出るか悩むな サンプルガチャとか実装されたらどばどばつぎ込んでしまいそう 出現確率
1% O(2^N)のアルゴリズムで通る激弱サンプル
6% O(N^2)で通る弱いサンプル
93% O(NlogN)で通る普通のサンプル 24時からCodinGameでゲームAIコンテストが始まるぞ PASTの過去問はなかなか質がいいような気がするね
もっとみんな解くべきですよ PASTはアルゴリズムの問題にせざるを得なく算数パズルの方を向いてないので、明らかに質が良いですね え、むしろPASTみたいな問題ばかりやってたら競プロ嫌いになるだろ 算数パズルは解けると楽しいけど解けないと嫌になるんだよ 算数パズルはまだ良いけどただの算数問は解けても面白くないな PASTみたいなのabcやarcで出されたら嫌すぎる past上級レベルだからかそんな問題の違い分からないな maroonさんのパズルは解けなくても面白いぞ
unratedな雑魚もAだけは解こうね 2400って珍しいん？
前回2200だからあんま変わらないような >>169
World Tour Finalsを除けば最高得点タイ
これまで2400点問題は3問しかない 今日はAGCなので、自作スクリプトの宣伝します
AtCoder Easy Test
・サンプルをボタンひとつで試すことができます（ABCの方が役に立ちそう）
・問題の画面で入力をテストできます
https://greasyfork.org/ja/scripts/415946-atcoder-easy-test
AtCoder Anonymizer
・学校や職場からAtCoderに参加したいが、垢は知られたくないという場合有用です
https://greasyfork.org/ja/scripts/413425-atcoder-anonymizer せっかく用意した難問が誰にも解かれないと寂しいから、毎回これくらいの時間制限にすればいいよね 9時スタートで日またぐのか。。
参加せず順位表眺めてるわ Apiadニキが200分かけてFだけ解いて去っていくやつありそう
もちろん唯一のAC 某社、ほんとに経営が心配
P社による救済があればいいけど 現時点でwriterの2人のレートが全く同じってことに気づいた APC001は23時から300分コンテストだぞ
0時20分終了くらいで騒ぐな 中国の上位勢みんな中高生じゃん、こわ
ロシアは古株が多くて落ち着く 前日に用事が入ったとかはないの？参加登録はいつしたんだろう 開始後10秒くらい経ってかられじってたから少なくとも1問は問題見たはず 今なら提出するだけでtouristよりも順位上回れるぞ 7時間前にコドフォにはアクセスしとるんだがなtourist 解説見てもよく分かんないけど2問解けた
＼(^-^)／ chokudaiのatcoderアイコンがいつのまにか実写になってる・・ やっぱAGCは難易度とパフォが合ってない気がするんだよなぁ まあ青以下は対象じゃないからね(運営も「本来は赤対象のコンテストだから最初はR2000を下限にしてたけど、レート補正とかレート変動が追いついてないとかで実力あるけど出られない人がかわいそうなのでABC一発で達成できる1200を下限にしてる」ってどっかに書いてたはず) Aパスで実験したら1/iの和になってたから適当にやったら通った SとTが一致してるかどうかをXORと言ってるだけじゃない？ Cはまだ解けてないから知らんけどBはかなり軽くないか
vectorに1の場所突っ込んで1個削除か2個削除を繰り返すだけだし なんでAとB逆じゃなかったんかな。2000以上だとAとBのdiff逆転するんやろか。実際強い人はみんな簡単に解けてるみたいだし 俺は黄色だけど、Bが緑なの信じられん
自分だったら事前にAとB比較してBのほうが簡単と評価することは無いと思う A で詰まった人間だから偉そうなこと言えないんだけど解法わかった状態でみると難度判定を A < B とするのもわかるんだよな
[操作回数の期待値] -> [各頂点が操作として使用される確率の和] の言い換えは典型だし確率自体は容易に求まるし Bは変な実装やって時間食ってたわ、確かにBはそこまで重くないな
AとBの難易度は絶対逆とは思ったが、青と緑ほど差があるとは思わんかった
この順番にしたのはAは典型寄りという判断かな
Bは緑に近いギリ水でAは水後半ぐらいだと解いた直後は思った Aみたいな、ある一箇所に気づくorそれを知っていることが本質な問題は難易度がぶれやすいんだろうな
最上位層からすれば当然のように知っているから、簡単と判定されそう
個人的にはCですらAより易しいと感じた >>233
解説にあるように
集合のサイズが
小さい方→大きい方
でうつしてかんとあかんで やり方は合ってたことが判明
ただしクエリ内にrep(i,n)の8文字消し忘れてた… ここって水色とか青くらいの人が一番多いかな？
Bもできなかったから恥ずかしい マージテクは水色後半diffくらいだと思ったよ
今年もどっかのコンテストで見た気がするし ABC-Fでマージテク使える問題あったな
マージテク自体はUnionFindに使われてるし知る機会はいくらでもある 昨日のAGCのAは気づかないとひたすらいろんなグラフ関連のアルゴリズム持ち出してあーだこーだやりだしてドツボにはまるのが難しいと思う 遂にPCK2019,2020本選の解説が
ｷﾀ━━━━━━━━(ﾟ∀ﾟ)━━━━━━━━!!
今日は祭りじゃ!! アルゴリズム名由来の変数名とか関数名って仕事で使えるのか？ >>252
場合によるでしょ
2種類のアルゴリズムの性能評価をするときとかは普通に使う またchokudaiが気に食わないツイート引用してお気持ち表明してる 競技プログラミングで平均くらいのレベル目指したいんだがなにすればいい？
ちなみにスッキリわかるJava入門はだけやったレベル >>255
qsortの内部実装はクイックソートとは限らない定期 >>258
ABCの過去問をAから順に埋めていけばいいよ
Aが簡単すぎると思ったらBからでもいい
知らんアルゴリズムが出てきたらその都度Qiitaとか見ればいい AGCの過去問をFから順に埋めていけばいいよ
Fが難しすぎると思ったらEからでもいい 競プロの平均なら黄色、一般プログラマの平均なら茶色って印象 分布に偏りがあるから代表値として平均値を選ぶのはよくない AGC生えてるけどりんごさんAtCoderから居なくなるのかこれ 競プロ辞める説
Admin やめてコンテスタントになる説 2000〜じゃん
rngさんがかんがえたさいきょうのセットなら楽しみ ratedのくせに4時間かけて1問もわからないを2回するのか まあ日本有数の頭脳をお遊びのサイトに遊ばせておくのはもったいないという考え方もある PFN ってバリバリ機械学習マンしか採ってないイメージ 機械学習マンを採用するとして、青を求めるとどうみてもスゴイ人を逃す >>277
MN-3の記事とか読めば分かるけど違う畑の人も結構いるな
低レイヤ最適化マンとか 人権がないなどの発言はしないように心がけています。
と発言してたりんごさんのお別れコンが大多数のユーザ参加禁止っていう いやレートがつかないってだけで参加するのは自由だろ
…と思ってコンテストページ見たら違ってて草 4時間を二日連続とかもうむちゃくちゃや
2500点問題とか出てきそう
https://atcoder.jp/contests/ rng 58 でツイッター検索するとおもろい
ガチでsnukeと間違ってる奴がいたり まさか、2日8時間かけて1問も解かれないとは・・・という未来余地 業務としての競プロは競プロしかできない人がやる方がいいのでは すぬけさんとりんごさんを見分けられない事をここに告白します まあ似てるしな でもりんごさんはあんま表に出ないし今頃コロナ禍でヒゲぼうぼうになってんじゃない？ >>299
writerが作った問題をaccept/rejectする
acceptした問題を何点にするか決める
コンテスト自体のシステム考える
とかじゃない？ つまりadminをやっている限り参加者にはなれないわけか で、ひげが生えてるのがりんゴリラさんと…よし！覚えた りんごがすぬけに似てると聞いて昔の動画あさってみたけどだいぶちがうじゃねーか！ んで結局
ひげの生えてるゴリラがすぬけなの？りんごなの？(´・ω・`) コロナ渦で髪が伸びるのはわかるが髭は自宅で剃ればいいじゃねーか C++とpythonどっちを使えるようになった方がいいんだ
Pythonは実行時間遅いけど書きやすいんだよな pythonはpypyあるからかなり長々と使える印象がある。そういう意味では好きな方でいいんじゃないかと思う diff3200以下はPython/PyPyで解けるからPythonでおｋ pythonで解ける（定数倍高速化が必要でないとは言っていない） Rustは何学ぼうって言ってる人にすすめるものではないよな 仕事してたら、その言語
機械学習系行きたいならpython
それら以外ならC++
どや 競プロで使う範囲のC++はそれほどひどい言語ではない けいぷろとかミニスクリプトで使う範囲ならいい言語なだけでpythonも超次元ウンコ言語だけどな(´・ω・`) とりあえず、使い慣れてるpython使っていこうと思う
ありがとう あ、Rubyもええぞ
だいたいのことを簡潔に書けるし、タイプ量も少ないし、Pythonより速いこともあるから Rubyは上に行こうと思ったら話にならん。pypyのあるpythonとは比べ物にならない PyPyはNumPy使えないから使ったことないわ
CPythonでもNumbaでJITコンパイルしたら十分速いし Java erやC# erだってときどき文句言いながらC++で書いたりするくらいなんだからPythonでいけるって主張は嘘ではないだろうが相当無理してる発言だと思うな そこまでの域に達する人ほとんどいないから。とはいえ弱い人ほど速い言語を使うべきというのもまた真実 想定O(NlogN)のところをO(Nsqrt(N))で犯罪するのはC++erの特権 それくらいの違いならAtCoderでJava程度の速さがあればだいたい通るよ
ベクトル化が効きすぎてうっかりO(N^2)が通ってしまう事件とかはほぼC++に限られるが 遅延セグ木だと3Nのメモリが要るんだっけ
平方分割だと、N+√N? メモリ3NじゃMLEして時間N√NでTLEしないなんて問題作れるん？ PyPyやJavaを犠牲にすることでC++で遅延セグ木を落とせるようになる
ダメだろ 平方分割が想定の問題ってのはもっと複雑なデータを載せてるから 遅延セグ木には何でも載るわけじゃないのか
半群→モノイドにする一般的なテクみたいに、何らかの変形をしても無理か？ 平方分割が想定解な問題はセグ木に載らないというよりは載せても計算量落ちないパターンが多い
https://atcoder.jp/contests/yahoo-procon2017-final/tasks/yahoo_procon2017_final_c
この問題なんかはセグ木に載せようと思えば載せられるが愚直なO(NQ)から計算量落ちないし旨味がない bまでの早解きとかやっててもしゃあないな
c解けるようにならんとレベル上がらん 樹形図書いて70ACまではいったが…
16通りじっくり考えるには時間が足らず Eが700点はひどい
Um_nikも解けてないじゃん Python使いで赤２人とかのレベル？
赤ってほんとにすごいんだな >>342
マジ？うまいこと載せれたらいけない？と思ったが確かに、区間加算→倍数を数えるはうまいこと合成できないな
こういうのは平方分割限定か 16通りとか言ってるやつ場合分けのセンス無さ過ぎだろ いやごめんF<Dはないわ多分
明日D真面目に考えよう Atcoder ProblemsだとAGC5Aは1054、ARC108Bは681
現代の茶色は過去の緑レベルだよ、おめでとう 茶色が就職に必要なコーディング力だったのに、灰色になったので使えなくなった >>172
C++のバージョンがC++14のようですが, C++17にできませんか? C、解説通りに場合分けしてるつもりだけどWAが3つ取れませんでした
コーナーケースみたいな入力例があったら教えて欲しいです >>366
提出コードにバグないかい？
自分も最初は4個だけWAやったけど<と<=間違えてるのに気付いてACしたで。 1 1 100 101
1 1 6 1(これはテストケースにはないらしい) >>368
どっちも2が出力されます
>>367
バグかもしれません Dで混乱して時間使いすぎた
Fは解けたけどE時間足らず… まあ3完を目指す場合は、今回のセットだとCに100分ほぼ費やせるからね
前の問題がもう少し難しかったりしたらもう少し正答率下がるよ F は半分全列挙やるだけで既出がどうこう言えるような問題ではない気がする
知らなけりゃ解けないかググるしかないだろうからまあ F になるんかな C嘘で通した人結構いるらしいな
テストケース作った人のサボりか？ c問題、解説の abs(r+c)<=3 のケースだけ思いつかなかったなぁ。式変形自体は理解できるけど、直感的にどういうケースになるのか分かんなかった D,E,Fは全部ド典型だけど全部解ければ青パフォか
難易度としてはいいのかな こどふぉみたいにマルチテストケースにすればいいんだよ 場合分けが本質の問題で嘘が通るのはちょっとなあと思ってしまう マルチケースの入出力書く方が難しいなんてことが起こりうるがまあ C, D ならそんなことは起きないか テストがザルになる位なら無理してABC開催しないでもいいんじゃないか 今回のCはランダムでテストケース生成しちゃうとほぼ3が答えになって2や1になる確率なんて10^9分の1とかになりそうだけど、手で作ったらしいテストケースが2個しかないのは流石に？って感じ パリティで2か3になる以外の確率が10^9分の1
に訂正 >>368
これ以外だと特にないでしょうか
探し方とかでもいいんですが・・ 1 1 100 101 (答え2)
1 1 2 5 (答え2)
1 1 2 3 (答え1)
この辺とか? 1 1 x y (x <= 20, y <= 20) くらいを全部調べて表示してみよう >>392
ありがとうございます。全部正しいです
>>393
それも試したのですが、解説コードと(100, 100)まで比べても結果同じでした
別の方法を考えてみます。。ありがとうございました 100,100まで合うならオーバーフローじゃね
0 0 10^9 10^9-p (pは適当に変える)
とか 他人のACコード拝借して乱択で突き合わせてみるという方法もあるがコンテスト中にできる方法が知りたい感じだよなあ
一回書き直すとかたまに効くがただの浪費になることもあるしうーん >>381
中国勢がグループでコードを共有してるらしい ここ見る前は2ch競プロスレなんてどうせ不正やってるだろと思ってたけど別にそうでもなかったな 実際2chみたいな匿名性のあるところでコンテスト中の解法リークとか出たらどうすんだろうな
開示して損害賠償請求されるのか？ 少し前に似た話が話題になりましたが、chokudaiさんがやろうとしないのでありません 過去のDP問題を解いてて疑問に思ったんですが配列の大きさは一般的な問題でどの辺りが限界なんでしょうか
解けなかった解答を見たら合計サイズが10^6で驚いてそれ以上のもあるのか気になりました 傾向を知るより、TLやメモリ制約から考えるとよいよ
たとえば64bitのデータが10^7個あると10^7 * 8e-6 = 80(MB)で、
このくらいは普通のTL、MLでまったく問題ないのでよくある
これが10^8だと800MBになる上にTLも怪しくなってくるので、2sec/1GBで想定になることはほとんどない >>408
メモリ制限普段中々気にすることないので盲点になってました…
明快な解答ありがとうございます 強い人は解説ACしないと言ってる事が多いけど
凡人がその真似をすると高難易度帯が一切解けないんだよなあ 配列のサイズと型を入力すると何MBか教えてくれるうしというサイトがおすすめです https://ei1333.github.io/beet/memory.html
ここに
for(;;)alert("\u7d42\u308f\u3089\u306a\u3044\u3046\u3057\u301c")
って入力してみ？ >>413
特殊な文字でない限り、エスケープシーケンスを使う必要はないよ
for(;;)alert("終わらないうし〜")
でよいかと 今って無限アラートは逮捕されるし前例もあるんだよなあ 初回からレート単調増加のまま色変記事書きました！wって言われても煽りにしか取れないよ レート単調増加って元々の実力に収束してるだけだからな AtCoderはレート変動少ないから変動が精進に追いついてない人は結構いると思う
Codeforcesくらい変動大きくするとそれはそれでレートに就活アピールとしての価値を持たせづらくなるから仕方ないけど 最初から持ってる実力には10回も参加すればレートが追い付くのでそれ以降も単調増加してるならなんらかの能力が伸びてる証拠 >>411
そんなもん sizeof*配列の長さで計算しろや >>359
想定解法はほぼ同じようだけど、除外するのが2文字より3文字の方が難易度は上がりそう(別解が少ない分) もうすぐDiv.3 です
華麗に全完してさっさと寝よう こいつはどんな反応を求めて「男と女どっち？」なんて寒い発言したんだろうな
「こりゃ男だろｗ」みたいな感じで乗って欲しかったのかな？ 文をよく見ると問われてるのは｢男｣と｢女｣のいずれか。
｢こいつはどんな反応を求めて「男と女どっち？」なんて寒い発言したんだろうな｣などはWA 気になってツイートある程度遡ってみたけど結局よく分からなかった
その後冷静になってみたらどっちでも自分の人生には全く関係がないことにきがついた そんなに界隈に女を増やしたければ、彼女作って布教すればいいと思うんだけど、それをしない理由は？ どこに女を増やしたいとか書いてあるんだろう
読解力灰色マンかな 天才東大生の遊び場が発障ガイジのスラムになってくの悲しいなあ 社長もこの人もなんだけど、
滑舌悪いのに動画を配信するのはなんでなん？
自分に向いてない事をするのって頭悪くないか 電車内とかやることない時に青〜黄diffの問題考えてる時間が一番楽しい 競技プログラミングスレあるんだと思って覗いた
Twitterみたいに和気あいあいかと思ったら
まあこんな流れだよね...うん 俺は和気あいあいとした競プロスレの方がいいです
少なくともヲチ要素はいらん 俺はギスギスした匿名の叩きあい、煽りあいがしたいからもっとやれ 煽り合いと言ってもTwitterから火種取ってくるだけじゃん Twitterも寒い内輪ノリで盛り上がってるだけじゃね？ みんな尊い(≧д≦)！！
チクチクことばやめて(≧д≦)ンァー！！ お前らみたいな匿名でしか物言えない臆病者よりTwitterで堂々とイキッてる奴の方が俺は好感持てるなｗ 競プロerが陰湿インターネットマンじゃないわけないだろ エリート中高生様は大切にしたいお客様ですから、少しでも受験のプラスになるような問題にしてあげないとねぇ 他の授業中も内職して数学ばっかりやってきたような数学アスペのためのサイトだからな このスレにも厨房居るのかな。
10年ROMってろ逝ってヨシ 461とかが厨房じゃねえの
というか厨房じゃないと救いがない こういうのやるのは厨房とかじゃなくて救いようのないおっさんな気がする 音ゲー板と遊戯王板見てる
冷静に考えるとかなり気持ち悪いな なんで競プロのひとたち音ゲー好きなの
アスペ特有のもの？ 5ch やってる時点で皆同類よ多分
俺は小規模MMO板とライトノベル板読んでるからより酷い なんか伸びてると思ったら嫌儲だの全く競プロ関係ないじゃん
ヲチでも良いからせめて競プロに関連した話をしろ 「競技プログラミングにハマるプログラマのスレ」であって「競技プログラミングについて語るスレ」ではない >>460
該当者多すぎる
寒色で寒いより救いがあるけど 競プロの話をします
AtCoderにおける潜伏の是非について
・ルールもおかしいし潜伏する人も許せない
・ルールはおかしいが潜伏する人はルールに則っているだけなので責める気はない
・ルールとして問題ない
のどれがボリューム層なんだろう Twitterでやってもいいような話題はみんなTwitterでやるに決まってるからなあ
しょうもない話しばかりなのは覇権奪われたSNSのさだめや Nosubするのは自由。Nosubを責めるのも自由 ルール上問題ない行為してる人に文句言う筋合いはない
見下すのは勝手にやってくれ Nosubバカにしてた奴がレート抜かれて大人しくなるのいいよね ルール自体に問題があるか否かに言及しろよ
自分は問題あると思うけど良い代替案が思いつかない 本来吸い取れるレートが吸い取れないから俺より上のやつはノーサブやめて欲しいわ よっしゃーー！！！٩(๑❛ᴗ❛๑)۶ Nosubを責めることはルールで禁止されてないから責めて良い 普通に問題のページ開いた瞬間にレジってゲームが始まるシステムじゃだめなのか？
鯖が耐えられない？ 複垢はルールで禁止されてるじゃん
お得意の損害賠償でなんとかするやろ atcoderのレートがただの数字ならなんでも良かったんだけど
jobsとかで趣味の範囲超えて紐づけようとしているなら会社として対策すべきではあるよね レートの価値うんたんいうなら替え玉とかの方が深刻じゃね？
コンテストじゃ判定しようがないと思う 替え玉・相談が弾けないのに就活に紐づける自体がなんだかな
実力＋2色差くらいなら面接してもバレなそう レートが収束するのには時間がかかるからそれまで付き合ってくれるかつ優秀な友達がいたら可能だね Aのサンプルすら通らなくてNoSubしたことならあります・・・ Codeforces方式だと(Aすら解けない場合を除けば)Nosub戦略が取りづらいからあっちのレートの方が実力を正しく反映できてると思う div1,div2方式ならいいけどdiv3方式は嫌い レート重視している企業ならそれ相応の面接あるだろうし別に問題ないだろ
就活のweb試験時代別に替え玉もできるし、AtCoderだけの問題ではない 今週日曜はabcないけどcodeforcesがあるから出よう
茶色でもdiv2 Bくらいまで解けて楽しいと思うよ codeforcesはロシア語分からないから無理だわ こどふぉの言語切り替えよくわかってなくていつの間にかロシア語onlyになった時どこ押せば元に戻るかわからなかったことがある パナソニックコンテストがabc186ってことは、それまでにもう一週abcのない週があるのか パナソニックコンテストの参加者を増やすためにabc民を飢えさせる作戦か ABC、ARC、AGCの中でRated対象者が一番多いのはARCなんだからARCを欲しがれ >>546
でもおまえABCより参加者少ないじゃん( ´・ω・｀ ) 長さNの数列のLISの中で辞書順最小のものを復元したいときってO(N*logN)解ある？
O(N^2)しか思いつかん 適切に摂動すれば全要素異なることにしていい
符号反転して逆から見たときのLISを求める
LIS を求める dp をやる時に各要素が配列の何番目を更新したかを覚えておく
あとは LIS になりうる要素で最も大きい奴を貪欲に採用していけばいい
結果を戻せば元の列の辞書順最小のLISが得られる
はず 単に定数を加えることを「摂動」って呼ぶのクソ違和感あるな
力学系以外で使うなとまでは言わないが、相互作用なり何らかの運動なりの源が加わるのが「摂動」であって、対象のモノ自体を手でちょっと動かすのは全く違うよね
元は物理で使われてた言葉のはずだけど、なぜ何のアナロジーもないのにわざわざ同じ言葉を使いたがるのか 誰かが使ってたから使った
微少項を足すといった方が適切？ 普通にO(NlogN)のLIS求めたらそれが辞書順最小になるのでは？？
辞書順最小と関係あるか知らんけどLIS戻すやつABCにあったな >>553
いやそれはならんでしょ
>>550は理解できないが あー嘘解法かもしれんが
一旦普通にLISを求めて、それぞれLISのどこを更新したか記録する、LISの長さをxとおく
後ろから見て、最後にLIS[x]を更新したところ、それより手前で最後にLIS[x-1]を更新したところ、…とやって最初まで戻る
とすると復元できてそう？>>550と本質的に同じ気がしてきた 類題みたいなのどっかでなかったっけ、勘違いかもしれん >>557
K番目のLISを求めるやつならアットコーダーで前出た
普通に難問だから今それを実装するのはオーバーキルだと思うが グラフ問題を作問するとき、グラフ性を隠すにはどうすればいい？ >>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.
値の主要な部分と比べてとても小さな変化がある、という部分が似ている >>556
それって普通のLIS復元であって辞書順最小のものができる保証なくね？ >>561
そうかな？
立証も反証もできないから反例あげてくれると助かる chokudaiまた余計な発言してるな
障碍者を引き合いに出すのは流石にやめとけよ >>563
数列の一番後ろにあるLISが復元されない？
読めてなかったらごめんね chokudai(高橋 直大) @chokudai
AtCoderでもよく「何色までなら誰でも行けるんですか？」って言われるんだけど、例えば知的障害とかの人がAtCoderで茶色にたどり着くのはほぼ不可能だろうし、それに対して「極端な場合を除く」って言い出したら、どこまでを「極端な場合」として扱うかってだけの話になっちゃうのよね。
知的障害でなければ茶色になれる→茶色になれないのは知的障害と解釈できるな
また曲解だとか言いそうだけど誤解を招かないように書いた文章がこれなら書いたほうが悪いよ 知的障害者→茶色になれない
茶色になれる→知的障害者ではない 政治家や有名企業のお偉いさんが言ったら大バッシング確実
AtCoderが無名で良かったな 必要条件十分条件分かってないやつがよく競プロできるな コンテスト中にヲチ的な意味で面白いこと起きませんように 頭の良い人はここで知的障害は持ち出さないでしょってお話 touristF通しててさすがだけど先越されてるし3WAだしで微妙にかっちょわるい 捨てセリフ残してツイ消しするかは微妙なラインだな
有名人じゃなくてよかった 知的障害者にもいろいろあるだろ
自閉症ならレッドコーダーにもなれそう >>580
知的障害だとどう考えても無理
高機能自閉症(知的障害のない自閉症)なら一般人と同じくらいには可能性あるかもしれない 現役アスペだけど緑停滞ですわ・・・
人間力低すぎて無職 茶色のワイ、c問題必死こいてようやく時間ギリギリ間に合ったと会心の思いでいたら入力例3につまづく。なるほど2の100乗ね、みんなそこで戦ってたのね… touristがつまづくd問題とかfの解かれ具合とか、AGCがこれくらいの難易度でええんちゃうの？ Bでこれであってる?
ジャッジは通った
ll n;
cin >> n;
ll k = sqrt(2 * (n + 1));
if (k * (k + 1) / 2 > n + 1) k--;
cout << n - k + 1 << '\n'; 3完でも遅すぎる…
俺も誤差修正で通したけどにぶたん思い付かないのが修行不足 >>591
賢いなぁ、k(k+1)だから一つ誤差調整すればいいんだ。二次方程式の解の公式で解いたけど結局こっちも誤差調整必要だった CとDの間2色飛ばしてて笑う
これが寒色虐殺回ですか 寒色だがCまで解いただけで自己最高パフォでちゃったぞ satashun
QCFium
gazelle
kotamanegi
nwin
drken
KoD
aajisaka
wafrelka
maze1230
flowlight
pachicobue
autumn_eel
ichyo
mencotton
tabr
jell
Mitarushi
TAB
tsutaj
startcpp
opt
simkaren
TumoiYorozu
kanpurin
face4
soshun
UminchuR
kyuridenamida
Thistle
holeguma
hs484 今週、来週、再来週のうち一回しかないんだから明日はないだろう。多分来週 いっそのこと過去の回数まとめてランキングにでもしたらどうだ AGCのNosubリスト作った方が面白いと思うで
(赤コーダーへの印象が変わるかも) 女だの男だのどうでもいい
NoSubする奴かしない奴かが重要だ NoSubするって事は、提出するよりもレートの方が大事って事だよな、、、 色変直後はレートが可愛くてNosub したことあったが最近は色落ちしたから考えなしに提出してるわ 同じ話何回も繰り返すおじいちゃんかな
Nosub率表示するユーザースクリプトでも作ったら NoSub戦略を極めてたら、いつの間にか赤コーダーになってた件
「俺、何かしちゃいました？」 SRM って対応言語増える予定ないのかな
出るためには言語勉強しないといけないっぽくてめんどい コンテスト開始時刻までに参加登録したらRated
開始以降に登録したらUnratedでば全て解決だと思うがそんな難しいのか？
事前登録が出来なくなるとか言うけど事前登録が出来ると何が嬉しいのか解らん
遅刻参加はこのスマホ時代、参加登録位は移動中出来るだろうし ようやくTwitterで>>603が燃え始めてんな
案の定というか何というか 問題開けたらRatedはDiv分けされてる形式じゃないと機能しないんやで
Nosubの代わりに別垢作って問題見るのがやったもん勝ちになる >>625
複垢で問題覗いても本垢がRated参加してないと意味無いから有効そう 気持ち良く競技に集中出来る環境を作って欲しいとは思う。出来る限り 未証明エスパーはレートに執着しすぎてて単純にダサい エスパーは早押しクイズで問題文が全部読まれる前に答えるようなもん >>632
問題開けたらRatedだと、サブ垢で問題開けて問題解いて、解けたら本垢で問題開けて即提出。
みたいなことが出来るってことやん。
脳みそみそ サブ垢で解いてokだったら本垢で提出って今でもできるけどな >>637
問題開けたらじゃなくて開始時刻までに参加登録ボタンを押したらRated
それだとサブ垢で問題見る意味が無い >>550
元の列を変更するのと符号反転はなぜ必要ですか？
>>556
僕もこれだと一番最後のLISが返るだけだと思います そもそもNosubってそんなに得かね
例えば「90分でDまで解けたときだけ提出する」と決めて、
40分でCまで解けた(提出せず)
80分でDを解けた→4つまとめて提出
としたとき、そのDが間違っていて終了までにACできなかった場合、80分でCまで解けた扱いになり爆下がりする
そんなリスク抱えるくらいなら解けたものからさっさと出してった方が良いのでは
よっぽど早解きが苦手でない限り 赤未満は競プロerじゃないから晒さないルールみたいのなかったっけ “90分” とかいう絶対的な時間ではなく、他参加者の提出率や予測レートを見て
提出するだろうし、自信ないときは提出しないだけだからWA率も少なそう >>641
最後のLIS=辞書順最小のLISではないのかな？
反例が作れないから教えて欲しい
>>642
リスクがあるのはそうだよ
だから数え上げででかいサンプルがあるみたいな、嘘解法を生みにくい問題があるとき特に有効 ぶっちゃけこんなシステムを何年も放置してるのが悪い Nosubは運営がしばらく対策してないし公式でもするなと言われてない以上別にやってもいいだろって思う
ゲームで言えばグリッチですらない 参加登録したけど急用とかで参加出来なくなった人への救済措置を悪用しているとも言える
社長が何度か否定的な言及をしている
chokudai/status/871148795907592192
chokudai/status/880224236173787136 >>646
> 最後のLIS=辞書順最小のLISではないのかな？
あ〜〜〜一番後ろの方にあるLISが辞書順最小のLISなんですね
あるLIS (Xとする) の先頭より添字番号が小さい要素を含み、かつ辞書順で X より小さいLIS (Yとする) が存在する場合、Yの要素を使ってXが伸ばせるのでXがLISであるという仮定と矛盾する
だから一番後ろにあるLISが辞書順最小のLIS
ってことですか
ありがとうございました
間違ってたらどなたか直してください >>566
これ見落としてた、>>646で同じこと言ってる
>>654
直感に頼った解法すぎて申し訳ない
合ってるとは思うが保証はできないから証明:ACしてくれ Twitterでnosubに物申してるアカウントのレーティングみてる 末尾を貪欲にとったLISが辞書順最小ってすげえ直感に反するな
辞書順といったら前から決めていくのが自然なのに後ろからやっても決まるってのが不思議 LISって増加部分列の長さが更新できないかを先に見て、更新できなかったら最長増加部分列の候補のどれかをより良いものに更新する（≒辞書順最小にする）から，こう考えれば直感的だと思った。証明はムズいかもしれんが DP の遷移をイメージすると確かに直感的だね、ありがとう 行間読めてないかも知れんが辞書順にした時先頭要素以外でより小さい場合とかあるから不十分じゃないか NoSub警察やめてください！！！真面目にNoSubしてる人の気持ち考えてください！！！ こういうのが問題になるのってレギュレーションの問題だろ？
運営がアホとしか言いようがないな。 お前ら黄色以上になってみろよ
そもそもratedがほとんどないのに数少ないratedでレート下がるとマジで病むぞ
まあここ数週間は毎週ARC級あるけど前は2ヶ月に1回あるかないかくらいの頻度でマジでひどかった >>633
レート停滞をNoSub勢のせいにしてる人のがダサくないですか？
誰とは言わないけど >>667
レート下がったってABCで黄パフォ取ってすぐ戻れるんだからよくね >>669
レート下がったら誰でもABCを受けられるとでも.....？？？ こんな便所のラクガキを気にしてる人多すぎて逆に驚きなんだが（>>603）
そんなにNosubが後ろめたかったのかよお前ら >>670
色落ちしなければ何も変わらんし色落ちしてもすぐ戻れるって言いたかった 意外と反応良いので毎回晒してくれ
専用サイト作ってもいい
AtCoder NoSubs レジって参加しなかったのか、nosubなのか判断つかないから
コンテスト後提出してる人をリスト化してくれ Nosubに不満勢とNosub勢でレート遷移比べたら面白そう コンテスト開始後30分してからやっと問題見られるようになってコンテスト時間でコード書いて終わった直後に提出とかはやむを得ないでしょ
そういう人も晒しあげるのはどうかと思うよ そう言った事情を考慮せず一律で晒し上げた方が平等でいいんじゃないか
いやまあそもそも晒し上げてどうすんねんという話だが >>614
日本人なら多分初
性別の話題に過剰な忌避感出す奴がいるけど、素直に女性初橙おめでとうと言いたい >>614,681
医者からGoogleのエンジニアに転職した人って女じゃなかったっけ あの人話題になったとき青じゃなかったっけ？今はさらにレート上がってんのか わざと不正確なことを言って情報を引き出す高度な情報戦か？
さすがアルゴリズマーはやることが違うな こんな時刻にCodeforcesがあったのか
問題だけ見てやろう Atcoder Nosubsは正直笑った
Nosub streakとかNo submissions ランキングとかあったら見ちゃう
別に作ることになんの問題もないよな >>691
出てれば温まるはずだったみたいなやつ予測して煽る機能も欲しいな NoSub批判は好きじゃないけど、名誉毀損はまた違う気がするなー.... オンラインコンテストにおける不正対策は現実的に無理なので、
Nosubを規制すると、もっと重大な不正をする人が増える可能性があるんじゃなかろうか
これがNosubを規制しない現実的な理由だと思う 具体的に重大な不正とは何なの？
実質no sub対策されてるコドフォで不正あんの？ ノーサブは別に大したメリットないし、他に与える影響もないから放置っていう見解だけなんじゃない？ nosubリスト書き込んだ人名乗り出ないかな
多分橙か黄のnosub批判派だと思うんだけど >>698
替え玉とかグループで相談しあって解くとか、atcoderでもちょくちょく耳にする。
コドフォがどうかは英語圏のコミュニティ読んでないから知らない。
>>702
出来がいい時だけ参加して、出来が悪い時は不参加なわけだから影響がないわけないでしょう。
レーティングシステムの欠陥。 解けたと思って出したらWAという場合もあるからノーリスクではない ノーリスクなんて誰も言ってない
リスクよりリターンが上回るからやるんでしょう？ >出来がいい時だけ参加して、出来が悪い時は不参加なわけだから影響がないわけないでしょう。
もっと論理的にどうぞ >>703
橙以上ならTwitterで言及してそう(偏見)
なので黄色以下かTwitterやってない人だと思う ・Nosubはレートをsaveできるだけで、スキル向上するわけじゃないから長い目で見れば意味なし
・Nosubは大きな問題にならないだろうから、AtCoderやCS Academyはルールを変える必要なし
・Nosubを規制しても参加者が減るだけ
2番目、3番目は現実はどうなんだろう 長い目で見たらレート吸うだけ吸って最終的にsubmit出来なくなって消えるんだからレートデフレ圧力になるでしょ nosub叩きの本質って「人のレーティングを下げたい」か「自分のレーティングを上げたい」のどっちかでしょ？
そのためにリスト作ったり気持ち悪いね
レート上げたいなら精進すれば？ >>713
レートデフレはアクティブな登録者間の相対的レートには関係なくないか
（ランキング等からノンアクティブを除くべき、みたいなのはまた別の話とはいえ賛同はする） >>716
あくまでnosubリストであって、悪意のあるリストではないので。 実際微々たる影響だろうけど、皆が皆やり始めたら色々おかしくなるからシステムとしてはおかしいな 冷え→温まり と nosub→温まり で最終的に同じレートにする（あるいは前者のほうを高くする）って無理なん？ >>718
プロフィールにTKって書いてるじゃん 筑駒は男子校だぞ nosubよりネカマを糾弾しろ
なーにが女子大生の競技プログラミング日記じゃ >>714
俺はNosub容認派だけど、その文章は「nosubの本質って〜」と書き換えるだけでそのまま反論になってしまうと思う >>723
そこのあなた！
男を自称するのはやめなさい！！
女の子は女の子らしくしなさい！！ 例の女子大生のアレはネタにしては大して面白くないし、その割に結構徹底してやってるから一切触れない方がいいやつだと思ってた
椿彩奈とまではいかないけど、なんかそういうのを抱えてるんだろうな まーた陰湿なdisが始まったよ
CodeforcesのD1B/D2D、かなり問題として面白いけどテストケースが弱すぎてダメだね レートでゲーム性出して釣ってんだからチート要素に対策しなかったらそれ相応に廃れるだけだわな。
んなこと他のサービス見てれば想像つくと思うんだがな。 >>725
nosubの本質は「自分のレートを下げたくない」なので全然違うけど。 陰湿なdisどころか、目立つポジションでネカマやってる奴はここで話題に上がって射精するほど喜んでるよ Nosub叩いてた某黄色が青に落ちててニッコリしちゃった >>731
久々にｵﾁﾀ
こういう出題が沢山あったのが昔のCodeforcesなんだよな
今の新参はHackをしないから困る >>736
これでnosub不利を主張して通ると思ってんの？馬鹿なんじゃないの？ >>719
nosubは単に「登録して提出しないこと」を意味するものではなくないか？
例えばKUPCみたいな有志コンに参加登録だけして実際には参加していない人がnosubと呼ばれているのは見たことがない
基本的にはratedでレートの増減に関する問題が起こる場合にのみ使う用語と認識している Streakとか普通に便利そうだから晒しerたち、本気でAtCoder Nosubs作ってくれ
(晒されて不都合があるような事をしてるわけじゃ無いんだから当事者としては問題ない) あれが女に見える奴がいるとしたら、医者に見てもらった方がいい Nosubはただ単純にダサいから叩く
いい年して汚いヨレヨレのTシャツを着てるやつにダサいと言うのと同じ ネトゲらしくno sub許さない派と許容派で勢力戦やれびいいじゃん 弱い根拠で中途半端に理屈こねて否定するよりも、>>743 みたいに感情的に否定する方が清々しいな
考え方の違いでしかないんだし nosubダメってマラソン勢どんな顔して見てるんだろうな
atcoderのマラソンは参加することでレート下がらない仕組みにするって話だが chokudaiが許容してtouristが問題ないと言ってるシステムに文句があるなら、それはもう新しいコンテストサイトを作った方がいいんじゃ
屁理屈で喚くみたいな非生産的なことするなら、SubCoder作ろうぜ？ >>740
nosubは単に「登録して提出しないこと」という認識なんですが。
戦略的なnosubと不可抗力によるnosub、元々提出するつもりの無いnosubがあると思います。
勝手に意味を限定するのはやめてほしいですね〜〜 >>740
nosubは単に「登録して提出しないこと」という認識なんですが。
戦略的なnosubと不可抗力によるnosub、元々提出するつもりの無いnosubがあると思います。
勝手に意味を限定するのはやめてほしいですね〜〜 NoSubを許さない会の規約
・コンテスト終了までにA問題にTextで「う し た ぷ に き あ く ん 笑」を提出しなければいけない >>748
貴様は権威主義者か？
chokudaiにちんぽしゃぶれって言われたらしゃぶるのかよ nosubリストはこれからも作り続けてほしい。単純に見てて面白いので。 次のコンテストで、上で名前の挙がった人らが必死に参加して、レート下げるのを見るのが楽しみだ こういうのほんと嫌いなんで、強制的に参加させようとする奴はめちゃくちゃ叩かれろ いやいやnosub問題ない勢だから次回も元気にnosubかましてくれるでしょ 叩かれろ（願望）
人の行動に期待ばかりしてないで自分でやれよ
赤ちゃんじゃねえんだから このnosub listはそもそもレジってない人も含まれてるの？ レジって提出してない人だけ
>>603は黄色以上の日本人のみ、>>715は色・国関係なく全員 世間に相手されない、女や友達が一人もいない、だから匿名でnosubたたくのか 今後、運営がnosub者をコンテスト終了後に不参加扱い(順位表に非表示)にするに一票 晒されたという認識になる時点でもう何らかの後ろめたさがあるじゃん >>773
お前みたいなガイジに噛みつかれないためだろ >>775
意味不明で草
晒しといてそれに文句言われたら後ろめたさが云々って無敵理論すぎる なんかの決勝進出者一覧とかが貼られてても晒しと感じるのか？
感じるなら俺の負けだけど nosubについて語るのは勝手にすればいいが、規約に書かれてない以上nosubやってる奴らを晒すのは違うだろ >>779
なんかアルゴリズムとか問題の話振ってくれたら自分がついていける範囲で答えるからよろしく >>782
蟻本に書いてる、行列累乗を高速化するアルゴリズムってどういうのですか？ >>784
O(K^3)をO(K^2logK)にするやつかな
TDPC-Tで出題されているのでその解説してるブログを読むといいかも(俺は挫折してまだACしてないです…) ARC109-Cでじゃんけんの勝敗決めるアルゴリズム書いてる時に(python)
if s == "RP" or "PR": return "P"
みたいに書いてたせいで全てのじゃんけんでPが返ってきて頭抱えてた https://maspypy.com/多項式・形式的べき級数（３）線形漸化式と形式
これの線形漸化式の高速計算 >>785
情報ありがとうございます
きたまさ法を使うとO(k^3logn) -> O(k^2logn) になるんですね >>791
Python では空でない文字列は特別な場合を除いて True を返すからじゃない？ 後ろがsとの比較になってなくて全部trueになるとか？ >>791
or演算子は==よりも後に回されるので
(s == "RP") or ("PR")
と解釈される、pythonにおいて文字列は空の場合のみFalse、それ以外ではTrueになるのでこの条件式は絶対Trueになる
s in ("RP","PR")とか書くのがわかりやすいと思います if s == "RP" or s == "PR" が正解？ C++でa^b == cでa XOR bがcと等しいか判定できると思ってハマったことならある AtCoder Career Designとかいうのが出来たらしいが AtCoder NoSub Listsはまだなのか？ >>802
公式でやるなら順位表ご確認くださいで終わっちゃう >>799 あるある
&と^に括弧つけないで痛い目に合うのはみんな通る道だよな atcoderで就職したい人そんなにおるん？ 二流大学出身者としては東大生なんかどこでも行けるやろという印象なんだが >>800
自分だったらinで書く という意味でした レーティングが本当に就活アピールになりすぎると間違いなく不正が横行するよな
複垢代行とか高レート保持者によるコンテスト中の解法共有とか闇ビジネスとか出そう いつもc++使ってるみなさん、Pythonくらいだったらそこそこ使える人多いの？ 本当に就活に役に立つようになったら実務型マラソン(数日おきに問題が少しずつ変わる)とか出たりしそう >>812
Pythonとは限らないけどライブラリ充実してる言語を他にひとつはやってる人が多いイメージ 不正で得たレートで就職したがるような低知能層はそもそもプログラミング適性ないんじゃないか 高レートが競プロから永久追放されるような不正に手を染めるかというと疑問
金に困ってる人もそんなにいないだろうし nosub云々言ってる暇があったら、
アルゴリズム勉強して、下記のところで雇ってもらえ
https://career.atcoder.jp/company AtCoderを追放された闇競プロer
社員に強いのおらんのにAtCoderで募集してる会社なら2色くらいごまかしてもばれないかも 働く競技プログラマ図鑑の人暖色ばっかじゃん
良い会社にいる茶色の人とか探して載せて >>820
良い会社に茶色の人もいるだろうけど、その人は別に競プロを評価されて就職した訳ではないだろうし無意味じゃね？ latte0119
beet
olphe
Tiramister
tute7627
se1ka2
dividebyzero
nebocco
ransewhale
tonegawa
simkaren
holeguma
mugen1337
shogier フツーに茶色下はコーディング採用向けかと。今のレベルだと緑も求めすぎで専門がおろそかになりそう。 >>806
ビット演算子の優先順位が比較演算子より低いのはクソ言語の証
よってC++はクソ言語 次スレからは前スレリストを10毎にしたらどうか？二分探索リスト作るの普通にめんどくさそう 0のみを要素とするn要素の配列があります。
クエリがQ個飛んできます。i個目のクエリは数字aiで表され、
「配列の左から1個目〜ai個目のうち、要素が0である最も右の要素を1にして出力する」動作を行います。ただし左から1〜ai個目の全ての要素が1のときは-1を出力します。
n,Q<=100,000
入力例
n=1,Q=[3,3,3,5,2,5]
出力例
3 2 1 5 -1 4
これ簡単に解けますか？ そうですか…
入力例において、配列は
00000→00100→01100→11100→11101→11101→11111
と変化しています setで a_i = 0 な index を管理するだけじゃないか セグツリーにちょっと手を入れたらいけそう
範囲の最小値が0なら右端から上行ったり下行ったりしてたどって特定して1に書き換える >>831
あっstd::set…たしかにそうですね…
平衡二分木のない言語しか使えないので考慮していませんでした；；
>>832
セグメント木使えばいける気はしてたのですが上手い使い方が分からず…
クエリあたり高々2lognくらいで探索済みそうです金？ セグ木に{int pos, bool is_one}を乗せたらいけそう
演算はis_one=trueかつposが大きい方を返す（どちらもis_oneがfalseなら{-1, false}）
単位元は{-1, false}
これでprod_allするとO(1)で右端の1の位置がわかる
更新はO(logN) あ、0と1が逆か
is_zeroで読み替えてください 同じく平衡二分木という選択肢が完全に頭から抜けてる・・・
>>833
2lognで済みそうです
右端が0じゃない→親に移動。0じゃないならさらに親に行く。0なら左側の子を見て0なら子に移動して右の子を見て左の子を見て・・・
みたいな感じになるんじゃないかな セグ木上にぶたんは実装経験ありますが結構考えること多くて面倒な気がしてしまい…
>>834
これスマートな気がしますがクエリごとに求めたいのはaiまでの右端の0の位置なので、両方logNかかりそうですね
なんか脳死で実装できそうなのでやってみます！ structとか乗せる必要がなくて、単に1のところは-1を入れて、0のところは位置を入れて、区間最大すればいいことがわかってしまったんだが >>840
あ、最高にスマートですねそれ
こっちでいきます なんか名前見たことあると思ったらPFNの人っていもすさんか いもすさんのHPに本名と勤務先乗ってるから、まあ間違いないと思うよ AtCoeder、宣伝のために一人くらいイケメン・美女がほしい 俺が知らないだけで、ここにいる社会人競プロerの皆さんもいもすさんみたいなかっちょええ仕事しとるん？ いもすさんって今もちょくだいさんとかと大会出てるよね？
あの仕事しながらそういうレベル感維持するの半端なくないですか １時間前に問題が完成していない、実質テスターなしで開催
制約違反なケースがあった
ケースがクソ雑で何やっても通った
コンテスト中にケースを追加した
自分が知ってる範囲の不備はこれくらい マイナビとAtCoder、電通が日本における先端IT人材の不足解消を目的とした業務提携契約を締結
プログラミングコンテストを運営するAtCoder株式会社（本社：東京都新宿区/代表取締役社長：高橋直大、以下AtCoder）と、株式会社マイナビ（本社：東京都千代田区/代表取締役社長：中川信行）が運営する就職情報サイト『マイナビ』と株式会社電通（本社：東京都港区/代表取締役社長：五十嵐博）は、国家課題となっている先端IT人材の採用・育成の分野において、各社の保有する人的資源、知的資源等を活用し連携・協力することによって、日本における先端IT人材の不足を解消することを目的とした業務提携を締結しました。
その取組みとして、先端IT人材として活躍が期待される競技プログラマーの就職・採用を支援するプロジェクト「AtCoder Career Design（https://career.atcoder.jp）」を11月30日に開始することをお知らせいたします。
https://prtimes.jp/main/html/rd/p/000000031.000028415.html ADHDASD診断されてるに決まってるだろ、発達舐めんな(誇らしげ) >>868
この時代に・・・・・・・・・・・・・・・・・・ 知的障害者だと思われるかもしれんが、N個のモノがK個のクラスに分類されていて、各クラスの各モノを走査したいとき、その計算量は O(N^2) じゃなくて O(N) だよな？
Kは1からNまでありえて、各クラスに含まれるモノの数も1からNまでありえるが、各クラスに含まれるモノの数の和がNであるという制約のために走査のコストは O(N) に落ちる
合ってるよね？ K=Ω(N)なので若干の注意が必要みたいなやつ、300点くらいで無限に出てそう。 発言内容でキモいかどうか判定してそうだけどさ、
女から見たら外見キモいならキモいよ、色とか関係ないから >>877
Ω？
Oじゃなく？
どう考えてもK<NだからOじゃない？ 具体的なアルゴリズムを一切示さずに計算量の話をするのは議論が雑すぎる >>882
モノiはクラスA_iに属しています。制約: 1<= A_i <= 10^9
みたいな問題、よくあるだろ Can I succeed in computer science research if I've failed at competitive programming?
https://www.quora.com/Can-I-succeed-in-computer-science-research-if-Ive-failed-at-competitive-programming
競プロできなくても研究で成功できるという好意的な意見が多い
アルゴリズム研究者の Jeff Erickson も同意見のようだ >>883
走査っつったら走査じゃないの
何らかのループで走査する以外に解釈できない
で、その計算量はO(N)としか言いようがない for k in class K
_for n in set N
__if n is k
___do something ハッシュが効くかどうかもまともに述べられてない時点で考察する意味がまるでない >>885
普段のプログラミングとの違いは
for 文でやろうとするかしないかの違い
競技プロはしないという考えかたをする。TLEになるから
普段のプログラミングではソースコードにコメントも入る
競技プロが遊びといわれるゆえん >>889
言葉が足りてないので伝わらん
「for文でやろうとする」というのはどういう意味だ？
何をfor文で書いたらTLEになる？
そもそも業プロではfor文はできるだけ使わないんじゃないか？ codewarsが面白い
いまTypeScriptやっている for文ってあんま使わないんだ知らなんだ
理由はなぜ？ >>886
例えば>>887みたいにNとKの両方で走査したらO(NK)
クラスごとに所属するモノをまとめて処理できるのであればO(K)
モノごとにそれぞれ処理するのであればO(N)
上でも言われてるけど計算量の話したいなら具体的に処理の流れ貼ってもろて >>892
バグの温床だから
通常使う場合は全部見るし
一部欲しいときは専用の関数が充実しているし
境界あたりでいつもバグが生まれているな REPマクロは正義
Linuxのカーネルでも山ほど使われてる 読みやすさやメンテナンス性の良さ
そんなものが本当に必要だろうか？ 強い人は少なくとも自分にとっての読みやすさは追求してるはず >>889
こいつpaizaのスレにもいるガチのやべーやつ
口調でおっ出たってなるんだけど、毎回総スカン喰らってて笑う 変数1文字でスペースのないコードを見ると
これをバグらせないのすごいなと思ってしまう Shortest狙うとそうなるよね
このスレにShortest持ってる人どのくらいいるのかな 自分でも解ける問題はだいたい golf勢が手をつけてるから持ってない
golf されてない問題でも大体自分よりもっと洗練されてるコードが Shortest とってるし 変数一文字の難読コードはminifier使ってるんだと思ってた 数式そのままコーディングみたいなのは普通に1文字変数がダビリティ高くね
んで競プロだとそういうのが多い 高級言語だと問題文に出る変数+α（1,2個）くらいで十分 グラフ絡む問題になったら1, 2個は不可能じゃないか よっぽど実装軽くない限りどんな分野でも1, 2個は無理 業プロでfor避けるっていうのはインデックス回すのをできるだけ避けるって意味ちゃうん？
いわゆるforeachのほうを使いましょうみたいな
Pythonとかだとforだけど 多分そういうことなんだろうな
組み込み関数を何故か全部O(1)だと思ってる人いるし 全部O(1)ってのとはちょっと違うけどC#だとなぜか通らない問題があったね
あれどういうことなんだろう 文字列を辞書順に並べるやつね
ABC155-Cで話題になってたな あれはね、標準の文字列比較で文字のカルチャまで含めて比較しようとしてくれやがるせいで無限人TLEしたのよ……
結局コンテスト中のACは3,4人しかいなくて、DがPairsだったのもあって地獄絵図になった
俺？当然灰パフォでした その言語使ってた人は可哀想だけどそれで特定の言語落とすのかとか騒いでで笑った 特定の言語が不利になるなんてPythonとかしょっちゅうなのにそれが自分の身に降りかかった途端騒ぎ出すのも
社長が晒し上げて作問バイト達が袋叩きにしてたのも見ててうーんになった >>929
www
名前をkeyにしてdictionary管理するコードがTLEは辛い…… 今週もABCなしか。atcoder終わったな。一番金になる層を冷遇するなんて経営センスなさすぎるわ。しょせん学生の会社ごっこやな 入茶だか灰上を育てるのが一番お金になりますからねぇ さすがにオフシーズンには野球ch同様勢いを失うものの、野球chに戻ることは決してなく「アニ豚氏ね」「なんJ終わったな」等と言いつつ次のシーズンが始まるまで板に居座り続ける有り様となっている。 C#知らんのだけどカルチャとやらの比較はそんな重い処理なんか topcoderでもC++だけ一つもACされてない問題がある
SRM710のDiv2-hard
自分なりに考えてみたがなぜC++だけそんなことになるのか解明できなかったので誰かやってみて教えてください フリーランス向け報酬即日払いサービス『先払い』が、オンライン資金調達プラットフォーム『資金調達freee』β版に掲載開始
https://prtimes.jp/main/html/rd/p/000000037.000047439.html
フリーランスやパラレルワーカー同士のマッチングプラットフォーム「conema」が、
案件依頼・仲間募集を中心とした掲示板機能（β版）をリリース！
https://prtimes.jp/main/html/rd/p/000000004.000059389.html
フリーランス薬剤師専門エージェントサービス「きょうりょく薬剤師」、リリース開始。薬剤師の新しい働き方を提唱。
https://prtimes.jp/main/html/rd/p/000000002.000058526.html
中卒、新聞配達員から月収4億の不動産王へ。姫路の不動産王の投資哲学
https://hbol.jp/184178
【アプリ開発で起業】必要な心得とマネタイズ方法のすべて
https://www.dreamgate.gr.jp/contents/column/application-development
副業を認める企業に対して「より魅力的に感じる」人は６割以上。
一方、副業を認めない企業に対する魅力度は６割超が「低下した」と回答
https://prtimes.jp/main/html/rd/p/000000016.000040832.html
みんなが知らない「サラリーマンの生存戦略」副業年収1億円！motoさん伝授
https://diamond.jp/articles/-/247070 なんや自治厨が湧いとるな
テンプレなんて貼りたいやつが貼れよ 次スレは安価を踏んだ人(踏む人ではない)が立てましょう
連投規制などの事情がない限りテンプレは>>1が貼りましょう
こういう専門板の基本的なことが分かってないなら半年ROMりましょう >>962
マルチスレッドで排他制御をしないとどうなるか考えれば分かるだろう >>964
競プロerがマルチスレッドなんかわからないだろ 並列処理すればO(10^8)でも通っちまう気がするんだ！ 真面目にTLが決まってる時の計算量解析する道具がいるだろ
FLOPSはなんか浮動小数点演算だった気がするし >>973
役に立たないとは言わないけど競技プログラミングでGoのGoroutinesとかC#やJS/TSのasync/awaitとかがどうして優れているのかを学ぶことは出来ないな 並列化しても、IOとかでも使わなければ定数倍改善にしかならないからな・・・
IOを使う場合で、O(N^2)からO(N)に改善できるようなことはあるんだろうか 美Vが3ヶ月で青色になる動画とかやったらバズりそう 順位表を眺めているのは順位表から読み取れない情報では？ youtube実況を必須にしたら、atcoderでギャンブルができる yutaka強すぎないか？
けんちょんは受けたのか？ このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 31日 16時間 23分 34秒 5ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。
───────────────────
《プレミアム会員の主な特典》
★ 5ちゃんねる専用ブラウザからの広告除去
★ 5ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────
会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。
▼ プレミアム会員登録はこちら ▼
https://premium.5ch.net/
▼ 浪人ログインはこちら ▼
https://login.5ch.net/login.php レス数が1000を超えています。これ以上書き込みはできません。
