競技プログラミングにハマるプログラマのスレ 24 YouTube動画>1本 ->画像>8枚

プログラミングコンテスト(プロコン)やオンラインジャッジや競技プログラミング(競プロ)や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
※前スレ
競技プログラミングにハマるプログラマのスレ 23
http://2chb.net/r/prog/1581127445

テンプレ続き

# 高校生・大学生対象コンテスト
情報オリンピック https://www.ioi-jp.org/
ACM-ICPC http://icpc.iisf.or.jp/

# その他便利なサイト
コンテスト・カレンダー
https://competitiveprogramming.info/calendar
http://clist.by/
AtCoder Problems http://kenkoooo.com/atcoder/
オンライン整数列大辞典 https://oeis.org/?language=japanese
WolframAlpha https://www.wolframalpha.com/
Spaghetti Source
旧: http://www.prefield.com/algorithm/
新: https://github.com/spaghetti-source/algorithm
競技プログラミングwiki http://wikiwiki.jp/kyopro/
AOJ-ICPC http://aoj-icpc.ichyo.jp/
competitiveprogramming.info https://competitiveprogramming.info/
競プロSlack https://competitiveprogramming.info/slack
OnlineJudgeHelper (オンラインジャッジ補助スクリプト) https://github.com/nodchip/OnlineJudgeHelper
Google翻訳 https://translate.google.co.jp/

テンプレ続き

# 書籍
プログラミングコンテストチャレンジブック (蟻本)
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (AOJ本, TLE本, 渦巻本)
最強最速アルゴリズマー養成講座 (チーター本)

# 日本人競技プログラマ
Twitter 競技プログラマリスト
https://twitter.com/kinaba/lists/topcoder-jp
https://twitter.com/kobae964/lists/atcoder
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
https://twitter.com/5chan_nel (5ch newer account)
https://twitter.com/5chan_nel (5ch newer account)
https://twitter.com/5chan_nel (5ch newer account)
https://twitter.com/5chan_nel (5ch newer account)
https://twitter.com/5chan_nel (5ch newer account)

テンプレ続き

# 過去スレ
1: http://2chb.net/r/prog/1443271207/
2: http://2chb.net/r/prog/1461096973/
3: http://2chb.net/r/prog/1468710465/
4: http://2chb.net/r/prog/1470294745/
5: http://2chb.net/r/prog/1472132297/
6: http://2chb.net/r/prog/1479623072/
7: http://2chb.net/r/prog/1482151701/
8: http://2chb.net/r/prog/1483782812/
9: http://2chb.net/r/prog/1487426332/
10: http://2chb.net/r/prog/1493085730/
11: http://2chb.net/r/prog/1498137486/
12: http://2chb.net/r/prog/1505047495/
13: http://2chb.net/r/prog/1511943431/
14: http://2chb.net/r/prog/1517756393/
15: http://2chb.net/r/prog/1526247830/
16: http://2chb.net/r/prog/1534548265/
17: http://2chb.net/r/prog/1540997394/
18: http://2chb.net/r/prog/1548601907/
19: http://2chb.net/r/prog/1557609166/
20: http://2chb.net/r/prog/1563667469/
21: http://2chb.net/r/prog/1572427030/
22: http://2chb.net/r/prog/1575287454/

テンプレ続き

# 関連スレ
【したらば】プロコン・競プロ・ハッカソン・CTFなどについて語り合う掲示板
https://jbbs.shitaraba.net/internet/13109/
TopCoder
http://2chb.net/r/tech/1333159918/l50
プログラミングのお題スレ Part9 [無断転載禁止]c2ch.net
http://2chb.net/r/tech/1480579110/
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3c2ch.net
http://2chb.net/r/tech/1466315249/l50
【会津】パソコン甲子園2004【若松】
http://2chb.net/r/tech/1094308951/l50
CTFについて語るスレ [無断転載禁止]c2ch.net
http://2chb.net/r/sec/1476430177/l50

>>1からここまでテンプレ

>>1乙

今日は人権こどふぉだよ (10:35開始)

150分で草

2時間半コンテストはきつい1時間くらいで十分

Div.2 1時間じゃ解けきれねえだろ

AtCoderのプレスリリースで糞グラフ使ってて草
なーにがIT人材（）じゃ

指摘どーぞ

法則性なく色んな色が出てきて戸惑う。
１つ目の灰と３つめの灰色の濃さが明らかに違う、
１つ目と２つ目の表の行数おなじなのに数字の大きさが違うことなどから、
単に雑なだけではという疑念がわく。


これはそもそも字小さすぎる赤文字で読めない
がんばって３００％に拡大して読んだら
左の応募者数の「応募」が「応其」になってるので本人も読めていないのだろう

wataさん降臨

>>13
ワロタw(´・ω・｀)

これのことかと思った
縦軸がパーセントなのに波線なしに30から始まってる

>>16
俺もこれかと
データをまともに扱う気ないよな

atcoder黄色以上で検査増やすな、陽性出ても軽症なら無意味、とか言ってる
競プロ特化型人材に捨てアカで絡んで
遊ぼうかと思ったがそういう都合のいい残念な人は見つからなかった

指数関数の単語を出されて怒り出す橙コーダーとか
面白いと思ったんだがな

やっぱ競プロerってリテラシー高いわ〜って　話？よかったねえ

意味のとりづらい改行だ

ニュースの類にコメントしないだけじゃ
俺黄色だけどリテラシー超絶低いと思ってる

ゴッドエイムあきらが鍵アカになってしまったのは悔やまれる

おまえら匿名掲示板でコソコソやらずに直接言いたいこと言ってこいよ

「文句あるんやったら直接言いに来いや」的なセリフって
定型句みたいなもんで
本当に言いに来られるの想定してないよなって思う

損害賠償取るための罠やで

>>23
生放送で副社長のツイッターの話に触れた？

競プロの質問サイトみたいなのって無いのでしょうか？
procon-qaというサイトが見つかったですがあまり稼働してないようでした
Twitterは今から競プロ仲間を作るのは難しそうですし…

procon-qa
teratail
5ch
テキトーなSlack
好きなとこに投げると良い
今からでもTwitter やるのもおすすめしとく

今からは難しいって何

自分より弱い人の相手してくれる人は少ない

twitterで適当にリプでも投げれば良くないか
コミュニティに入りにくいとかはあるかもしれんが

黄色くらいならこのスレにもいるから適当に質問してくれていいぞ

ない
ってレスしないみんなやさしい……

教えたがりって結構いるからな
手軽に優越感満たせるし相手も喜ぶからwin-win

教えることで自分の理解が深まるのでオヌヌメ

Google Code Jamにはレジりましたか？

明日からですよ！緑色コーダーでも記念参加してみてはどうですか？水色以上はもちろん参加しますよね？

明日の予選ラウンドは早解きではなく３０ポイント獲得全員進出できますよ！
明日の朝から２７時間コンテストと時間たっぷりあるので機械翻訳使いながらゆっくり解いても大丈夫ですよ！
https://codingcompetitions.withgoogle.com/codejam

開催スケジュールを見て分かるとおり今年のGoogle Code Jamは日本の競プロ勢が参加しやすい時間帯！Tシャツ狙ってゆきましょう！

https://codingcompetitions.withgoogle.com/codejam/schedule

>>36
予選ラウンドはABCのC,DくらいからARCくらいの難易度
その次のラウンド1はARC級の中堅
その次のラウンド2はARC級の高難易度
AtCoderで例えるこんな感じだったかな？

Tシャツが欲しいけどこどふぉで1000位のレーティングは2232なんだよな
厳しい

最近やってないけどGCJだけは出るみたいな人結構いるからもっときつくないか

最近やってない人は早解きやコーナーケースに弱い
コドフォのレート順位は18歳未満を含む

仕事に忙しいオッサンになると競プロのノウハウやテクを忘れっぽくなるからGCJだけ復帰勢で驚異になるのはごく一部

明日のABC、参加者数が楽しみ
プロ競技プログラマーの誕生のために!

今夜yukicoder

GCJの参加は16才以上、オンサイトは成人年齢以上、？

GCJ、これからやるんだけどQualifiedにレがついてるのはなんだろ

https://codingcompetitions.withgoogle.com/codejam/schedule
このページのことか？
多分30ptとったって意味じゃないの、文字通り通過の意味で

そのコンテスト自体の参加資格っぽい
特に制限がないから全員ついてるんじゃない?

registeredと何が違うんだろ

E問題ピクロスやんけ！(歓喜)

D問題の解説10xじゃなくて11xでは

10xで合ってる

10xでも11xでも合ってねーわ

x % 10 がいるという話

デキューしたものをxとする
(x%10)≠0なら10x+(x%10)-1エンキュー
10x+(x%10)エンキュー
(x%10)≠9なら10x+(x%10)+1エンキュー

D問
もっと良い解説無いのかい
理屈がわからん

>>56
1~9を順番にキューに入れといて
1取り出したら10,11,12をキューに突っ込む
2取り出したら21,22,23をキューに突っ込む
これを繰り返すってだけ

>>55
これが正しそうだね
珍しいミス

>>56
ただ小さいほうから列挙するという話
Kが小さいんでうまくいく

>>57
ありがとう、めっちゃわかりやすい

D全列挙したら上手くいかなかった

また引用RTで晒し上げやってんな
そういうとこだぞ

なぜわざわざ晒すのかねえ

晒しか？

vtuberがキャラ忘れてブチ切れはかなり草

全く関係ないお受験とか言い出して、コンプ丸出しでワロタ
化けの皮が剥がれてる草

みんな何処みてるんだ
chokudaiくらいしかフォローしてないからvtuberとか何の話かわからん

きりみんとか言う奴だろ
キャラ崩壊とか言われてもそもそもどんな奴だったか知らんが

第1回データ構造総当たり選手権はいつですか

Educational Data Structure Contestが待たれる

でも実際今日のBとかCは何がしたいんだと思う
アルゴリズムとか何の関係もないし方向性がわからん

B問題はいつもと変わらんくない？
「繰り返しや条件分岐を使ったプログラムを正しく組めますか？」っていうよくあるやつだと思うけど

何がしたいも何も昔からこういうゲームじゃん
競プロは結局競プロに過ぎないしアルゴリズムが勉強したければ専門書で勉強すべきだし、プログラミングがやりたいならアプリでも作ってりゃいいんだよ
最近就職に役立つ！とかプッシュし始めたせいでその辺り勘違いしてる奴多そうだが

vtuberのやつ意外と長く持ったなっていう感情しかねえわ
対して競プロしてない癖に毎回うだうだ言っててすぐやめると思ってたわ

Fめっちゃ簡単じゃないか、E飛ばせばよかった

Cくらいなら非競プロerでも普通に解けそう

>>71
Writer本人が「整数除算でハマる人が多かった」ってツイートしてるけど
それだと「繰り返しや条件分岐を組める」からちょっと逸脱してる気もする

>>ABCの問題で解けない問題があった人
問題の傾向に文句を言うのではなく「プログラミング/アルゴリズムに関する知識や論理的思考力が身についていないことに気付けてよかった」と考えるのがｵｽｽﾒ

そんなん言われんでも分かっとるわ

就職に役立つは本当で、コーディング試験/面接がクソ余裕になるんだな
楽しくもないのに就職のためだけに毎回コンテスト出るのはコスパ悪いし、1ミリも実務開発経験の足しにはならんけど
>>74
順位表を見て正解者が多い問題から解くと吉じゃ

CとDのAC数差5000人超えてるんだな
5000人にとってはただのC早解きゲーでしかないってことか

BやめてCとDの間のDIFFでもう一問作ればいいのに

データ構造総当たり選手権の人にクソリプ送る奴がいるからツイ消ししてる
こうやって敵を作っていくんだよな
晒した本人は自覚ないから本当に厄介

パズル解くだけならまだしも、たくさん問題解いて典型を身につけるっていう作業は、どこが楽しくてやってるのか聞きたい

まぁ晒されるようなしょうもない発言するな　って感じはする。
しかもエアプっぽいしなあ。

元々有名な人だからしゃーない


>>82
俺はそれはそれで楽しいけどなぁ

https://twitter.com/tdualdir/status/1246451459408850944
https://twitter.com/5chan_nel (5ch newer account)

>>84
競プロだけに役立つ能力を伸ばすためにわざわざいろいろ覚えて時間を費やすというのが自分は好きになれん。
パズル問題は、解いて全能感を味わうのが好きだがw

ペンシルパズルの類も強くなろうと思ったら大抵定石覚えるフェーズがあると思うんだけど

あー「パリティを考える」「逆から考える」とかの定石は楽しいが、「全方位木DP」とかそういう高度定石が嫌

解けそうにない問題がこういったデータ構造/方針で解けるようになる
ということを知る快感を味わいたいんじゃないか、自分はそう

>>81
マジで教祖と信者で草
昔のヤバい奴らと同じ構造だな

競プロ界隈って信者ファンネル流行ってんの？
荒野行動みたいだな

>>89
なる、ちょっとモチベが湧いてきたわ

馬鹿野郎レート上げるためにやってるに決まってんだろ

>>81
chokudaiがクソってより一部の競プロキッズがクソ
てか調べた感じ競プロキッズの一人がクソ

>>81
普段のchokudaiは意図して信者をけしかけてるフシがあるけど
今回の晒し方的にはちょっと予想外なんじゃね

>>81
自分は悪くないとか思いながら、嫌われていくんだろうなあ

>>95
俺も今回は思わぬ方向に行ったと思ったが、その後のフォローが一切ないのはさすがに悪手

信者に突撃させて気に入らないブログとかツイを消させるのが気持ちよくなってるんだろうか
好きにすればいいけどリアル企業としては関わり合いたくない

信者をけしかけるて

うしたぷにきあくん笑って何？

>>98
何かあれば一瞬で燃えるやつだからな
関わらない方が賢い

周りに苦言できるのがいないから勘違いしちゃうんだよね
本人が自分は平均的にやってると思ってるところも逆に作用してるし

わざわざ苦言を呈してきた人間も一人ひとり潰していったし

Google Code Jam 2020 予選

日本人めっちゃ参加しとる

https://clist.by/standings/code-jam-qualification-round-16820931/?country=JP

関わってないのをお察ししてあげろっつってんだろ

SNSで他ユーザーや界隈に挑発的意見や攻撃的言動する人たちの意図は何？

天然

損害賠償で儲ける

>>105
反応してもらえないからってイライラすんなよ笑
小魚でもポリポリ食ってろ

>>104
rng_58がいない

前回決勝戦進出者はシード権あるとかでは？

>>109
これ向こうのネタだから反応しなくていい

touristは普通に参加してる

>>111
tourist参加してる

5chのスクショ撮ってtwitterで晒してるやつ何なん

それをわざわざ報告するお前なんなん？

url plz

https://twitter.com/noimi_kyopro/status/1246737246721638401
https://twitter.com/5chan_nel (5ch newer account)

クソほどどうでもいい内容だった...
言語アプデコンに備える

赤とかwriterならいいけどそれ以外の人をさらすのはやめようね

赤だろうとwriterだろうと基本的によくないぞ

昨日初めてatcorderをやってみたのですが、gccのc言語でabcのbまでしか解けませんでした。c ++は何回か触ったことあるのですが、回答を見たところ読めないところが多く、手始めにこのスレで紹介している書籍のどれかを買おうと思うのですが、どの本が一番おすすめですか？

赤タッチの扱いってどうなんだ

AOJ本

教科書的につかえてC++前提なのって「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」だけ
あと公式でC++入門あるのでこれでもつかめてくると思う　https://atcoder.jp/contests/APG4b
蟻本は辞書的に使う感じある

本は全体的に内容が古いし、ABCレベルの初心者にオススメできるものじゃない
蟻本は強くなったら役に立つけど今はまだ要らない
AOJ本はアルゴリズムとかデータ構造一通りさらうにはいいけど、どっちかというと競プロって感じじゃない
チーター本は読んだこと無いからよく分からん

C++まだちゃんとやったことないならAPG4bをやるのがいいんじゃないか
https://atcoder.jp/contests/APG4b

ありがとうございます！アルゴリズムとかデータ構造って本買いました。届くまで時間がかかるのでapgってやつやりながら待ちます！

5ch晒してる奴をさらすなってのも変な話だな

アプデコンのほうが前回のABCより良問な気がする

何を良問と思うかは人によって違うし実際どう思っている人が多いか知りたいならTwitterの投票機能で調べてみるといいかもね

パソコン甲子園、早く解説を公開してくれ
作る時間は十分にあるよね？

負荷テストとやらは終わったが真に言語アプデされるのはいつになるんだっけ

早ければ来週のABCらしいが
まあ今月中には移行できるんじゃね

次のABCもう予定あるのか。良かった。

ABC級は毎週生えると考えていいんじゃないかな

会津オンラインジャッジはいつコンテストやってるんですか？
コンテストバリバリ参加しないとレーティング上げられないじゃないですか

AOJのレーティングは解いた問題のスコアの合計

詳しい情報サンクス！

今度はbits/stdc++.hか
競プロ初心者にとっては紛れもなく有益ではあるがまあ競プロ外に持ち出すべきではないよなぁ

競プロ外に持ち出させるべきではないというのもまあ正論

白山とかいうの完全にゲェジやん

おかしいやつしかいなすぎて感覚が麻痺してきた

C++界隈と競プロ界隈では言語に対する姿勢がほぼ真逆だから荒れるのはしゃーない

この手の話題はお気持ち問題だと思うので遠目に眺めます

https://twitter.com/chokudai/status/1247178901756862466
これの「リスペクトはしっかりある」は真逆じゃねぇかな
https://twitter.com/5chan_nel (5ch newer account)

bits/stdc++.h滅べ派の過激派は@kazatsuyuとか@SaitoAtsushiとか何人か見るけど、別に良いだろ派の過激派はどのへん？
滅べ派が目立ってるから頭の中で中和したい

1つの分野しか取り柄が無いエンジニアはアイデンティティ保つ為に無意識にマウント取ってしまうの実際よくある事やから気を付けるんやで

良いか悪いかの意見は割と別れてるけど、過激派はただAtCoder叩きたいだけの人達でしょ
Qiitaを質問サイトとして使うアホをAtCoderが責任持って管理しろみたいなレベルのツイートしてる奴が1人じゃない訳で

これだからC++はいやなんだ

初心者にC++教えようとしてる時点で間違ってる
Rust教えていけ

>>146
他人の意見でバランスとってると何かある度に流されまくるだろ。中和なんか必要なくて、自分の判断で確固たる立場をとればいいと思うよ。

重要なポイントとしてとりあえずbits/stdc++.hって書けって書いておいて
処理系依存だから注意みたいな話は初心者は読まなくていいってまとめられてるゾーンや付録にしか書いてないのは不親切だとは思う

コードテスト前提じゃなかったっけ

コドフォとかトップコーダーの問題のアイデア、
バンバンAtCoderに取り入れて欲しい
AtCoderさえやり込めば、最新の知見が手に入るように
して欲しい

最新の知見ってなんだよ
先月publishされた論文に載ってたアルゴリズムで解けるようになった問題を出します！とかか？

segment tree beats の例題がatcoderに見当たらなくて苦労している
全方位木dpも500点くらいの欲しい

その辺がコドフォとかトプコにあるかは知らない

みんなからAPG4bってやつすすめられてやってみたけど，なんだこれって思ったらちょうど話題になってるのね、includeなんちゃらってやつ、

全方位木DP、600点以上のアルゴリズムじゃないか？
そもそも木DPを書かなきゃいけない上にそれを高速化する訳だし、低く見積っても600点だと思うが
beatsは知らん

segment tree beatsって英語ではなんて呼ばれてるの？

beatsで殴れる問題ならある
ratedでは知らない

たんなる木DPなら塗り絵とか今だと500点で出そうだけど
500点って水diffでしょ？全方位木DPで水は典型そのままでも怪しそう

名前が付いてるものを勉強したがる病か？
だからレートが上がらないんやぞ

勉強は別にいいじゃん
AtCoder のレートにはまあ直結しないだろうけど

>>160 beats自体がこどふぉブログで付けられた名称だから海外でもそう
アカデミックだと知らん(そもそもアカデミックのセグ木は平衡二分木にモノイドを載せるやつを指したりするし)

全方位は練習として再遠点を求めてみるといいよ Verifyは全点のMax(=直径)でできる

最近問題を解くだけではレートが変わらなくなったんだが
レートに直結する勉強って何？

まずタイピングかな

>>167
問題を解くことに直結することしかしてこなかったから成長が頭打ちなんじゃないか？

つまりどういうことだってばよ

レート帯による

1200です

EDPC

レートが変わらなくなったの感覚が違う可能性がある

>>154
Atcoderなんて所詮計プロで遊びなんだしそんなの期待してもなぁ
それにdata structure algoなんてnp解決とかない限り従来の知恵何らかに適用とかで大きな革新なんて殆ど無くね？
Kaggleとかの方がそうゆうのあるだろ(´・ω・｀)

chokudaiが強くなるための一番わかりやすい方法はバチャって言ってるよ

バチャで食い散らかしたら復習キューが山積みで消化しきれん

復習よりコンテストの方が楽しいから仕方ない

GCJ1Aってレーティングどのぐらいなら通過できそうですか？

Round1は1500人ずつ抜けていく形式だからAが一番厳しいよ
2200くらいはないと無理そう

ありがとう
じゃあB Cに備えます

水あればワンチャンくらいはありそう？

パソコン甲子園、何故解説を公開しない?
作る時間は十分にあるよね?
AtCoderなんて毎週開催でちゃんと公開してるよ

時間帯的にむしろAは狙い目では

全世界でみると時間帯の影響がどうなるかよくわからん

夜型の人は知らんけどもBの時間帯は厳しすぎるしCは最後だし
Aから頑張るのがいいと思うけどなあ

5chみたいに匿名かつその人がどんな人か分からないなら攻撃的な口調の意見とかそこまで気にならないんだけど、
Twitterだとアカウントと本人との結びつきが強い場合が多いから「あ、この人こんなこと言う人だったんだ……」って感じで残念な気持ちになる。
もちろん人それぞれ考え方は違うだろうけど、競プロ界隈の雰囲気を少しでも良くしたいのなら、せめてTwitterくらいは大人しく使うべきなんじゃないかな。

発狂しそう

火のように時間にせかされ
ろくな助力もなく問題の根拠も確かめられない
なんでみんな冷静にやれるんだ？

Educational Codeforces はじまるぞー

すまん、易しかったみたい

GCJ R1Aおつかれさまでした
統計情報↓
https://vstrimaitis.github.io/google_codejam_stats/

インド人多すぎ

全完最多は喜ばしいこと

やっぱ水でも通るくらいだったか

Springerがコロナ禍で無料公開した教科書に競プロに役立ちそうなものもあります
Guide to Competitive Programming
http://link.springer.com/openurl?genre=book&;isbn=978-3-319-72547-5
The Algorithm Design Manual
http://link.springer.com/openurl?genre=book&;isbn=978-1-84800-070-4
Computational Geometry
http://link.springer.com/openurl?genre=book&;isbn=978-3-540-77974-2

英語読むの厳しいな〜
TOEIC950くらいまで勉強すべきかな
950取ったところでスラスラ読めるようになるとは思わんけど…

上の教科書読むのにTOEIC の点数はいらん

最近流行りのDeepLで何とかなるのでは

どなたか、競プロについて気軽に雑談できるDiscordサーバを知りませんか？（Discordでなくても構いません）
実力は水上位です。今年中に黄になることが目標です
とあるサーバは見つけたのですが、そこでは既に緑の人が仕切っているのでコメントしづらいです

あと話は変わりますが、一度1000点の問題を解こうと思っています
目的は「目指すべきところを明確にしたいから」ですが、効果はあるでしょうか？
もしあるのでしたら、おすすめの1000点問題を教えていただけると嬉しいです

もうひとつ、700〜800点問題はいくつか解いているのですが、
700〜800点問題と1000点問題の違いなどを教えていただけると嬉しいです

典型的な資格厨って感じの質問

何に効果があるかなど誰にも分からず

点数は飾りみたいなもんだから

点数は飾り、ですか…
700点問題と1000点問題はあまり変わらないということですかね？

Discordは知らん、twitterとかで探した方が良さげ
点数は飾り
俺は青の時本番で800点以上通したことないが黄色になれた
高い点数の問題解いて達成感味わいたいなら
https://atcoder.jp/contests/cf16-final/tasks/codefestival_2016_final_f
https://atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_j
https://atcoder.jp/contests/agc012/tasks/agc012_d
この辺おすすめ

>>205
明確な違いなんてないんだから、人に聞かずに自分で解いてみればいいだけだろう

簡単な高得点問題の話題でRow to ColumnとTree Gameがないとかエアプか？

game on tree って証明辛くない？
row to column はコンテスト全体の点数がインフレしてるだけに見える

>>206 >>208
具体的に問題を教えていただきありがとうございます！
早速「Road of the King」から解いてみます

Twitterで探すといっても、具体的にどうすればいいかわからないんですよね…
競プロerをフォローしまくることから始めるのが良さそうですが、そこからどう行動するか…
いきなり話しかけるといっても、何を話せばいいかがわからないです…

これで簡単な方なんだろ？
とてもじゃないがD解ける気がしなかったわ

GCDガイジほんと勘弁・・・

Fはこれを貼ると終わる
https://atcoder.jp/contests/joisc2018/tasks/joisc2018_j

JOI難易度11?と思ったら1<=j<=N/2全部かよ
そんなの解けるのか

>>198
必要ないのは確かだが
TOEIC0なら英語問題そもそも読めないだろアスペかw

>>215
実質満点じゃん

D速攻で解答できてたのに掛け算のオーバーフローに気づかずオワタ

Dなんでintじゃだめなんだ？

N^3がintに収まらないので

Eのアルゴリズム思いつかんかった

大体llで書いておけばなんとかなる

>>219
そうだった
これからint全部long longで書こうかな

>>200
自分はもっと下のレベルだけど雑談できる場所は確かに欲しいですね
twitterも大体既に繋がりができてて入りづらい

(N/3)^3では
収まらんのには変わりないが

twitterは垢つくってコンテスト後にぽつぽつ呟くだけになってる
AtCoder のプロフにtwitter ID 登録してあるからかそんな垢でもぽつぽつフォローが飛んでくる、使ってる言語がC++以外だからかも知れんが

>>224
O(N^2)は出来てたんだけど答えをintにしてた

レート変化-65wwww笑うしかねえ
Eにハマりまくって終わってしまった、なんか再帰でいけるくね？とか思って方針ミスって時間が溶けていった

atcoderは
#define int long long
してまず問題なさそう

矯正したらええやん

昨日のF、とりあえず2乗のDPをメモ化再帰で実装して枝刈りすれば計算量とか考えてなくても通るか

というかまともに枝刈りができれば計算量がO(N)なのは明らか

はい明らかハラスメント

Dで4000のO(N^2)はスクリプトだと無理だと思ってた、
Cの想定解の200^3ですら怪しかったので

Cは何も考えずに書くとlogつかないか、前計算できるけど

>>223
そうなんですよね〜
ということは、友達のいない人（僕のような人）がDiscordで競プロのサーバーを立ち上げたら、
ある程度人が集まったりするのかな…

一から実装した二分探索に比べてlower_boundのほうが圧倒的に速いんだけど何でだろう？
・一から実装→1000ms
・lower_bound→500ms
みたいな結果になる

>>236
エスパーに期待してるのかもしれんけど
「一からの実装に無駄があるんじゃない？」
としか言えん気がする

>>236
lower_boundのソース見たら？

Dは定数倍やると3乗通るらしい

ある程度、作問した人には敬意を持つべきだなあ　と思う。まあ学生だし仕方ないかって気持ちもあるけど。みっともない。

Haxe 誰も提出してない

なにそれ

作問、別に無償でやってる訳でもないし

CとEのGCDを足していく行為は、数学的に無意味でアホなんじゃ無いかと思う

＞数学的に無意味

それはない

意味論は数学の一分野に過ぎないだろ

age

無意味でアホかもしれない問題に真剣になるのが競技プログラミング

競技プログラミングはもう数学ができるかどうかで
本質的な意味を失っている。

君が思う本質は本当に本質なのか

蟻本に載ってるようなアルゴリズムに詳しくなりたいというモチベーションがあるならatcoderよりコドフォやaojの方がいいのかもしれない

CってO(N^2logN)でできるよな
いくらなんでも愚直解が想定解なのはC問題としてはダサくないか

たかがC問題になに求めてるん

コドフォ問題文で遊びすぎ

defineintlonglong

読めないよりはまし

令和ABCのCなんて平成ABCのB＋αぐらいだろ

一律給付への頭悪いコメント
誰か止めるやつは居なかったのか・・・

社内でコンテストやる企業もあるんだね

https://proc-cpuinfo.fixstars.com/2020/04/contest-site-open/

青コーダーにシード権…？

https://tco20.topcoder.com/competition-overview/algorithm/algorithm-byes

今SRMやってる人これしかいないの？

>>260
色の表示ミスでしょこれ

過 疎

>>260
去年のbyeは最低でも2000越えてたのに今年は1700台もいて草生えるなｗ

去年 https://tco19.topcoder.com/competition-overview/algorithm/algorithm-byes

どうせ今年はコロナの影響でオンサイトは無さそうだし
最悪スポンサー付かなくて賞金なしになったりしてなｗ

りんごさんがGCJに出なかったのはオンサイト見込みが無いからだろうか？

AGC/ARCに色々捧げてるんじゃないの

パソコン甲子園は早く解説を公開してくれ！
たった年1回の行事だぜ?

順位表にレートの玉がついてる
https://clist.by/standings/srm-782-17843413/
https://clist.by/standings/atcoder-grand-contest-043-18537249/
https://clist.by/standings/codeforces-round-631-div-1-thanks-denis-aramis-shitov-18806597/

世界には何十億人といる人間のうちたった1000人にしか与えられないGoogleCodeJamTシャツを日本勢は何人獲得するだろうか

>>260
対象者が大幅に変わったな

修正前のbyeを信じてRound1を逃した人いたらかわいそう

どういう人が漏れてたんだ？

1Bの開催時間日本人には厳しい
1Bはさようなら

全域木とか１年くらい出てない気がする

コロナ、頼むから収束してくれ
ICPC含め、競プロオンサイトイベントが死んでしまう

競プロ、どう考えても影響が小さいしいくらでもやりようがある界隈なんだよな

競プロはまだましだからいいよね
ある程度の実力がついてきたからオンサイトにチャレンジしたいが

まあオンラインでどうにかなるけどさ、あのTシャツ着るのと強豪チームがアホみたいに風船増やしてくのを見たいんよな

atcoderのここ最近ABC人数見ても引きこもりで、競プロ人口は増えてるイメージ
オンサイトみたいなお祭りもあった方が良いとは思うが、他と比べても別に無くても特に困らなくね？

家より外の方が精進しやすいから困る

やるぞやるぞ

502なんだが

はいunrated

unrated多すぎでは？

unrated率高すぎだろ

コドフォより安定してたのは参加者が少なかったからってオチか

3ヶ月ぶりか?
Unratedのときに限って調子良い法則。

また Unrated かよ. いい加減しろ.

オンサイトはコロナで人集められず終わり
オンラインはコロナで人集めすぎで終わり

>>286
ほんとこれ
悲しい

こどふぉ散々でぃすっといてこどふぉより悪いのウケるな

毎回DとE以降の難易度差ありすぎだと思うんだけど

せっかくD解けたのに…

まあ無料でこんなことやってくれるだけでもありがたいから残念だけど責める事でもない

まーたやったなAtCoder

誰かunrated率計算してくれな

unratedも難易度やジャンルの偏りも慣れた
色が変わりそうなときにはやきもきするけど

>>293
Atcoder Jobsやってるし一企業のやってることなんだから失敗続きはまずいだろ

自分にとって不快だったからwriterやめろねぇ......
とは思うが、運営もよく利用者に不快だからサービス使うなとか言うし、そのしっぺ返しみたいなもんやね

社長やらwriterからして治安が悪いにも関わらず競プロ界隈は治安が良いと言われてた時期があるらしい
(どんだけ信者に我慢させてきたんだ)

一時間後にGCJ R1B だぞ
今は休息の時

相変わらずのうんこ具合で安心した
巨大な糞を集めるんだなｗ

社長の囲い本当にうぜえ
今までの流れあった上でまだ鯖代ケチってunratedしてるのはマジで無能だろ

Eは最小費用流を使えば解けますか？

計算量は嵩むが解ける
高速な実装なら通っても驚かない

レッドコーダーが居ても適切なサーバーの個数を見積もれないとバレるのは痛手だろうね

海外の競プロのサイトはいっぱいあるから精進には困らないよ！
https://w.atwiki.jp/projecthikky/pages/71.html

英語読めません
ぴえん

きも

You can use DeepL or Google Translator ;)

参加権を抽選にすればサーバ負荷を軽減できるのでは？

Eの解説を読んでもよく理解できなかったのですが、
要するに、活性度の大きいものから順に端へと配置していく、という認識で合っているでしょうか？

たとえば、A = { 1, 3, 4, 2 } であるとき、
1. 4 を右端か左端に配置
2. 3 を右端か左端に配置
...
というふうに配置していく、ということでしょうか？

あ、EというのはABC163のE問題のことです
https://atcoder.jp/contests/abc163/tasks/abc163_e

あってる
端に配置するという操作で貪欲にやると死ぬのでDPをしている

この問題ってA_iに負の値があっても解ける？

>>313
ありがとうございます

追加で質問なのですが、
「活性度の大きいものから順に端へと配置していくのが最適」
であることを証明したいのですが、うまくいきません
一応自力での証明を試みたのですが、場合分けが多すぎて綺麗に証明できそうにありません

よければ、綺麗に証明する方法などあれば教えていただきたいです

>>314
確信はないけど、まったく同じアルゴリズムで解けるはず

競プロをする上での証明力を鍛えたいのですが、
おすすめの書籍やWebサイトなどありましたら教えていただきたいです
（具体性のない質問になってしまい申し訳ございません）

「〜を昇順に選んでいくのが最適」といった貪欲は、
大抵きちんと証明せずに提出してしまいます（本番でも練習でも）
この癖を改善するためにも証明力を鍛えたいです

皆さんがどのようにして証明力を鍛えたかどうかも教えてほしいです
ちなみに私は青です
アルゴリズムの知識は豊富にありますが、それらを組み立てる能力がまだ足りなく、
今のところ黄色になれる気がしません

>>315
解説の説明ではダメなのかな
コンテスト中は私はまともに証明してない
発想としては活性度が 1 3 2 みたいに凸な並びが変換後にあるなら3 を端に寄せた方がスコアは良くなる
-> 変換後の最適解の形は 凹
みたいな観察で解いた

証明力は私も欲しいと思ってる...

証明力の鍛え方は簡単で、証明をすればいい

証明になってない証明っぽい何かができそう

貪欲の証明は、それをしなかった結果を仮定して、それより結果が悪くならないというロジックが一般的だね
上から順に端に寄せなかった場合、それより小さい数字が両端にあるから、どっちかと入れ替えても値が悪くならないって考え方でいけるはず

アルゴリズムイントロダクションにその辺のこと確か書いてなかったか

>>298
今回Writerの悪口って観測できなかったんだがあったん？

なんかEの「原始的なDP」って言い方を煽りと取った人がいるらしいよ
俺の見てたTLでは大喜利になってたけど

原始的なDPを煽りと捉える人性格ねじまがってそう

俺は普通に煽りに見えるわ

生きるの辛そう

他人の感想にそこまでケチつける必要あるか

逆に近代的なDPとは？

論文ゲー

原始棒銀、原始中飛車を使われたら煽られたと見てよろしいか？

将棋スレで聞いてこいよ

将棋ってカードゲームでもないのに環境かわったりすんの？

対戦ゲームは流行り廃りがあるだろう
将棋がそうかはしらんが流行してる戦術のメタ、改良考えるのは基本

いくらABCとはいえ中世DPまでは使えてほしいですね（呆れ）

ABCのメタデッキ教えて

原始的なDP、std::vectorが使えなさそう

>>324
それか…煽りかは知らないけど何の情報量もない言葉だとは思う
普段から説明不足でヘイト溜めがちなんだから余計な事書かなければいいのに

○○dp みたいなのが多いんだから
原始的なdp と言うことによる情報はあるだろ。

>>318 >>321
ありがとうございます
証明できそうです

---

移動前の位置を i, j, k、移動後の位置を Pi, Pj, Pk とする
そして、Ai > Aj, Ai > Ak, Pj < Pi < Pk を満たすような (i, j, k) が存在するものとする

[1] Pi ≦ i の場合
Ai と Aj をスワップしたとき、Ai のスコアは Ai * (Pi - Pj) 増加する
そして Aj のスコアは最大でも Aj * (Pi - Pj) しか減少しない
Ai > Aj より Ai * (Pi - Pj) > Aj * (Pi - Pj) を満たす
よって、Ai と Aj をスワップすることで、全体のスコアは必ず増加する

[2] Pi ＞ i の場合
Ai と Ak をスワップしたとき、Ai のスコアは Ai * (Pk - Pi) 増加する
そして Ak のスコアは最大でも Ak * (Pk - Pi) しか減少しない
Ai > Ak より Ai * (Pk - Pi) > Ak * (Pk - Pi) を満たす
よって、Ai と Ak をスワップすることで、全体のスコアは必ず増加する

[1] と [2] より、
Ai > Aj, Ai > Ak, Pj < Pi < Pk を満たすような (i, j, k) が存在するとき、
全体のスコアが必ず増加するようなスワップの方法が存在する
このスワップ操作を繰り返すと凹の形になる

したがって、最適解は必ず凹の形である（証明終了）

---

自分の証明を人に見てもらったことがなくて不安だったので、証明を投稿しました
証明として不十分なところや間違っているところなどありましたら指摘してほしいです

>>322
Amazonで調べたのですが、けっこう高いですね…
購入するかどうか悩みます

>>341
急がないならセール待てば
半額になる

ゴキゲンdp

原始DPを煽りと捉える人は低レベルプログラミングも煽りと捉えてそう

低レイヤのが正しくね

こどふぉの Editiorial 見てたら, 尺取法のことを Two Pointers Like Algorithm って書いてあったんだけど,
英語圏と日本語圏で用語が違うケースもあるんだな

>>345
低級言語、低水準言語はlow-levelの訳だし語句自体は適切だと思う
フクザツなメンタルの方々へのお気持ちへの配慮については知らん

パソコン甲子園、いつになったら解説公開するんだよ
時間はたっぷりあるだろ?
参加者のこと何だと思ってるんだろうね?

AtCoder、攻撃的な言動がお得意なのが多いからその手の人間が書いたと思うと引っかかる気もするな
書いた人が実際どんな感じか知らんけど

若い人多いししゃーない

作問者とかってわからないようにしてるのかな

解説からじゃわからんがwriter自ら公開してるから少々のネトスト力があれば特定は容易

https://twitter.com/chokudai/status/1252920311089004546
ネットワークは何もわからないんだけどつまりどういうこと…？
https://twitter.com/5chan_nel (5ch newer account)

フルマネージドなサービスがスケールしなかったってことかな？
急激にトラフィック増えるサービスと相性悪そうではあるが。

unratedな上級者は10分遅れスタートでいいんじゃない

人数的に誤差じゃね

上級者より初心者の方が圧倒的に多いんだが

会津オンラインジャッジのそれぞれの言語で使用されるコンパイラのバージョンはどこで知ることができますか？

https://onlinejudge.u-aizu.ac.jp/system_info

AOJで根付き木の問題（Rooted Trees）を解いてるのですが、根はどうすれば求まるのでしょうか？
Solutionsのコードを見たり「根付き木」で調べても分かりませんでした

木を「辺が親から子への方向を持つような木」とみなせば、
「入ってくる辺の数が0なら根」と判定できる

System Information
update: 2018.01.25

読んでる本で
int sum[MAX_N];
int t = lower_bound(sum + s, sum + n, sum[s] + S) - sum;
というコードが出たんですが、(s, n, Sは整数)
これをvectorで実装するにはどうしたらいいんでしょうか？
sum.begin() + s
などはエラーを吐きました

よそでやれ

>>363
符号なし整数を符号つき整数に暗黙キャストしようとしたから出た警告では？

>>364
すみません言葉足らずでした…一応累積和の問題だったんですが
改めて読み返すとこの文では読み取れませんね
完全にこちらのミスです申し訳ありません

>>364
ありがとうございます
原因なんですが色々弄っていたら最終的に
int t = lower_bound((sum.begin() + s), (sum.begin() + n), sum[s] + S) -
sum.begin();
でうまく動いたので自己解決しました
おそらくvectorでの実装の時イテレータと整数をどこかで間違えてたんだと思います
ご迷惑をかけてしまって申し訳ありませんでした

>>361
すみません、基本的な事が分かってないかもですが
木は接点同士が繋がっているので必ず入ってくる辺が１以上にならないでしょうか？
（親が一意に決まるなら親のいない接点が根だとわかるのですが）

親は一意に決まると思うけど

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_A&;lang=ja
この問題か
子の情報だけ与えられるからぱっと見で根が分からんってことだよね
根の判定だけなら、例えばn要素の配列を持って、子として与えられたノードに1を足していく
最終的に0で残ったノードは誰の子でもないので根
とか

>>369
すみません、その問題です。例えば出力例２だとnode1が根になってますが、
他のnodeが根でも根付き木が作れると思うのでルールが分からないです…
node1の接点がnode0という事は、node0から見るとnode1が子という事ですよね？

>>370
そういうもん
無向木の根に特別な性質はない。恣意的に決められただけのもの

入力例2は
1の子は{3,2,0}
0の子はない
3の子はない
2の子はない

「根」は「一番上にあるノード」のことだから1が根だよ

自分の書いたコードを人に見せたい欲が抑えられないのですが、
どうすればいいでしょうか？

時間があるならブログ作ってサンプルコードをpythonにして難しめのアルゴリズムの解説記事をガンガンアップしていけば見る人は多いはず
cppは既存記事を押しのける必要があるから微妙

pythonも溢れてねえか

>>340
この証明が証明として成立しているかどうかが知りたいのですが、
どなたか教えていただけないでしょうか？
社会人になってから競プロと数学を本格的に学び始めたので、
指摘してくれる人もおらず合っているかどうかが不安です…

東大理系生を家庭教師として雇ってはどうか

>>371-372
なんとなく理解できました。無向木と言っても親→子は一方通行なんですね？
同じ形状の木でも問題の書き方によって根が変わるんですね…

何度もレスしてすみません、有難うございました

>>340
正しそうに見えます。もっと厳しくできて、Pi<=iのやつを←、Pi>iのやつを→と書くことにすると、完成形は←←←...→→...の形になることが言えます。
この形なら一番左の←が最大、一番右の→が最大なのも比較的明らかです。

蟻本の第二版を読み始めたけど、36ページのLake Countingの実装例、微妙に変じゃない？
char field[MAX_N][MAX_M + 1]
って定義されてるのにメイン処理では field[x][y] のように参照されてて、xとyの使い方が逆のように思える。
変数名だけの問題だから、競プロやる人はあまり気にしないもの？

>>379
確認していただいてありがとうございます！
正しいのですね。安心しました

https://atcoder.jp/contests/abc161/tasks/abc161_e
こちらの問題の解法がわからないため質問いたします
とりあえず、考えたところまで書きます

Sの'o'の数をMとしたときの、頂点数Mのグラフを考えます
そして、次の'o'までの距離が+C以上の頂点に長さ1の有向辺をはります

このグラフ上での最初の頂点から最後の頂点までの最長距離がK+1以上であれば、
どの頂点を消しても最長距離はK以上になるため、必ず働く日は存在しない

↓ここから質問
それ以外のとき、各頂点について「自分自身を削除したとき、最長距離がK-1になるかどうか」を判定したいのですが、
その方法がわからないです
愚直にやると、最長距離を求めるのにO(N)かかり、全体でO(N^2)かかってしまいます
どのような工夫をすることによりこの計算量を減らせるでしょうか？
それとも、この方向性では解けない、または解くのが難しいでしょうか？

長文失礼しました。回答していただけると嬉しいです

それだと全部"o"でC=1の時に辺の数が(10**5)**2にならない？どうやって辺張るの

>>380
何に引っかかってるのかまるで分らない

>>383
実際に辺を張るわけではなくて、
考察のときだけそのようなグラフを考えるという感じです

このグラフをそのまま実装するとO(N^2)になりますが、
このグラフの最長距離を求めるだけであれば、セグ木を使うことでO(NlogN)で計算できます

ただ、500点問題でセグ木を使う時点で、誤った解法の気がしてならないです…
セグ木を使い始めるのは600点問題からだと思う…

セグ木と言ってるが更新もしないし、前からと後ろからしか使わないんだろ?
だったらセグ木じゃなくてもいけるということだ

>>380
xyを横縦に対応させるか右手系に対応させるかはよくある宗教問題

dp[i] = (dp[0 ~ max(i - C - 1, 0)] の最大値) + 1
という更新を前から行うことで dp[N] に最長距離が入りますが、
「dp[0 ~ max(i - C - 1, 0)] の最大値」をセグ木を使わずに実装できるものでしょうか？
なんとなく、setなどを使うことで可能な気もしますが…

>>388
ああ、>>380ってそういう意味だったのか
数学つよつよのりんごさんが、いつかの解説放送で「Xを下方向、Yを右方向が一番好き」と言ってたから、
「競プロする人はあまり気にしない」は違うと思う
蟻本の著者のこだわりやルールがあって、その変数名を選んでるんだと思う

今気づいたのですが、普通に累積maxを取ればできますね
セグ木必要なかったです

下方向が第1座標、右方向が第2座標だと数学での座標平面を時計回りに90度回転させたものになっていて綺麗だし、普通にループ書けばメモリアクセスも連続する

>>392
画像処理では右にx座標正、下にy座標正をとることが多いから、プログラミングでは左手系がデファクトだと思ってる

こういう宗教戦争が起こるからそもそも競プロ以外で使うべきでない変数名なんだけど

右手系！そういうのもあるのか
こだわってる部分をこだわりがないとか言ってしまって失礼しました。教えてくれた人ありがとう。

OpenGLでは基本的に右手系だし、プログラミングでは左手系がデファクトってわけでもないと思うけどな

左手系って例えば回転とかするとき頭壊れないのか？まあ慣れるかもしれんが

>>359
ありがとうございました

>>373
競プロ系ユーチューバーとしてデビューするといいです

https://dotup.org/uploda/dotup.org2125825.txt
このUnionFindの実装でsizeの時に返り値が連結成分の大きさになる理由がよく分かりません
この場合のparは根とはまた違うんでしょうか

>>399
連結成分の根かどうかで、parの値の意味が少し変わります

・根である：parの値はマイナスで、絶対値は連結成分の大きさ
・根でない：parの値は非負整数で、値は親の頂点番号

普通に実装すると根のparは-1になりますが、
ここに連結成分の大きさを保存しておくと少しだけメモリ使用量を節約できるので、
こういった実装をしたのだと思います

>>400
本当にありがとうございます！
根とそれ以外でparの意味変わってくるんですね…ずっと悩んでたんですが言われると納得しました
そういう問題が本当にあるのか私のレベルだと分からないんですが、万一UnionFindで連結成分の大きさと
各成分の根を求める問題が出た場合はその場で根を求める関数とかを追加していく感じなんでしょうか？

>>401
そんな感じだと思います
追加する場所としては、UnionFind自身とそれ以外の2つの選択肢がありますが、
僕の場合はUnionFind自身を拡張することはあまりないです
既に完成されたUnionFindには手を出さず、
UnionFindの外側で、別のデータ構造（setやmapなど）と組み合わせて解くという感じです

>>398
AtCoderって、同一人物が複数アカウントを持つことは許されていないんじゃ…

chrome portableで
ブックマークが競プロ関係のみの意識高いブラウザを作った

Atcoder Beginner Copy-Paste

不勉強だから数学じゃんとしか思えなかったよ

Problemsでcがレート0だったので、プログラミングっぽい問題はいきなり1800近くになる

D解説読んでも全く分からない

D問題が緑diffという事実

Diffってどこで知るの

AtCoder Problem

今回のＤはABC158のEで既出だからそっちの解説記事探すのが良いかも

似たような問題やったなと思ったらそれもABCか

コピペして青パフォ出したけどEで撃沈したからすげぇ虚しい

D 2019で割った余りを保持する割と典型問題なのに解くのに1時間もかかってしまった

Dは2019*200000回まわすようなうんちみたいなコードでもACできる

E解けなかったの悔しいなー
いくつかのパラメータ持ってDijkstraに落とし込む問題に苦手意識あるな

数時間粘っても問題が解けなかったとき、どうするのが最適でしょうか？
解説を見る前に、「これだけはしておいたほうがいい」みたいなことはありますでしょうか？
たとえば、どういったことを考えたかを文章化しておくとか…
それとも、そういった行為にあまり意味はないでしょうか？

数時間粘っても問題が解けなかったとき、どうするのが最適でしょうか？
解説を見る前に、「これだけはしておいたほうがいい」みたいなことはありますでしょうか？
たとえば、どういったことを考えたかを文章化しておくとか…
それとも、そういった行為にあまり意味はないでしょうか？

>>416
どういうこと？

ABC164のE問題の解説が理解できません
助けてください

>>420
i文字目で終わる数xの右にもう一文字y追加して終端をi+1文字目にすると、10x+yになる
0〜i文字目、1〜i文字目、…、i〜i文字目を用いてできる数をmod 2019ごとにカウントしておくと、
0〜i+1文字目、1〜i+1文字目、…、i+1〜i+1文字目を用いてできる数のmod 2019ごとのカウントが、上のやり方で求められる
一回の遷移に2019回ループするから全体で2019×200000回

わからないとだけ言われてもどこが分からないのかがこっちがわからんわい

「最初に銀貨を Amax(N - 1) 枚持ってることにして捨てていく」という問題と
元の問題が同じとはとても思えないんですよね
私が何か勘違いしている可能性大なので、どこが間違っているかを指摘してほしいです

>「最初に銀貨を Amax(N - 1) 枚持ってることにして捨てていく」
こんな文章は見当たらないぞ

今、信じられないほど全てを理解できました
>>425さんレスありがとうございました
といっても、まだ辺の数が多すぎて間に合いそうにありませんが、
そのあたりは自分で考えてみます

うんちみたいだと思ったのはなぜか気になる

計算量的な意味じゃない？

>>422
まさにこの解法考えて、計算量見積もってあきらめてしまったけど、これでいけたのか…

頂点数125,000、辺の数375,000のときのダイクストラの計算量は
O((125,000 + 375,000) × log (125,000)) ≒ O(8 × 10^6)
という認識で合っていますか？

つまりO(1)

書き方間違えました
8 × 10^6 という認識で合っていますか？

オーダーについてもう一度学んでくるんだ

うっざ
言わんとしてることはだいたいわかるだろ
答えろよ

言わんとしてること全くわからないのだが・・・

演算回数の目安であって計算量ではないという話

演算回数と言えばいいのですね
次からはそう言います

話は戻りますが、頂点数125,000、辺の数375,000のときの
ダイクストラの演算回数は約8 × 10^6ですか？

V頂点E辺のDijkstraの計算量がO((V+E)logV)なのかO(VlogV+E)なのかよくわからないやつじゃん
Fibonacci heapなら後者なんだっけ？？
まあV+E<=500000なら通ると思っとけばいいよ

>>438
回答ありがとうございます
特に実装上の工夫はしていないのでO((V+E)logV)だと思います
＞V+E<=500000なら通る
わかりやすい目安を教えていただきありがとうございます
覚えておきます

演算回数って言葉も微妙じゃ…
ヒープの実装見て解析とかまでしたんかな？って思う

おおよその見積もりで十分だろ
お前はO(N)の演算と言われて10000000*Nの処理をすることでも想像するのか？

オーダーにそのまま数字突っ込むのがそもそもよろしくないという話だが、なんか広まってる以上ぼんやりとつかっている

そのあたりの用語の使い方については誰かに任せることにします
続いて質問させていただきます

ダイクストラの実装には以下のように2つの方法があると思いますが、
計算量的にはどちらも変わらない（両者共にO((E + V)logV)）と考えてよいでしょうか？



1（左）. キューからデータを取り出したときにdp配列を更新する
2（右）. キューにデータを追加するときにdp配列を更新する

できれば�@で書きたい（簡潔なため）のですが、
本質的に�@よりも�Aの計算量が優れている場合は�Aで書こうと思っています
（定数倍程度であれば�@を選択します）

回答よろしくお願いします

>>441
当然それも想定するし、すべきだろ

1の実装はあまり見ないな
計算量は同じだと私は思う. 定数倍は2の方が良好なはず

>>445
競プロの文脈で想像するか？
例題あったら教えて欲しい

>>447
オーダー記法は競プロの文脈でのみ使われるものではないため

>>446
�@の実装はあまり見られないのですね
そうなると、たとえ計算量が同じでも�Aを選択したほうがよさそうな気がしてきました

よくよく考えると、コードの短さ以外で�Aに勝っている部分はないです
定数倍は�Aのほうがいいですし、
dp配列の更新タイミングとキューへの追加タイミングが同じなので書きやすい気がします

�Aで書くことにします
回答ありがとうございました

オーダー記法の使い方に関してうるさいくせにN→∞の省略には何も言わないし定義の理解も曖昧なやつっているよね

普通は2の方が速いけど枝刈りができないようなグラフを与えると最悪同じになる
あと37行目のifを削除してもO((E + V)logV))だと思う

なんか2は負辺あっても正しい答えが得られるらしい（計算量は壊れる）

定数倍的にpython でクラスって実用的なの？

pythonってクラス作ると遅くなるの！？笑えるな

https://github.com/atcoder-live/library/blob/master/mint.cpp
上記URLの公式のmodintライブラリについてお聞きしたいのですが
.x を付けた時と外した時の挙動って何が違うのでしょうか
例えば提出したコードを簡略化したものが下なのですが
https://dotup.org/uploda/dotup.org2128689.txt
このコードで一番上の宣言部以外で .xを外した場合
入力例では通っても実際のケースでWAが多発しました
自分でも色々入力を変えて試したのですが違いが分かりませんでした
回答よろしくお願いします

どの問題？
.xつけたらただのlong longと変わらないはず
外部から直接xにアクセスすることは基本想定されていないと思う

情報が少なすぎて回答のしようがねえ
MODの設定ミスとかa[i] がMODから溢れてるとか
.x つけるとACになるってのがよう分からん

mint n;

と int mを比較するときとか？if (n.x < m)
基本.xとはしないんだと思う

https://atcoder.jp/contests/arc035/tasks/arc035_b
返信遅れてしまってすみません、この問題です
提出コードが大体こんな感じです
https://dotup.org/uploda/dotup.org2128783.txt
このansとsumの.xを全部外した場合はWAになりました

全ての問題を解くときのコンテストペナルティの最小値と、
(そのような解き方が何通りあるかを1e9+7で割った余り)を答えて下さい。

ペナの総和は剰余を取ってはいけない
ペナの総和はMODを超えうる
だからサンプルは通るみたいな

mod 2019での10の逆元って具体的になに？

ヒント:2019+1=2020

202か
加法逆元と勘違いした

https://atcoder.jp/posts/20　にテストケースが見たらないないんですけど
square869120Contest #4　って公式コンテストではないからテストケースはありませんという理解であってますか？

D Driving on a Treeを解いていて
コードテストでは問題ないのに提出するとと全てREになって困ってます

テストケースはないのが普通だよ
手元で考えられるだけ試してみるしかない。人によってはランダム生成したりする
ところで
2
2 1
みたいな単純なものも失敗するみたいだけど? (別の人ならすまん

競プロでWAが出たときのランダム入力データ生成入門
https://betrue12.hateblo.jp/entry/2019/09/07/171628

無向木の問題ならサンプルの頂点番号を入れ替えてみるとかもデバッグの手助けにはなるはず

>>467
別の人ンゴ

>>467
もしかして過去の提出を見てあたりを付けてテストしましたか？
入力のフォーマットが別の問題前提のものになっていたようです。
確かに単純なデータでエラーが出ます。おかげで気づくことができました。ありがとうございました。

>>461-462
ありがとうございます！
ansをlong longに変えたらACだったのでおそらくそれが原因でした
完全に問題文の誤読で申し訳ない…

みんなのデータ構造　オープンソース版だと結構誤訳があって辛いんですが
ラムダノート版だと修正されていたりしますか？

Asprova プログラミングコンテストって美味しい？

賞金も出るし美味しいと思うよ

むしゃむしゃ

ABCのC問題あたりから難しいんだけどアルゴリズムどうやって勉強したらいいですか？

昇順に整列された整数の数列a_1, a_2, …, a_nが与えられるとき、この中からk個選んで（昇順に整列された）数列b_1, b_2, …, b_kを作る。数列bの隣り合う2つの要素の差b_(i+1) - b_iの最小値をmとする。すべての数列bの作り方を考えるときのmの最大値を求めよ。

この問題が解けなくて困っています助けてください

累積和できる？

あ、>>479は>>477に対してね
>>478
mを二分探索すればよさそう

https://twitter.com/superponime/status/1255779675164401665
https://twitter.com/5chan_nel (5ch newer account)

>>478
答えはこんな感じになると思う

>>482
ああ、なるほど！
ありがとうございます

https://twitter.com/kobae964/status/1255834128408211456
東大卒社会人でもスクショ晒し文化を踏襲する人がいることが心証が悪いという意見を強めてしまっていると思うけど
小林弘季さんがどう思われようと知りませんが…
https://twitter.com/5chan_nel (5ch newer account)

「自分が採用担当なら競プロの話してるやつ全員落としそうなぐらい競プロへの心証は悪い」とか公言してしまう人が採用担当になるような会社があったらそんな会社には行きたくないので落としてくれて結構。

競プロ、東大だけ異次元
卓球における中国みたいな感じ
ICPC国内やるか分からないけど、やったら今年は
超激戦になるはず

マジで強いの今年WF行ったとこだけじゃないの

競プロ上位勢は人格破綻者多いしな
心象悪いのは分かる

メインで話すことじゃないからな

二分探索の対象が整数ならwhile、小数ならforで書くといいらしいのですが、
どういうことでしょうか？

>>490
適当に答えると、両者とも正確なループの回数は分からないという前提のもと、
前者は「差が1より大きいとき」という条件式で書きやすいから
後者は「こんだけ回せば誤差がいい感じになるだろう」という考えで適当なループ回数(100回とか)を設定するから
これで合ってる？自分、緑レベルなので信じ過ぎないように

>>491
ありがとうございます！

後者は、一応 while (x >= 0.000000001) みたいに書くことはできるけど、
浮動小数点の誤差が悪く働いて x が 0.000000001 未満にならないことがある → 無限ループになる
そうなるのが怖いからループ回数を設定しておく

という感じで理解できました！

回数としてはどれくらいが適切なんだろう…
2分の1ずつ減っていくと考えたら、相対誤差10^-9のときは最低30回くらいですかね？
50回ほどループすれば安心かな

関数内で巨大なベクタ配列を生成するとREになり、
それをグローバルな配列にするとREがなくなることがあります
その原因がわかる方教えて頂きたいです

スタックとヒープ

>>492
おれは二分探索なら100、三分探索なら200にしてる
実数の問題でTL厳しい問題がそうそうないという認識もあるな

競プロでキャッシュを意識することってありますか

それが主眼となる問題はない
意識にいれとくと定数倍の改善の手助けにはなる

>>495
制約が厳しめでない限り、50でも100でもそれほど変わらなさそうですね
安心のために100にします。三分探索は大きめに設定するというのも覚えておきます
ありがとうございました！

>>494
ベクタ配列の実データもスタックに積まれるんですか？

>>467 >>470-471
無事一部AC/他TLEまでたどり着けました
根から葉までの方向と逆方向の入力がない木の直径の問題用のコードを流用したのが原因だったようです。
ありがとうございました。

巨大ながどれくらいをさすかは知らんが
ベクターのヘッダだけで溢れるなんて普通に有りそうだ

>>501
ベクタ配列のヘッダってそこまで巨大なんですね
ヘッダはスタックに積まれるという認識で合っているでしょうか？

大きさとしては、vector<vector<int>> dp(5000, vector<int>(5000));
なので、計算すると200MBでした

別の可能性を探せ

>>493
ACしたコードのvectorをもういっぺん関数内に戻してもREになるか確かめてみろ

atcoderの環境ならそれくらい普通に確保できると思うが

>>504
普通に通りました
お騒がせしました

どうせ未初期化のNで配列サイズ指定したとかそんなんだろ

解説みても誰かのACコードみても何言ってのか分からないバカなんですけどどうしたらいいですか

誰かに聞く
時間をおいて考える
諦める

なにが分からないのか聞けばええんとちゃうか

>>508
ここで聞けばたいていの人が反応してくれると思います
というか、コロナで暇すぎるので私が反応します。青でよければ

>>508
それがD問題だったらC問題１０問解く

聞くにしてもレベル（色）が近い人に聞いた方が理解しやすい気がする
2色より下の人に分かるように説明できる人は少ない

赤コーダー様の悩みかもしれんぞ

赤コーダーが解説見てもコード見ても分からないってことはなさそう

りんごさんの2718点問題ってどんな風に難しいのですか？

それに答えられる人間はここには居ねえ

高度な数学的知識が要求されている印象 >2718点

ニコニコ動画がりんごさんを推している

どういうこと？

>>516
まずサンプル1の理解が非常に難解で、「ランダムに座る」を解析的に計算可能な形に読み替えなければいけない
それがうまく行くと次は数�Vの積分が待っていて、それを理解することでサンプル1の答えがわかる
ACを取るためにはこの思考をまた天才的なDPに落とし込んで複雑な状態遷移を正確に書けないといけない
という感じ

サブリミナル的に

>>521
回答ありがとうございます
実際のところよくわかりませんが、何となくイメージは掴めました

あの極限値が初等的な議論で出てくるのはビックリ
CFのインタビュー記事でも強い人たちが結構好きな問題として挙げてた

今日はyukicoderとCodeforces

chokudai氏が競プロerの社会性の無さを嘆いてるぞ

競プロがそのまま仕事になると思ってる奴多すぎんの
そんなわけねぇだろ

TLにもそんな感じの学生が多くてちょっと可哀そうになってくる
競プロだけ頑張ってれば成功するみたいな

競プロってほとんど趣味ではあるが
応用が容易ではない
深いところの基礎の補強という認識

赤あればどうにかなるというのも真実な気がする
ほとんどの人には関係ないけど

競プロ強い人はだいたい良い大学で計算機か数学やってるイメージだけど
そんな人の就活は凡人とは違うだろ

ABC155のDが解けないです
x以上の数の個数を数える方法は理解できたのですが、
個数を求めた後にK番目の数を求める方法がわからないです
何とか頑張って解こうとするのですが、複雑すぎて途中で投げ出してしまいます
どのように工夫すればスムーズに解けるでしょうか？

問題はこれです
https://atcoder.jp/contests/abc155/tasks/abc155_d

x以上の数の個数が数えられるならあとはもうすぐで、
「積がx以上になる組がK個以上になるような最小のxを求める」
と考えるとxを二分探索すればよいかと。

>>534
回答ありがとうございます

そのあたりを自分で考えようとすると、
x 以上とか K 個以上とか最小の x とかが混在して訳が分からなくなります

具体的にどう混乱するかというと、同じ数が連続するようなとき、
たとえば数列が { 1, 1, 1, 2, 2, 2, 2, 3, 3 } であって 5 番目の数を知りたい場合、
x = 2 であれば x 以上が 6 個
x = 3 であれば x 以上が 2 個
そして 5 番目の数ということは x 以上の数が何個あれば…あーもう訳がわからない

みたいな感じです
このへんを整理して考えられるようになりたいのですが、
どのように考えていけばスムーズに解けるかが知りたいです

まずこの問題は最初にやるには考えることが多すぎるので、類題で1ランク簡単な「億ます計算」「Handshake」を先にやることをお勧めする
xを決め打って片方の数aを固定した時にx/a以下の数を二分探索→合計すればよい
不等号は頭おかしくなるから最悪サンプル合う方で提出すれば良い

>>536
回答ありがとうございます
解いてみます
不等号が複数絡んでくると頭が壊れるのどうにかしたいです

頭が壊れなくなるなんてことはなくて強い人も壊れる壊れる言いながらやってる

GCJ1C出ます

がんばって

問題の制約に出てくる｜S｜ってどういう意味でしょうか？
今まで絶対値だと思ってたのですが、例えばABC164-Dには文字列Sが入力のとき
制約が1≦｜S｜≦200000なのに200000以上の入力例があります

数字のときは絶対値
文字列のときは文字列の長さ

|S|は文字列Sの長さを表します
200001以上ってまじ？

>>541-542
ありがとうございます！型によって意味が変わるんですね
説明なしで出てくるので常識の範囲なのかもしれませんが、このような
知らない数学記号？が出てきた時はどうやって調べるのがいいでしょうか？
（記号で検索したのですが絶対値しか出てきませんでした）

うーんGCJむずかった
Round2に進むみなさんさようなら

>>545
記号というのは検索しづらいし、
誰かが「競プロで使われる記号の意味」的な記事を書いているわけでもないから、
今のところ人に聞くのが一番手っ取り早いし確実だと思う

色々検索ワード試してみたけど出てこんなあ
一般論としては「-高校」とか「-受験」とかつけたらいいと思う

あ、でもコンテスト本番でわからない記号とかが出てきたら困るか…
うーん、今のところ、これといった解決策が見つからない…

そういやたしかに絶対値で文字列の長さを表すってどこで知ったんだろう

本当に意味がわからないときは質問してもいいと思う

またunratedになるのか

10分遅れスタート

ひでえなほんと

開始を遅らせるアナウンスを開始1分前にするって頭おかしいじゃないの？

なにが1分前にアナウンスしてF5連打やめてくださいだよw
無理がある

他に競プロで出る記号はガウス記号ぐらいかな

>>549
俺は確か集合の濃度から類推した覚えがある

常用できる文字列のノルム的なのが長さくらいしか思いつかない
データ量圧縮したらとかそういうのは強者が考えてくれ

数学的には長さってより同じことだけど空文字列との編集距離って考え方の方がよさそう

Cからやり始めたら俺には難しすぎ
Dのほうが簡単だった

クソゲー Writer みて察した

またlonglongじゃなくてintにして30分以上溶かしたわ
死にてえ

難しすぎる
もう嫌だ

2000↑のパフォーマンスが甘い気がする
ABCやりすぎて少し強い人はみんな黄色になっちゃったんじゃないの

「結論から述べると」の人、問題も解説も嫌い。せめて入試で部分点もらえる位には解説書けよ。

なーにが質の良いコンテストサイトじゃ

CってDegwer？

https://twitter.com/kyort0n/status/1256581801897676803
https://twitter.com/5chan_nel (5ch newer account)

Eリジャッジして順位もう1回出すかそのままでいいじゃん
Unratedの代わりのコンテストでUnratedとかシャレにならないだろ

full-feedbackのコンテストだからそれだと公平にならないとか前に言ってた

しばらく AtCoder 出るのやめるの検討するレベルにひどいな。
この短期間に何回やらかすの？

Cの解説はいいと思う。
全探索で間に合うと気づく所が本質なんだから

Cって10重ループで通るから簡単ですよーって事だったのかな

Eほとんど影響なさそうだしratedだな

>>565
どこに不満があるの？

>>568
もうわざとやってるっぽいから辞めさせろよ

Cは別に良くないか
Dの出題意図の方がよう分からん

っておもったが普段からこんなもんか

>>546-548
なるほど、競プロ用語なんでしょうか…
取り合えずは過去問をこなして経験則を高めようと思います
ありがとうございます。

C問題叩いてるやつは解けなかっただけだろwライターのせいにするのやめなよ

久々にCやりごたえあったな。ライター有能