競技プログラミングにハマるプログラマのスレ 27 YouTube動画>6本 ->画像>2枚

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

１乙！１乙！１乙！１乙！１乙！１乙！１乙！１乙！１乙！

>>1
乙

>>1乙

競プロに関するKENTA氏の見解


SIでも同様(研究開発部門は知らない)
このスレに出現する競プロ否定派の意見とほぼ同じだね

だれ？

>>5
3行で書いてよおねがい

月刊競技プログラミングは役に立たない　特別号：就活編 - beet's soil
https://twitter.com/beet_aizu/status/1277932717347188736
https://twitter.com/5chan_nel (5ch newer account)

これなぁ、たった数社しかも有名企業のみ受けてるんだよねきっと。それで失敗するのは当たり前かと思うけどな。上手くいく方がレアだと思うし、なんていうか甘く見てたのか舐めてたのか分からんけど、もったいないなぁと思った。

やべーところしか受けてないからこうなる可能性はある
今年は特に大変そうなのも気の毒だな

こいつググったらクソイタいの一発で分かるから普通に無理だろ

日本語わからない人しか採用に関わらない外資ならワンチャンある
ただし日本法人はダメ

R社ってリクルートなんちゃら？
競プロerだいぶいっぱいいるよな

I社がわからない。どこだろう？

Indeedかな?かなり競プロerを採ってる印象

今年就活の人は本当大変だな

>>13
ありがとう。ブログの内容と一致してそう。新卒採用サイトが消滅してる
https://indcn.avature.net/indeedtokyoncg

新卒の競プロerさん、有名私大職員がおすすめだよ
IT知識があると滅茶苦茶重宝されるし、まったりホワイトだし、
給与もキャリア官僚とほぼ同じだよ、大手インフラ系の事務職も同様
プログラマにこだわらずに、事務系を目指すのも手だよ
仕事の発注側になれるのも気楽でいいよ

I社やG社は、会社へのコロナの影響大きいのに加えて、外資なので採用人数一気に絞りそう
流石にスペックが色々違いすぎるので、個人的には青〜黄で、インターンもちゃんと行ってて、10社くらいちゃんと受けて全滅、みたいな人がいるかの方が気になる

天才さんも言ってたけど、競プロ人材、もう割と飽和してると思うよ

競プロを主軸にするのは危険だね、あくまでサブなので、別に軸を持っておいた方がよい

仕事に役に立つのは確かだけどコスパ良いとは誰も言ってない

A問題解けるくらいの奴が人口の半分を占める、みたいのが理想的な「競プロ人材の飽和」だけどな

http://2chb.net/r/poverty/1593526576/

Web系には役立たないだろ
Webとかただ調べてコピペして組み合わせてるだけだし

競プロアンチに競プロができる奴はいないという悲しい事実

競プロを主軸にできたら最高なんだけどなあ

まー、必要なものを取ってきて組み合わせる力とも言える
これは必要なデータ構造やアルゴリズムを組み合わせる競プロと共通点なのでは？

競プロはこっちが金払って問題を買うタイプの趣味だよ
ナンプレと全く同じ
それで金をもらうなんて考え甘すぎだや

役に立てばもらえるでしょ。役に立ってないからもらえないみたいだけど
そもそもプログラマーなんてコミュ力というか人の話を聞いて理解する力が一番大事
その点で言えば、日本語禁止コンテストなんてのもあるし、競プロは問題文を理解できる証明にならない

競プロを主軸にしたい？
博士に進学してアルゴリズムを研究すればわいくらでも活かせるぞ！！

競プロのほかに大学の成績も良くて飛び級で英語も出来ても駄目なら何を主軸にしたら良いんだ？

結局落ちてるのってF欄だからじゃないの？

>>8
イキりすぎて就活失敗とかかわいそうすぎる
勘違いさせた界隈にも責任あるよね

なぜAtC○derの就活システムを使わないんだ…
あと企業コン開いてるところもエントリーしてないみたいだし、dwang○とか

G社なんて旬は過ぎたとはいえ幾らでも優秀な学生が来るのに
お山の大将極まれり…

>>5も相まって界隈が動揺しててウケる
イメージ回復に追われるちょくだいさん

gってGoogle？

まあ、IT業界は転職でガンガン上に登って行けるから、
最初に入ったところはあんまり関係ないからな
最終的に一流企業に行ければいいのさ

AtCoderが拾って救済してくれないのか？
さすがにないか・・・

chokudaiと戦うことに躊躇が全くないタイプはpaizaでも目指せば

>>31
強い武器を持つのは結構だけど、それだけじゃダメだろう。そいつが実際どんな奴でどういう理由で落とされたかは知らないけど、強みがあっても他の点で問題があれば総合的には要らないと判断されても仕方ないと思うよ。

面接官「一緒に働きたくない人材いりません」

そして面接官と同類が補充され、
ますます日本の国際的競争力は落ちぶれていくのであった

エンジニアなら普通に強いアピールなると思うんだけど
むしろ自分が過大評価し過ぎてイキったり求められてない業界攻めてそう

アルゴリズムの研究職の人以外で、何か実際仕事に競プロが役立った場面ある？
企業で働いたことないちょくだいの意見聞いてもあんまり信用できない

俺が企業となることだ

大会で見かけたことあるけど普通にコミュ力ありそうな感じだったんだけどな
自分の就活が今から不安になる

景気がヤバいとのニュースが
https://www3.nhk.or.jp/news/html/20200701/k10012490631000.html?utm_int=all_contents_just-in_001
氷河期が再来しないといいけどなあ
20代で、体力とコミュ力に問題なければ、医学部再受験は全然ありだからね!

他業種よりコロナの影響は小さいし採用人数を一気に絞ることはないのでは
この情勢下で安定している分倍率は高くなりそうではあるが

仕事探しはindeed（お祈り）

流石にアレは有名企業だけ受け過ぎでしょ、数も少ないし
しかも今年はコロナ糞ゲーもあるし

とは言え平時ならYとRどっちも落ちるとは思えないけど
タイミングが悪くて気の毒

競プロの文脈でこの人より下っぽい人でもY通ったみたいなのも見たしタイミングというか運悪かったんだろうな

結局正解のある、人が作った問題に対して答えてるだけなんだよね。
地頭が良くても他のところに生かした実績がないと、評価できないわ。

競プロのアンチならよそでやってどうぞ

彼は競プロ抜きにしても大抵の就活生より優秀でしょ
アンチはアンチスレに行ってね

競プロで減点されてると捉えることもできる

受けてる企業見てから言え

競プロしか取り柄が無いと思っている自分よりレートが高いうえ
この人のレートが0だったとしても人材としては自分より明らかに優秀な人がこの辺の企業落ちてるの怖いな

全くプログラミング経験がない東大理系が１日3時間くらい精進したら何ヶ月くらいでAtcoder水色いけるかな

水パフォなら運良ければ1-3回くらい
水色になるなら2-3ヶ月

ほんとに3時間やるなら2月ありゃ余裕
要領いいやつなら1月

1ヶ月だとコンテスト回数4回とかだから平均1800パフォとか必要だぞ
やり始めの頃の成績が足引っ張るから2ヶ月はかかる

1日3時間ワロタ
そんなにやったら誰でも水色なれそう

東大生の中でも適性にはかなり差があるからな
1日1時間で黄色までスイスイ行く奴もいれば3時間やって水色止まりもいる

数学得意な人なら2,3ヶ月で行けそう

会津とか東工大じゃない○○工業大学の人たちで割と競プロできる人多いの非自明なんだが
そのへんの人たちがフェルマーの小定理なんか分かるわけないという偏見を持ってた

競プロできるなら大学受験かなり戦えるだろうにな
実家から近い大学に行ったんじゃない？

競プロを入試でやったら面白そう
中国はもうやってるんだっけ

早期入学ってところ見てないのかな

入学時に知らんでも勉強すりゃわかるだろ

東大理系なら最初からガンガン青パフォ出せそうな気がするけどそうでもないんかな

>>68
そりゃないだろ
競プロは学科の1科目程度だよ

>>73
東大入試の問題の大半がatcoder800点問題くらいの難しさじゃない？

>>74は数学と物理くらいを想定してる

お受験マスター様がやってくる予感

2012時点で「レッドコーダーは司法試験より難しい」がまことしやかに言われてたしな

あの頃のレッドコーダーって今の黄くらいだと思うけども

なろうかな

>>74
東大入試はもっと簡単
典型ばっかでAtCoder500点もない

atcoder800とか捨て問でしかないな

AGC022 A、なんでabcの次がabdじゃなくてabcdなのか誰か教えてくれない？

辞書順でググれ

>>74
競プロだけで入れる大学があるのか？
就職も競プロの成績だけで採用することはない
採用される人は他の部分も優秀なんだよ

日本語嫁

>>83
キミF欄卒の灰coderだろ

昔の赤が今の黄くらいってマ？
UTPCとか難しすぎる感じしかしないが

なんでそうなったのか誰か証明できない？
個人的には、難化というより長期的に見て出題側が安定してきたのではないかと

>>86
「昔の」と言った時点でtopcoderを指すことになるけど、topcoder div1は昔の600点問題と今の300点問題が傾向似てる
だから「topcoder内で言えば」昔の赤と今の黄が一緒くらいってのはある程度正しいね

>>87
証明ではまったくないが、赤の価値とかレートのディストリビューションを保証するためには難化せざるをえないでしょう

大昔の東大数学が簡単なのと似たようなもので
典型問題のパターンが認知されてくると問題自体の難易度は上がる

うそ問題つくった これって解法あるかな
beetくんは就活がしたいです。beetくんはN個のスキルS_1, ..., S_Nを持っており、Mつの会社C_1, ..., C_Mに面接を受けに行きます。
面接ではスキルをK個までアピールでき、会社C_jはアピールされたスキルS_iに重みC_jiをつけた総和がL以上になった場合内定をくれます。
beetくんが最適なアピールの仕方をした場合、何社に内定をもらえるでしょうか。

入力
N M K L
S_1 ... S_N
C_11 ... C_1N
.............
C_M1 ... C_MN

普通にC×Sの大きい順にソートしてO(NMlogN)

身内ならキモいし、無関係ならこんなとこで名前使ってやんなよって思うし……

トータルクソキモいから消えてください

才能も（多分精進の量も）全く違うレベルだって分かっていても、中学生で赤がいるのにいい年した自分がこの色かって思う瞬間ない？虚しくなることないか？

悔しがれるのはいいことだ
負け犬根性が身につくと何もできなくなるからな

面接じゃスキル問われないでしょ履歴書に書くし

>>95
履歴書に何が書いてあってもホワイトボードコーディングは面接に含まれうると思うが、、、

>>96
たしかにそうだな
スキルを選んでアピールする面接を思い浮かべてそれには当てはまらないと思った

与えられた a, b について、(a*x + b) mod 1e9+7 を最小化する x ってどうやって求める？
ただし、
1 <= a < 100
0 <= b < 1e9+7
0 <= x < 1e9+7
とする。

競プロの文脈だと x を全探索するのは TLE になりがち

拡張ユークリッドの互除法？

制約抜けてないか
その書き方だと x = -b * a^(-1) (mod 1e9 + 7) で終わりに見える

数学の問題だね

今日の22:35-のCodeforces div.2に出よう

>>102
出るわ
ABCをDぐらいまでしか解けんけどdiv.2って難しそう？

cくらいまでは解けるんじゃない

3完くらいじゃね

>>102
物○好きさん5chでも宣伝わろた(楽しみにしてます！)

もうここTwitter競プロ界隈ヲチスレになってんじゃん
ネヲチにそういうの建てたら？

>>107
効いてる効いてる

テンプレもまともに貼れないやつがスレ建ててるあたり大量に流入してきてるんだろうな

ヲチスレ化してんならもっとじゃんじゃん名前が出てくるだろ
これだけ濃いメンツが揃ってる界隈なんだから

ヲチスレとかクッソしょうもないのでここ以外でやれ

面白い競プロerを１日１人紹介していきます

>>112
はよ

>>108
なにが誰にどう効いたと思ったんだ…

「効いてる」ってのは便利な言葉で反論したら効いてると見なされ反論しなくても効いてると見なされる

「効いてる」自体には何も主張が含まれていないのも強い

気の利いたコメントを心がけていつも滑ってる人いるよね
Twitterで頑張ればいいのに

>>114-116
一人で書いてそう

>>39
橙とかはいらないんだろうなぁ…
つかこういう時に「ウチに入りなよ」って人が皆無なあたり競プロerの社会的立場の低さを感じるな

最近覚えた効いてるって煽り文句を使いたくて仕方ないんだろ察してやれよ

AtCoderの競合サイトを作って競プロerを採用してあげればいいんじゃない？
良いサイトができると思うよw

邪推を減らす意味でもidあった方がいいと思うんだけど

IDなんてあってもなくても同じ量の悪意が飛び交うと思うよ

old-boys be malicious(´・ω・`)

IDあっても良いとは思うけどどの板に行くの

プログラム板

IDあったところで飛行機飛ばして終わりなんだよなあ

ワッチョイが必要だな

末尾だけでよくね

心でフィルタリングするからいりません

匿名で色が表示される掲示板を作ろう

AtCoderはOAuth対応してないだろ

発言者の色分かる匿名掲示板ほんと欲しい

自分で作ればええやろ

オレンジくらいで既にあんまり匿名じゃないんだよな

>>134
そんな技術力があったら競プロなんかやってないぞ

真面目に考えるとTwitterの連携みたいなやつが必要になるのね

https://twitter.com/koyumeishi_/status/1154865527770120192
https://twitter.com/5chan_nel (5ch newer account)

フムー
AtCoder→TwitterIDを関連付けられるから、Twitterと連携すればいけそうだな

そこまでやるならTwitterで良くない？

そういう掲示板を作ろうとする人も参加者だろ
そいつにわからないように匿名性を実現するのは
AtCoderがAPIを提供しないと無理

スクレイピングでいいですよね（ﾊﾅﾎｼﾞ）

問題を典型というか知ってる知識の組み合わせに落とし込むの難しいね

プリム法とかクラスカル法をライブラリ化してる人って最小全域木を返すようにしてる？ それとも最小コストを返すようにしてる？

ごちゃごちゃ言ってる連中は匿名掲示板向いてないんじゃない？
Twitterの鍵垢にでも引きこもってればいいのにね

匿名掲示板は勿論のこと
まとめサイトだの2ちゃんねるコピペ集だのに興じたことの無い者だけが
匿名の発信者に石を投げなさい

pairとかで両方返しときゃいいんじゃね(´・ω・`)

作ってないけど作るなら最小コストと全域木に含まれる辺のidたちを返すな
長さが辺数のvector<bool>でもいいかも

>>145
元ネタは「だけが」じゃなくて「から」だよ
つまり1人でも条件を満たしていれば、その人から投げれば全員投げられる

>>100
すまん問題おかしかった


(a*x + b) mod 1e9+7 を最小化する x ってどうやって求める？
ただし、
1 <= a < 100
0 <= b < 1e9+7
0 <= x < T
0 <= T < 1e9+7
で、a と b と T が既知とする。


が聞きたかったこと

aが比較的小さいからa*x+bを1e9+7で割った商を全探索すれば良さそう

単純にfor some n in Natural num, x=round((1e9+7*n-b)/a) &&0<x<T
でmin探し全特攻仕掛けるとかじゃ駄目なん？(´・ω・`)

中身が頭に入ってこない文体やめろ

-ax-b mod 1e9+7が最大だからagc045Fみたいに光線打つとか？

最小になるのは繰り上がりが起こるとき限定で
繰り上がりがせいぜいa回だから全部見たら解けるかな
と思ったけど商を全探索と同じだった

ブログだけ見てた頃はchokudaiさん大好きだったな

>>154
繰り上がりが起きないときが最小なケースもありえますよね？（つまりbが最小）

したがって以下が解法でしょうか
for i in [0, a]
　i*x + b が 1e9+7 を超える最小の x を答えの候補に入れる
　そういう x がなければ x = 0 を答えの候補に入れる


でも、ある i について
a*x + b = (a-i)*x + i*x + b
だから、i*x + b が 1e9+7 を超えるとき
a*x + b mod 1e9+7 = (a-i)*x mod 1e9+7
ですよね？
(a-i)*x mod 1e9+7 の範囲が全探索できるほど狭いというのはどうしたら分かるでしょうか。
頓珍漢なことを聞いていたらすみません。

多分解法が間違ってる
> i*x + b が 1e9+7 を超える最小の x を答えの候補に入れる
じゃなくて
[ ax + b が i * (1e9 + 7) 以上となる最小のxを答えの候補に入れる ]
が正しいと思う

>>157
あー x を増やすことで a*x + b は a ずつ増えるわけだから、a*x + b が 1e9+7 を超えたときにその超過分は最大でも a、つまり a*x + b mod 1e9+7 の範囲は 0 から a まで、ということですか。
皆さんとても親切にありがとうございました。

グラフィッカルに考えりゃp=1e9+7とする時
y=ax+bとy=pk(kは自然数)の交点近くの格子点？だかをxのopt臭い点として扱ってる
aによるcompute時間の推測は(xのopt点の候補数)<=sup{a*x|x in [0,T)}/pだからっしょ
リニアの傾きaが大きい程同一x-ドメイン内で現れるレンジ上のpkが多くなっちゃう(´・ω・`)

競プロ界隈に限らないんだがTwitterアニメアイコンとかが多すぎる。
自分が好きでそのアニメアイコンにしてるのは分かるんだけど、自分のツイートのせいでそのアニメのイメージを下げる可能性があることを自覚して欲しい。

アニメもそうだが、アイドルとかのアイコンはほんと風評被害だと思うわ

>>159
？
解決してることを自分なりに言い直してるだけ？
それとも上に出てる何かを訂正か否定かしてるの？

触るな

多分そのアイドルのアンチなんでしょうね

>>151,159は論外として（同一人物だよな？独自の語法使い過ぎだし顔文字がキモいし二度と書き込むな）

>>150,154
「商を全探索」じゃなくて「剰余を全探索」じゃね？

おそらく自分じゃない女の顔写真をアイコンにしてる奴見たことあるけど、あれアイドルだったんだな

テメェかテメェの彼女のゲボ面に差し替えりゃ良いのにな

>>165
商だと思うよ
ax+bが0以上になる最小のx
ax+bが1e9+7以上になる最小のx
ax+bが2e9+14以上になる最小のx
...
という感じで候補を探していくんじゃないかな

商決めたら剰余も決まるから同じことです

>>165
おつkay分かった(´・ω・｀)

>>167-168
すみませんでした
僕も二度と書き込むのをやめます

殺伐しすぎ馬鹿じゃねーの
ようかんマン参上させたろか？

5ch基準じゃ至って平和じゃね

>>160
本当に気持ち悪いのは中国人なんだよ
アイコンを日本アニメのエロエロ美少女にした上でニックネームもアニメキャラや声優の名前にする
マニアックなやつはしゃべり方すらアニメっぽくする
あいつらのせいでもともと好きだった日本アニメに対しては低俗なイメージしか抱いていない
ほんとシナ畜のセンスのなさは救いようがねぇ
かくいう俺もシナ畜の一匹なんだけど

専門板基準で荒れてる

>>160
アニメはどうでもいいが自撮りグロ女装画像はほんとやめて欲しい（RTで周ってくる）
競プロerなんであんな女装好きなん？

アイコン非表示にできるTwitterクライアント需要ありそうだな、、

アイコン地鶏女装、ほぼ個人特定できて草

>>175
ほんこれ

女装が嫌いな男子なんていません！

女の子みたいな格好してみたいならわかるけど女装はないわ(´・ω・｀)

女装は別に良いどころかniceじゃね？
ただの自分じゃん

どっかで拾ったみたいな3次元美人とか版権アイコンの奴は全員死んだ方が良いと思うが

お前らが見てる世界がさっぱりわからねえ
俺の垢だと女装もアニメアイコンも存在しねえぞ
フォロー少なくしてるから助かってるのか

>>181
ないわ
女顔とかちゃんと化粧してるならともかく汚いオッサンの女装とか見たくないわ

アニメアイコンより絵師アイコンのがよく見るが

気持ち悪いアニメキャラやら自撮りやらってどっちも結局
昔から言われてるツイカスは自己顕示欲の塊で糞って話ちゃうんか

｢慶應卒の学歴なんていらない｣10代起業で成功する子の共通点
https://www.excite.co.jp/news/article/President_35457/
起業で成功するキャリア形成の仕方とは？ 元プロサッカー選手で起業家の鈴木啓祐氏に聞いた
https://sogyotecho.jp/career-development/
【アプリ開発で起業】必要な心得とマネタイズ方法のすべて
https://www.dreamgate.gr.jp/contents/column/application-development
学生起業家が開発、「人を軸に本を探すアプリ」とは？読書通じて「考える力」養って
https://newswitch.jp/p/20168
島田商高生がアプリ考案、発表　ＩＣＴ起業家育成プログラム
https://www.at-s.com/news/article/local/central/730010.html
医師コンビが「治療用アプリ」で起業、禁煙に続き高血圧治療アプリを開発
https://diamond.jp/articles/-/229375
好きが高じて“カレー起業”、キャッシュレス決済アプリ「TOKYO MIX CURRY」の挑戦
https://diamond.jp/articles/-/215868

AtCoder以外が主戦場の人ってどれくらい居るの？

Kaggleやってる人ってこういうとここないのかな
つーかKaggleやってみてー

そんならアイコン自分で描けばよくね
前chokudai監禁絵書いてたやつは5年くらい練習してたみたい

>>187
トップコーダーマラソンの専門家いるんじゃない

アイコン程度でそこまで不快になるならもうTwitterでの情報収集は諦めればいいのに

Codeforcesのほうが主戦場って感じがする。AtCoderは遊び

みなさんが水色になった時って、ABCは基本的にDまでは解けて、調子良ければEもいけるみたいなレベル感でしたか？

今年のすべてのCS分野に精通している社のインターンの選考見たらむっちゃ競プロw
競プロはやっぱりコーディングテストの役に立つね
（その割には競プロerでインターンに行くやつそこまで多い印象はないがやはり選考相当厳しいのか…）

水色になった時はABCはDまでしかなかった

秋葉さんといもすさん居るんだよな

Eが水Diff以下の時はEまで、青Diff以上の時はDまで速解きしてれば水にはなれる

https://atcoder.jp/ranking?f.Country=&;f.UserScreenName=&f.Affiliation=Preferred+Networks%2C+Inc.&f.BirthYearLowerBound=0&f.BirthYearUpperBound=9999&f.RatingLowerBound=0&f.RatingUpperBound=9999&f.HighestRatingLowerBound=0&f.HighestRatingUpperBound=9999&f.CompetitionsLowerBound=0&f.CompetitionsUpperBound=9999&f.WinsLowerBound=0&f.WinsUpperBound=9999

semiexpってどなた？

たとえば、会社の中で自分だけが水色だったら
水色のレベルのコードかけると思っているのかな？

水色は水diffそこそこで解くか、青diffの1個前まで早解きかな
...茶青...みたいなのだと早解きで青パフォ出たりする

アニメキャラの口調で喋ってる人は何を思ってそうやってるんだろうか
自らをキャラクターに投影しているんだろうか
厳しい

黄色になってratedが消えてからモチベが無になってしまった
みんなどうやってモチベ維持してんの

AGCに向けてがんばればええやん

前まではCodeforces って言ってたんだけどもこっちもRated少なくなってるしなあ

>>203
黄色まで何ヶ月かかった？

今ってARCってやつはなくて企業コンがそれに相当するの？

>>206
半年

>>208
歴ゼロから半年なら大半の東大生超えてるし強い
天晴だ

つか特定されうるくらい少ないと思う

ぐろふぉってAtCoder緑レベルで出ても楽しい？

知らん
今回のぐろふぉは告知が不穏だから楽しめるか事態が怪しい

普段はdiv1+div2回のレベルだから全く解けないってことはないと思うけど今回は告知がやばい

告知の畳まれてたとこ見て盛大に草生やした

これな
As a tester, this round gave me PTSD.
As a tester, I am very happy that I won't participate in the official contest.
As a tester, I can confirm that I am now expecting all contest organizers to pay for my therapy.
As a tester, I am very happy that I can enjoy others suffering in the contest.
As a tester, I agreed to advertise the contest even if I don't like the problems. Please participate!
As a tester, I tested the round.
As a problemsetter, I set a problem ＼(≧▽≦)／
As a tester, where's my t-shirt?
As a tester, I want to advertise our new song!
As a tester, I recommend testing.
As a tester, I tested limits of my Mental health.
As a tester, I recommend you solve as many problems as possible.
As a problemsetter, I am sorry

コンテストの告知ページでネガキャンするの普通に理解できないんだけど、どういうノリなんだ？

でもめちゃくちゃupvoteされてるからついてけてないのお前だけやで

4000に凄く簡単な問題が置いてあるだけとかそういうんじゃないのかねぇ

>>211
ぐろふぉってたまに聞くけど何？
ググっても出てこない

>>219
https://w.atwiki.jp/projecthikky/pages/139.html
Grobal Round＝ぐろ
Educational Codeforces Round＝えでゅ
Codeforces＝ふぉ

コーナーケースが多いとか実装の場合分けが面倒とか
そういう雰囲気を感じる

結果はパズルコンテストでした
正直全く面白くなかったんだけど普段数学ゲーとか叫んでる人たちもこんな気持ちなのかしら

エアプ逝ってよし

誰

逝ってよしとかめちゃくちゃ久しぶりに見たわ

ぐろふぉ前回もアルゴリズムより発想力寄りの問題だったんだよな
AGCに近い感じかね

>>220
サンキュー

クッソ簡単そうなC解けなくて涙がでますよ

Cは制約に気付いて何でもできる状態になり終了

CとかEとか実装問題が出たけどどうでしたか

青なのにE問の謎WAが取れなくてごめんなさい…

topcoderのdiv2 H、div1 E〜HってAtCoderで言ったらどのへん？
幅があるのはわかってるので、期待値というか期待感として

Eって0あんのね

サンプルに0がないのはちょっと意地悪ではあるな

>>231
俺か

0って関係あるの？

非0 だけで作る時に負にしかならない時は 0 があると 0 にできるとか、どうやっても 0 になる場合とか

絶対値でソートしてるなら、0でバグることは無いはずだが
普通に実装すれば影響はない

diffの数値ってどこでみられる？

解説PDFの
min(x,y) + min(a_k ,y) <= min(x,y) + min(x,a_{k+1} )
ってx = 1, y = 2, a_k = 10, a_{k+1} = 11
とかだと成り立たなくね？

これは言い訳なんですが最近レートデフレし過ぎじゃないですか
ユーザが成長する限り仕方ないとは思うんですけど

>>240
って思ったけどx,y >= a_kの仮定があるか、すまんこ

毎週レート下がるだけだからモチベ下がってきた

あーやっとEのバグ分かった
正の数を取って負の数を入れたものと、負の数を取って生の数を入れたものを比較してたんだけど、積じゃなくて積のMODで比較してたわ
そらバグる

故意にレート下げる行為って荒らし行為ではないんだろうか。
まあ故意かどうか判別する手段無いし取締るのも無理だろうけど。

レート下げる意味とかなくないか？

こどふぉで灰色底辺まで下げて一気に暖色に復帰する遊びしてたひと見たことある気がする

全然問題ねーだろ
ひがみか？

「あー灰まで下がったー」って言いふらしてるならお友達付き合いとしては荒らし行為かもな

まあやりたければどうぞご勝手にっていう感じだよな、特に害は無いし
荒らしかどうかは運営に判断してもらって

数人がやるだけなら問題ないと思うんだけど、レーティングって相対的なものだから何かしらの影響は与えてるんだろうなと思う。
極論自分以外が0完とかなら金パフォとかでるんだろうし(ほんまか？

レート何も気にせずコンテスト中に適当に解いてる奴もいるだろうし何ともいえない

毎週末AtCoder関連の用語よくトレンド入りするし企業コンテストかなり宣伝効果ありそうだな

>>245
AtCoderにそんな人いるの？
引退とか言ってアカウント作り直してるアホならたまに見るけど

強くてニューゲームですかね・・・

ABC173のE問題、やっとAC通せた…
これが安定してACできる上位はどういう思考回路をしてるのか気になる

逆にどういう遠回りをしてしまったのかが気になる

eはやるだけって感じだが、場合分けにはまると辛そう

>>257
サンプルのケースから考えていったけど、いろんなケースに対応するために場合分けがいくつも生まれてバグも同時に生まれ、最後まで解消できず終了という感じ

Eは0を分けようとしたら場合分け増えて死んだわ
負と非負だけで良かったんだな

負と非負に分ければ十分てのも知見だけど3通りに分けちゃったとしてもゴリ押せる力も必要だと思うんだよな

無向グラフに閉路じゃないパス描ける？

描ける

>>263
！？
どうやりますか？

質問の意味がわからないんだが…

辺が1つ以上あるグラフならその辺をパスとすればよい

これ数学的トリビアルに成りませんか？閉閉閉閉>ヾ(´・ω・`)

まず無向木と称した
方向付きの木を作る
方向は根から葉へ固定する
その木の上でパスを作れば閉路ではない
パスになるし元の無向グラフ上でも閉路ではないパスになる

条件を満たすパスを網羅するのは
さっきの無向木でまず最初に通る枝を固定してdfsする
さっきの無向木に入れなかった枝をパスの最初に固定して探索する
枝に番号ふって重複を防ぐ

>>262 と >>268 の意味がわからん
どんな問題をどう解こうとしてるの？

無向グラフのどんなパスでもいいから閉路でないものを構成すればいいなら >>266 でFA
すべての辺を使うとかすべての頂点を使うとかの制限があるならオイラー路とかハミルトン路とかの有名問題になると思う
全列挙とか数え上げ(ではないだろうけど)は難しそうな気がする

それが競プロの問題なら、制約がなければNPだけど制約をつけるとPになる問題かもしれないし、普通にNPだけどNがとても小さい問題かもしれない

ってこれNとPでNPみたいに見えるな

与作が木を切る
閉閉法

今更Cが解けた
頑張った

えらい

よしよし

Codeforces: ここまで解けたけど別にそんなに難しくはないな…あれ、みんなあまり解けてないな
AtCoder: これ解けるとか天才すぎる、自分の才能が怖い…え？みんな解きすぎだろどうなってんだよ

こうなりがち

こどふぉだと自分の解くスピードが遅い気がする。
英語のせいか

この前のDってどうやってといた？
解答見ても自分と全く別のでよく分からない

本当に聞きたいならコンテスト名くらい出せや

解答が普通なんだから普通じゃない自分の方法を書くべき

こっわ
やっぱりいいや

俺が優しく教えてあげよう
ABC173-Dのことだよね？
まず、フレンドリーさが高い人から順に到着するとする
彼らの番号を1,2,…,フレンドリーさをa1,a2,…とする
その時、最初の人は心地よさが0
2番めの人は心地よさがa1
3番目以降は、一番心地よさが高くなるところに入るようにする
そうすると答えはa1+a2+a2+a3+a3+…になる

なんで野獣先輩がイキスギィっていうだけの動画で我々は笑顔になっちゃうんだろうな、不思議だよな

>>283
これは解説の方法じゃないの？

>>285
解説の方法だったら何なの？

chokudaiさん昼から飲んでるの？

自分も解説と同じ方法で解いたな どんな別解があるんだ？

区間をpriority_queueにぶっ込む

>>289
なるほど
確かに式変形するパートが減って楽そうだな

自分もよく分からんかったからpriority queueに突っ込んだわ

ソートして順番に並ばせるのがよさそう
↓
紙で何ケースか試すと>>283の式が出てくる

解いた時はこんな感じだったな

>>282
喧嘩腰のやつは荒らしだから無視してNGにでもぶち込んどけ

>>283
解説が言ってるのこういう事だったのか
横からだけどありがと

NGワロタ

仕様書無しさん はNG推奨

今難易度茶色から解いているんだけど、同じ難易度でもABCよりAGCの方がきついんだが、そういうもん？

喧嘩腰が嫌ならTwitterで馴れ合ってくれ

>>297
AGCの出題は考察が重視されるから
考えるの苦手だと典型重視のABCのほうが楽に感じるんじゃないか

ソートした状態だと2人目以降はどこかに入るとこの時点で自分が一番小さいから区間が2つ出来る
その区間をpriority_queueに入れて取っていったな
よくよく考えるとpriority_queue入らなくて解説の式が出てくるんだけど

>>297
>>299
あとAGCは普段ABCで茶diffまでしか解けないような層が少ないから、それで低く出てるのもあると思う

考えるの苦手 ← 馬鹿の婉曲表現

強い女性競プロerっているんだろうか
緑以下の人なら何人か見た事あるけど

黄↑は特定できるレベルで少なそう

人のセクシャリティをネタにしようと思ってるわけでは全くないが、hos_lyricって女の人じゃないの？
TCO19のTwitchのチャットで外国人が同じこと聞いてたけど答え忘れた

https://tco19.topcoder.com/interviews/lyrically

これは…

マジでヲチに行けよ

競プロ会の姫とか競プロアイドルとか、将来そういうポジションができそう

女性ユーザー増加のために新色ピンク導入を宣言→炎上、まで読めた

自由色になってピンク指定しろ
今もmolamolaとmulgokizaryがピンクだろ

暖色はほぼいないんじゃないか
青なら何人かいるらしいが

Atcoder版ちょまどの登場が待たれる

女装した男に見えてしまったが本当に女なのか？

界隈から女を遠ざける直球ムーブ

>>298
こうゆう意識他界系の権化嫌いじゃない(´・ω・｀)

けんちょん、アイコンと少しイメージがちがった

アイコンのイメージのままの奴の方が珍しいだろこの界隈

め◯アイコンの標準的中身じゃねーの？

きびしい

ARCAGCまだかなあ
8月に1回くらいはあってほしい

夏は rated 砂漠のイメージが

ABCの方が集客効果あるんだからARCは企業コンじゃなくすればいいと思うんだけど
そもそもなんで普通のARCは無くなったんだ

>>312
橙にアイコンが女性の人いるけどあの人違うの？

>>318
典型的なドゥフヲタだから顔出しやリアルタイムトークは向いてない
記事や本で留めておいた方がいい

>>325
マジならインターネットをやめた方が幸せ

プロフィールにtkって書いてある人なら恐らく某男子校だからそういうこと

>>326
chokudaiさんのトーク力がなかったら、微妙な配信になっていた感が否めない
そういう意味だとゲストはトーク慣れした配信者やVTuberがいいかもな

じょえチャンネルにけんちょんさん出て欲しい
面白い事になりそう

あの人が「○○君可愛い！！尊い！！」とか言ってたのか
そうか…

ひどいルッキズムだ

>>331
いつまでやり続けるのが見ものだな
大学生かと思ってたが、社会人だったんだな
いつ働いているんだろう

なんでヲチに行かないの？

>>328
女性か女装系のどっちかかと思ってた
アイドルの写真使ってるだけなんだな

怖えー、アイコンとリアルの顔のイメージを一致させないとだめなのか

彼NTT数理リサーチャーという事実

想像以上にデュフってた

もしもtwitter自撮り実写アイコン必須になったとして、競プロTLを想像し給え

もしもtwitter自撮り実写アイコン必須になったとして、競プロTLを想像し給え

人の顔で笑うのはやめようよ、自分に返ってきちゃうよ…

チー牛「チー牛！チー牛！」

これと同じ

ルッキズム

知らん人が自分の写真をプロフィール画像に使ってTwitter発言してたら嫌だよなあ　とは思う。

肖像権が云々

Atcoderというか競プロって、典型解法覚えたあとはそれを組み合わせる練習するってところがかなり大学受験の数学と似てる印象抱いたんだけど、みんなもそう思う？どっちの場合にもそういう枠組みで捉えられない天才がいるところもそうだが。。。

天才以外お断りパズルをとりあえず考えなければ大体そうじゃね、
水色の意見なのであてになるか知らんが
個人的には競プロ版青チャートor1対1対応の数学が欲しいな、同一典型パターンが何問が連続で集中的に演習できるやつ

エイシングさん、賞金ないのに個人情報入れるわけないよ

Web系だけでなく、いわゆるJapanese Traditional Big Companyへの理系就活で競プロが役立った例はありますか？

保険会社のアクチュアリーとか

ユーザー系、メーカー系SIerでもいいの？

いわゆるガクチカにはなるだろ

>>337
ここ競プロで入れる？

学歴は？

>>354
競プロだけ

赤なら入れそう(適当)

ユーザー系、SIerでもいいです！
いわゆる部活頑張ったとかのと同じような感じですかね？

>>337
研究者？

競プロは研究の役に立つ

競プロは競プロの役に立つ

競プロは人生の役に立つ

競プロは最高の人生のために役に立つ

競プロで人生破滅してる人もいるじゃん
と思ったけどそういう人は競プロやってなくても破滅してるか

破滅と呟けるうちは破滅してねえから大丈夫だろ

競プロでどうやって人生破滅すんねん…

競プロ以外何もやらず、暖色にもなれずが一番破滅してそう

競プロ暖色が就活全滅で破滅

戸田英志 - PINK RICH ［Official Music Video］


【課金勢に物申す】ゲームに課金してる人とかマジで無駄だよなwww


【衝撃的な事実】なぜパチンコに通う人で成功者は一人もいないのか？


【お金無い人必見】失敗して借金とか一切なし！誰でもリスクゼロで始められるビジネス３選！


【超大切】これをすれば起業は失敗しない！戸田英志が行っていた起業３ポイントはこれだ！

貴重な青春を競プロに捧げて就活すら失敗するってどんな気持ち？

競プロしてなかったらMMOして破滅してたからまだマシ

>>336
文盲か本人

競プロで就職した人がそんなに仕事楽しくなさそうなのを見るとどうすればいいんだ

>>372
これマジ？

仕事が楽しくないだけだよ
競プロ関係なし

ICPCとかめちゃくちゃ青春だと思うんだけど

>>344
発言するどころかネカマして外人引っかけてたら相当嫌だろうな

競プロ暖色の地頭があればクオンツかアクやったほうが待遇はいい。逆にクオンツやアクチュアリーは競プロやったらすぐ暖色になりそうな人が多いけど。

競プロと仕事はそりゃ別だろう
仕事は楽しくないこともしないといけないから

>>377
そうかあ？
アクチュアリーもクオンツも業務経験が物を言う世界だと思ってた

アクチュアリーでKaggleやAtCoderやってる人はそこそこいる。GAFAやPFNは別だがプログラマとして搾取されるよりアクやクオンツになって趣味で競プロやるのが楽しそうに思える。

>>378
競プロどんなに強くてもつまらん仕事しなきゃならないって悲しいだろ
人生のかなりの時間は仕事して過ごすんだし…

>>378
何のための競プロ採用だか

すべてたのしい理想的な職場があるのか？想像上以外で

>>378 は仕事が全部楽しくないって言ってるんじゃないと思うんですけど

>>381-382
面白すぎるだろ

競プロはネトゲという前提を忘れてる奴多くないか

ゲームと仕事の差に苦しむ奴も沢山いるだろうからな

アクチュアリー試験、結局統計とかの数学出来るかどうかなので、特に競プロ関係ないがち（相関はあるけど）

数学強い→競プロ強いとなるが、逆は必ずしも真ならずかもな
いや、多少の保証はできるか 数学だめなら暖色とかなれないだろうし
それはともかく、まだ発展途上だから俺達が盛り上げていくんだぞ

理学部数学科を出てもプログラムできない人は山ほどいるだろ

整数NをL以上H以下の整数の集まりに分割したい。
ただしA+BをAとBに分割するときA*Bというコストがかかる。
コストを最小化するための分割方法はどのようなものか。
解がない場合は考えない。


半分に分割し続けるのが良いかなと直感では思ったが、証明ができない。
有名問題っぽいので考え方分かる人がいたら教えてください。

>>391
6を2以上2以下の整数に分割するとき、
6→3,3→(1,2),(1,2) コスト13
より
6→4,2→(2,2),2 コスト12
の方がコスト小さいからそのやり方は正しくないでしょ。

>>392
すみません……

a_1,...,a_nに分割するコストは分割する順番によらずΣa_i*((Σa_j)-a_i)/2=(N^2-Σ(a_i)^2)/2だからa_iの2乗和を最大化すればいい
だからたぶん各a_iができるだけ大きくかつ均等になるようにするとかが答え

a_i の2乗和を最大化するのであれば a_i はなるべく偏っていた方がよいのでは？
例: N=6, L=2, H=4 のとき 6 -> 2+4 ならコストは 8 ですが 3+3 ならコストは 9 です

できるだけHで埋めて、余りがL以上ならLを1つ用意して終わり
L未満なら調整してどうにかする
例えばN,L,H=100,6,8なら分割は13個で、8×12+4なので最後に4が余る→8×11+6×2に調整
N=97なら8×12+1→8×9+25→8×9+7×1+6×3
これが嘘解法でなければN,L,H<=10**9でも解けそうだが果たして

>>395
そうね
後半は適当書いた

>>397

L=1

問題文読めてなかった

>>395
偏ってた方が良いってのは、LとHを沢山作ったほうが良いってことか？
N → L,H,L,H,L,H,L,H,...
証明わからん


>>396
それ>>394と一緒ちゃう？

>>401
なんで一緒なんだよw
>>395当てはめたら俺の実装なら2,4になるわ

>>402
ああすまん全然読めてなかった

貪欲なんて未証明で投げなよ女々しい

ABC 6完安定する人って色でいうと黄くらいのレベル？

ABCの青問題が全部解けたらそれだけで黄色になる

自分は黄色中位だけどABCは基本全完できると思う(し、実際ほぼ毎週してる)
たま&#12316;にできない回があるが
でもABCとAGCで見てる能力がちょっと違うように感じてるから2000overでもABC全完安定しない人がいても驚かないな

&#12316;！&#12316;！&#12316;！
いあ&#12316;&#12316;！いあ&#12316;&#12316;！はす&#12316;&#12316;&#12316;！

この文字化けなに？

あと結局>>391の想定解なんなの

>>394-396
大枠はこれでいいでしょ
できるだけ偏らせたほうがいいから、LともHとも違う分割の仕方は高々1つ
分割する個数も減らしたほうがいい(Lをばらしてほかのに割り振る)
だからLからHに分割する方法の中で、Hをたくさん作れる分割の仕方を求めるというのがやりたいことのほとんどなんだけど、
Lがたくさん存在する場合もあるから貪欲でやるのは難しい気がする?それとも>>396の二つ目の例みたいなものは数学的に簡単に求められる?

これ確かO(1)解法あるよ詳細はもちろん知らんが

最小分割の個数が、L*x <= N <= H*xを満たす最小のxでそれがわかれば分割の仕方も
出せるから定数で計算できるね

実用上はにぶたんO(logn)で十分
場合分け頑張れば定数でいけるだろうけど

二分探索って分割回数を二分探索か？
分割回数に対して単調ってなんで分かるっけ？

Hの個数

Ｈの回数（O（0））

N/Hの商をq,余りをrとする
r=0かL<=r<Hの場合は自明
そうでない場合、(L-r)/(H-L)の商をs,余りをtとする
t=0の場合、H×(q+1-s)+L×s
それ以外の場合、H×(q-s)+(L+(H-L)×t)+L×s
こうかな

今週は企業コンがABC代わりなのか

企業的にはABCのほうが嬉しいのかね、企業が選べるんだっけ

参加者はABCの方が多くなるよね
2000以上の人をどのくらい重視するかによるんちゃうかな

結果はどうでもよくて宣伝できればいいって感じなのかな
ってか今日か

ABCでも暖色の人結構出るし宣伝的にはABCのほうが良さそうか

kaggleのコンペ最近画像分類ばっかりやん

ABCの過去問解いてるんだけど、同じ色でも昔の方が簡単な気がするのだが、正しい？
受験者のレベルが高くなってることを反映してるのかなと思ったのだが

正しい

最近見かける受験者って表現気になる
正しい正しくないの話じゃなく各人の認識のしかたとして興味深い

デュエリスト

挑戦者

コンテスタントで良くないか

参加者でいいじゃん

パーティシパンツ

何よりABCはバズるしな
「エイシング」って単語がトレンド入りする可能性すらある

くる！

Eが黄diff？もしかして

3完爆死

パナソニック2020もそうだけど、企業コンABCのFに不可能を置くな

難しくてワロウタ！！これもう半分ARCだろ

コンテスト中にdifficulty予測出来るツールってありますか？

あります

教えてください

ありません

https://greasyfork.org/ja/scripts/398439-atcoderstandingsanalysis
これだと思うけどどんな計算してるのかわからない

>>435は俺だけどpredictor見て言っただけだからわからん

Dがムズいんじゃー

Dコンテスト終了直後に投げたのが通ったわ、3分伸ばしてくれ

CDが茶色か
もっと難易度差あるかと思ってた

abc見てない？

もう出てる？

にほんごでおけ

明日もABCかな

先週の解説で日曜はないと思うってすぬけさんが言ってたような

CDのdiff茶色って言ってるけどabc173のdiffと勘違いしてない？
エイシングのdiffもう出てる？

英語版の解説pdfまだ出来てないの、外国の人かわいそうに…

灰灰灰水黄赤

>>452
勘違いしてたわすまん

>>454
それ＜Obvious.＞じゃなくてあなたの感想ですよね？

Cはギリギリ茶色な感じがする

参加者7000人ちょっとか
なんで今日こんなに少ないの？普段のABC1万超えなのに

企業コンだからABCって分からなかった人が相当数いるんちゃうかな

土曜日の夜はみんなセックスしてるんだよ…

>>459
これだよな
ABC○○○ by (企業)にした方がわかりやすいよな

賞金もないと普段のABCと変わらんからありがたみないな。宣伝効果的にどうなんだろ

最近の企業コンはARCだったから、最近始めた人が勘違いしてもおかしくない

ところで今回なぜ参加情報の登録項目があったんだ?

コンテストの後って興奮しちゃってるのかなんなのか寝つけないわ
わかるやついる？

そのせいでコドフォ出ると生活リズムが終わる。

競プロ生活の始まりだぞ

学生だったら良かったんだけどなあ。
社会人にはきつい

なんかコドフォ苦手なんだよな

Dのpopcount()なんですが、最大200000桁の割り算ってどう実装すればいいんでしょうか
2の200000乗だと64bit整数でも溢れますよね？

繰り返し二乗法というアルゴリズムでaのK乗 mod MをO(log K)で計算できます

普通に累乗のテーブルを作ったほうがいいんだよな

modpowでもいいし頭から割り算の筆算みたいにmod取っていけばいい

昨日のD問題はどうやって方針立てれば良かったんだ？
普通に問題文のまま実装しようとしてTLEになっちゃったんだが、その前に計算量オーバーしてるって気がつかなきゃいけなかったのか？

2*10^5桁の数値を2*10^5回除算しようとした時点で負け

さすがにDは愚直が許されないイメージ
自分の書いているコードの計算量を常に把握していれば気づくと思う
まあ中には計算量解析が難しくてそこが本質みたいな問題もあるけど

>>471
ありがとうございます
2のK乗ということは最上位bitが1（「100」とか「10000」）が対象だと思うんですが、
「10101」のような値にはどうやって適用するのでしょうか？

E天才すぎる
こういう貪欲どうやって思いつくんだよ

>>477
2進数の10101=2^4+2^2+2^0
なので、それぞれに繰り返し二乗法を用いて足し合わせればよいです
今回の制約なら、2^nを0<=n<=桁数まで計算しておいて足し合わせるのでも良いです

D改めて見てるけどかなり難しいだろこれ…
これスラスラできたら青レベルだろ

C灰diffなのもすげえな、、。一昔前なら緑はありそう。

c灰なのか。落ち込むわ…

といってもx,y,zの全探索だからな

普段のABCと違って企業コンなのが難易度予想を狂わせたところはあるかもね

このスレ来てる人でC出来なかった人いる？

ノ

自分も

n,x,yがわかったらzが求まる、ってやり方(Otoshidama)でもできる

10^8になると思うん、だけど通るんやろか

10^6だろ…

探索範囲を絞ればそこまで落ちるかもしれないが、それを全探索というか?

nが10^4でx,yが100だから10^8じゃない？

配列とかで個数カウントすればx,y,zで10^6

あーx,y,z全探索で10^6に収まるのか
N,x,yでx<=yに絞ってやって1200msで通したわ

いや、>>488を受けての発言だったのよ。
c++なら通るんだろうけど自分rubyだったんで諦めた

全探索とはいえ見た目が因数分解できそうな引っ掛けやf(1)から順に求めようとすると詰むところとか灰diffって感じはしないよね

>>495
実はN<=10^4まで全て求まれば数値を埋め込めるのでコンテスト時間に間に合えばokという解法もある

解説放送はよ

>>497
おー、なるほど

Ruby・・・getsをgets.to_sに書き換えてCrystal使え

Aは入出力、Bはif文、Cはfor文
となると全探索しかないだろ

>>479
実装できました、ありがとうございます
ちなみに、「2進数のmodが各桁のmodの和と等しい」というのは何かの定理なんでしょうか？
調べたら合同式というのが出てきたんですがよくわからず…

おいこどふぉ落ちてるが、寝て良いか？

数学がちょっと得意な人がPython覚えて何回か参加したら青や黄になれるのにプログラマの能力の何が保証できるの？

>>502
一般的に整数a,b,Mに対して、a mod M=A, b mod M=Bとしたとき、
a+b mod M = A+B mod Mが成り立ちます
これは、足し算の他に引き算、掛け算、累乗などで成り立ちます
合同式で調べるのが早いと思いますが、a=xM+A, b=yM+Bと分解でき、代入すると証明できます

数学がちょっと得意なことが保証できる

すごく得意な人がすぐ橙になったりも

逆に言うと競技プログラミングがあるから入試数学がなくなっても理系人材の能力評価に支障はなくなった
文科省が入試改革で好き勝手やってもその辺のリスクはもはやない

微分積分・ベクトル「」

ちょっとのレベルが高すぎる

ちょっと＝東大か京大の理系

東大京大でも上位1%だろ

または筑駒とか灘とかの数強だがそれらは普通の東大理系より圧倒的に上だし。

東大理系なら無精進で青はそれなりにいそうだけどな

でも実情は東大でも青は上位20%なんだよね

他に山程やること、面白いことがある中で競プロを選んだ人の割合が20%なんだろうな

多杉内

黄色なんだけど東大京大理系の平均よりは数学力高いってことでいい？

ちゃんと微積できますか

ある整数nが他の整数の4乗であることの判定ってどうする？
pow((int)pow(n, 1.0/4.0), 4) が n であるか調べる？
割と長いしキャストとかミスりそうで嫌なんだが

それでやるかなあ

ABCでギリなりましただったらダメ

ll x=pow(n,0.25)+0.5;
return x*x*x*x==n;

10^18位のオーダーなら全探索でも余裕だろうけど

余裕があれば全探索
なければにぶたん

>>522
黄だまりを否定するならratedコンテストをくれ

参加回数10回超えた後って、レーティングってどのくらい変動するものなの？
現在のレートx 獲得パフォyとすると、大体abs(x-y)/10くらいの変動幅？

>>527
AtCoder Rating Simulatorで調べてみて

数学の実力の証明がしたいなら数検1級でもとればいい

>>529
数検1級はどっちかというと計算力みたいな方向性で
数学的な論理力はあまり問われないから純粋な数学の実力の証明とは言えないと思うな

もちろん計算力は実用上とても重要だが

微積も出ないうえに超重要な線形代数さえ黄色になるのに使うのは行列累乗と吐き出しぐらいなので...（特異値分解どころか固有値の計算すら出ない）
算数力の保証にはなる

競技中学受験数学

「日本が世界各国に追いつけなくなる」　日本版シリコンバレー設立へ
http://2chb.net/r/newsplus/1594624492/
４都市圏をグローバル拠点都市として選定

・東京都・横浜市
・名古屋市・浜松市
・大阪市・京都市・神戸市
・福岡市

シリコンバレー目指すなら地方に作りゃいいのに

0 <= x1, x2, x3, x4, x5
x1 + x2 + x3 + x4 + x5 <= N
を満たすすべての (x1, x2, x3, x4, x5) について、Σ(x1 * x2 * x3 * x4 * x5) を求めてください

という問題について質問です

2つの条件を満たすものの個数が Combination(N + 5, 5) であることは理解したのですが、
そこから Σ(x1 * x2 * x3 * x4 * x5) という式を Combination(N + 5, 10) に言い換える方法がわかりません
（n < k のとき、Combination(n, k) = 0 とします）

解説放送を見てもわからなかったのでこちらで質問いたしました
回答よろしくお願いします

質問する人は問題のURLはってくれな

これは問題そのままじゃなくて途中に現れる部分だから仕方ないんでは？

https://atcoder.jp/contests/aising2020/tasks/aising2020_f
こちらの問題です
といっても問題そのままではなく少しシンプルにしたものですが…

○N個と｜5個を並べて、一番右のグループ以外から○を●に置き換える方法に対応
これは
●｜●｜●｜●｜●｜
に○をN-5個挿入する方法と同じ

>>540
回答ありがとうございます
その部分については理解しているのですが、なぜその組み合わせ数が Σ(x1 * x2 * x3 * x4 * x5) になるかが理解できないです…

>>541
x1個の○、…、x5個の○から一つずつ●に置き換える方法がx1*...*x5通りということではなく？（馬鹿にしてるわけではないです）

542の言い換えは、普通は知らないと浮かばないレベルの発想だと思います。高度競プロ人材はこういうの得意ですよね。

542単独の話ではなくこの問題の中でということで

そこは解説pdfにちゃんと書いてあるから（分割を行った後、〜対応しています？）大丈夫かと思っちゃった

理解できた気がします
解説放送の方針を勘違いしていました

「x1 * x2 * x3 * x4 * x5 = A を満たす A はいくつあるか」を数え上げるわけではなく、
たとえば (x1, x2, x3, x4, x5) = (1, 3, 1, 1, 2) のとき、
(1, 3, 1, 1, 2) が 6 回数え上げられるので自ずと A に一致する、ということだったのですね

難しいです
自力で思いつくのは大変そうです…
回答ありがとうございました

>>505
合同式について今日色々調べていたのですが、使えないケースとかありますか？
例えば13mod10は2^3+2^1+2^0に変換できますが、各項を繰り返し二乗法で計算すると
8+2+1＝13となってしまい、期待した答え（余り3）が得られないです

アホか？

>>547
最後にmod取るの忘れてるね

>>549
すみません多分私がちゃんと理解できてないのですが…
適当な値が思いつかず13を例にしましたが、64bitに入らないような大きい数の場合は
繰り返し二乗法だけでは最後までは計算できないという事なのでしょうか？
（元々大きい数に対してmodを取りたくて、繰り返し二乗法で計算する(>>471)とコメントを頂いたので）

なんか玉石混交過ぎるねここに投げられる質問
>>391とかは結局まだ証明ないし、>>536とかはやるだけ・読むだけっていう

非常に分かり辛い質問になってしまいました…

繰り返し二乗法で計算したXmod10の結果Yが10以上の場合、最終的な余りをどう求めるべきでしょうか？
Y=13なら13%10で3が求まりますが、Yが64bitに入らない数値だとどうすればよいのでしょうか

1回の演算ごとにmod取ればいい

繰り返し二乗法で計算した値がmodより大きくなるってどういうこと

>>552
加算や乗算をするたびにmodを取るようにすれば、
modが10^9+7とかであれば64ビットを超えることはないです

動的計画法と線形計画法はどのような共通点がありますか？

後ろ3文字が一緒なことくらい

536がやるだけって緩めに見て上位200.人ぐらい？

>>553>>555
有難うございます（何度もレスしてすみません）
ここで言う「modを取る」とは繰り返し二乗法を使わないで、という事でしょうか？
>>547で挙げた13mod10の場合、2^3+2^1+2^0のどの項も10未満なのでmod取って和が13になってしまいます

>>559
modを取った和の13のmodをさらに取ればいい

>>560
「13のmodを更に取る」というのは13mod10を計算する、で合っていますか？そうするとまた13になってしまいます(>>547の通り)
（何か私が根本的に勘違いしているのかもしれません）

または、modの計算を1回目は繰り返し二乗法で、1回で答えが出なければ普通に計算（A%B）する、
というルールでやるという意味でしょうか。

1010100....01_(2) みたいな数のmodはすぐに計算できないけど、各桁を繰り返し2乗法でmod取りながら求めた値はmod以下だよね
それを足していく時もmodの2倍より大きくならないから、毎回あまりを取りながら足したらいいよ

13 mod 10 は 3 だよ

例えば、27=11011_(2) mod 10 を求めたかったら、
2^0=1 mod 10
2^1=2*2^0=2 mod 10
2^2=(2^1)^2=2*2=4 mod 10
2^3=2*2^2=8 mod 10
2^4=(2^2)^2=4*4=16=6 mod 10
を利用して、
27=2^4+2^3+2^1+2^0
=6+8+2+1
=14+2+1
=4+2+1
=6+1
=7 mod 10
と求められる

皆親切すぎだろ

大きな数のあまりを取るのは難しいけど、小さい数のあまりは％演算子とかで取れるから、それを忘れてるんじゃないかな

てか13って2^3+2^2+2^0じゃん
今気づいた

>>551
>>396じゃお気に召さないかね、証明ではないからか？
二乗和の最大化なので、できるだけ最大の数字を増やした方が良い(a+b=c+d,a>b,c>dのときa>cであればaとbに分けた方が良い)
a^2+b^2-c^2-d^2=(a+c)(a-c)-(d+b)(d-b)
a-c=d-bより(a+c-d-b)(a-c)>0、よって示された

え、540、542の言い換え天才すぎない？この言い換え典型なの？
典型じゃないとしたら自分には無理だから、形式的冪級数履修するか…

>>562>>564
ご丁寧に有難うございます！理解できた気がしました
示して頂いたこの部分（=14+2+1=4+2+1）が「余りを取りながら足す」という事だったんですね

コメントして頂いた方々有難うございました（かなりスレ汚してしまいすみません）

>>566
小さい数が％で計算できるのは分かっているのですが、
その「大きな数」と「小さな数」の判断（どこからが「大きな数」か）をどうすればいいかで悩んでいました
（ここはまだ理解できてないので今後自分で調べようと思います）

AtCoder上でパッと自分が思い出せるだけで2問はあるからど典型じゃないかなあ

典型ならこの手法も覚えておくか、ありがと

はー天才すぎる無理やろこんなんからの意外とすぐまた出会うってのあるあるだからな

すぬけさんすき
他のatcoderのひとだいたいすきじゃない

りんごさんとwataさんの外から見て嫌いになる要素何？

分数の演算を行う構造体を作ろうと思うのですが、使うことはあるでしょうか？

普通にあります

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1131&;lang=ja

赤になるまでは〜のツイートは思うところある人いそう
rngさんはmaroonさんにadmin完全に引き継いでもらったあとcontestantで無双してほしいな

分数を表す構造体、足し合わせる分数が多いと通分したときにすぐに分母がオーバーフローしそうで怖い

多倍長整数使えよ

今の時代に多倍長に対応した分数の構造体を使う問題が出るとは思えない
そんな問題を作る橙以上の人がいるとは思えないし、
もし作ったとしても絶対悪問と言われる
やっぱり分数の構造体（特に多倍長に対応したもの）を作る必要性が見い出せない…

ちょくだいは最近就活就活言い過ぎで不快なんだよな、それがないとお金入ってこないのはわかるけど
まわり見てても就活の結果とレートそこまで相関ないし

boost/multiprecisionの基本的な使い方押さえときゃよくね

分数の構造体の件、作っても使わなそうですし、
作る過程で得られるものが特になさそうなので作らないことにします
レスしてくださった皆様ありがとうございました
boost/setprecisionの基本的な使い方についてはまた勉強しておきます

あれくらいで不快とか、生きにくそう

>>579
現役に未練はないと言ってたし今年のGCJも出てないみたいだから引退気味なんじゃないかなあ…

>>587
まあそうなんだよね
残念

まだ若いのになんで引退気味なん？
衰えとか感じてんなのかな

https://codeforces.com/blog/entry/62540
りんごさんではないが引退した人のブログ
衰えはあるみたい、当時30半ばだろうか

2色上の奴が無い内定でゲラゲラしてる

参加者も増えた分そろそろ就活に役立たないって事が露見してきた感

就活には初めから役に立たなかっただろ
学生と社会人が、つまりおれたちが力を合わせて盛り上げるんだよ

>>582
ちょうどAtCoderでも宣伝されてる、ICFPコンの2016年の問題は
多倍長有理数が必要な問題だったけど良問と言われてるはず
まあAtCoderで出題される可能性は低いとは思うけどね

>>579
赤になるまではって何？

>>595
https://twitter.com/rng_58/status/918485141718052865?s=21
https://twitter.com/5chan_nel (5ch newer account)

これ突然こんなこと呟かない気がするけどどういう文脈だったんだろう

作問者に対する大量のイチャモンを受けて言ってるんじゃね

りんごさんとすぬけさんの解説動画はいつ見てもカッコいいな

https://togetter.com/li/1160322
2017-10-12 の付近の呟きみてみたらSRMがクソ回だったらしい

りんごさん→かっこいい
すぬけさん→かわいい

競プロばっかりやってないで研究しろって怒られちまったぜ