競技プログラミング総合スレ 63 YouTube動画>3本 ->画像>2枚

!extend:checked:vvvvv:1000:512
↑2行になるようにする

競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder https://atcoder.jp/
yukicoder https://yukicoder.me/
Codeforces https://codeforces.com/
CodeChef https://codechef.com/
Project Euler https://projecteuler.net/
CLIST https://clist.by/
AtCoder Problems https://kenkoooo.com/atcoder/
AtCoder Clans https://kato-hiro.github.io/AtCoderClans/

※前スレ
競技プログラミングにハマるプログラマのスレ 62
http://2chb.net/r/prog/1626625368/

---

VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

>>1
乙

移転記念パピコ

もほほほｗ

SNSヲチ勢はNG推奨
健全な競プロスレにしましょう

うっかり特定されるやつが出てこないか楽しみ～

15分後にcodechefあるから出ましょう

今週末から8問ABCか

インドコンって特有の問題傾向ってあるの？
AtCoderは算数パズル多め的な感じの

苦痛なlog落としの問題とか謎い式を変形していく問題とか？
俺は知らないけどFPSを使う系の問題もあるらしい

結構勉強にはなりそうだね、atcoderにはなさそうな感じ
それだけ聞くと好きかもしれない

アカギスレ開始

インド人ってチーター多い印象

見てみたらインドコンのがコドフォより英文読みやすかった
英文はこっち標準がいい

このスレは終了しました

競技プログラミングにハマるプログラマのスレ 63
http://2chb.net/r/prog/1627503463/

競プロと関係ない馬鹿な話題が蔓延ってたから移行うれしい

こっち20まで保守とかいるんやろか

たったレス10個で落ちてなかったスレがあるから大丈夫そうな気がするけど

前スレで質問あるって言ってた人、こっちで聞いてみたら
俺も可能な範囲で答えるよ

のいみ鍵垢なってるじゃん
非公開リストで見てたのに

8問ABC が始まったら AtCoder Problems の横枠？がまた狭くなるのかな
AGC-like とかもう問題名が何も見えんのだけども

自分スマホで見てるから関係ないな

どう棲み分けされてんのこれ

向こうは競プロerヲチスレ、こっちは競プロスレ

25分後くらいにこどふぉ div. 2 です
夜更かしする人は出ましょう

米ニューヨーク市
7月30日以降のワクチン接種者全員に
100ドルを配布するキャンペーン開始

nosub余裕でした

質問いいですか
Ford-Fulkersonの計算量O(FE)の最大流量Fって何のことですか？具体的にどう見積もればいいのでしょうか

こどふぉのレートなんて溶かしても余裕じゃない？
橙から落ちるとかならありかもしれんが今日はDiv.2 only だし

>>28
最大流量F ってのはそのままの意味で、 始点から終点へ流せる量の最大値
見積もりは難しいと思う。自明なカットで上界与えるくらいしかできないんじゃないかな
(辺容量の最大値) * (辺数) とか

>>30
ありがとうございます！スッキリしました
AOJのVerify用問題も(辺容量の最大値)*(辺数)が10^7に収まるようになってるので取りあえずその見積もりで問題なさそうですね
（1/4とかの定数倍はつけてもよさそうですが）

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&;lang=jp

最大流が青までの問題に出ない教プロに何の価値があるんだろうか

蟻本だと中級だからそんなに発展的な内容という位置づけではないわな

最大流とかグラフ系を増やしてしまうと進学校の数学の先生が激おこですからね

IOIシラバスで明確に除外されてるものは黄色以降でいいだろ

こんなのがあるのか、有効グラフの連結分解が明確に除外ってw
https://www.ioi-jp.org/ioi/ioi-syllabus_jp.pdf

中高生の「事情」に一般人が配慮する一般向けコンテスト

>>35
これはどう考え方？
ARCで前提にするつもりのテクニックはABCで出しておかないと
ARCがそのテクニックを学ぶための教育的コンテンツになってしまうし、ARCの位置づけはそうではないと思うんだが
一切出さないかABCでも出すかの二択しかないと思っていた

それはそうと実はCodeChef LunchtimeはIOIのシラバスに沿うというルールなんだよな
言うほど守られていないが

>>37
ABCの600点(解けたらABC卒業;黄diff～)
に少し難しいアルゴリズムを出すことは否定しない

>>38
なるほどだけど、少し難しいアルゴリズムが結果的に青dif以下になるなら点数にはこだわらなくていい気がするなあ
本当にフロー流すだけ、とかはIOIで除外されてるけど青ボーダーくらいになりそうだし500点ででても違和感がない
(そんなん出すなよ、というのは一理はある)

ZebranessとかGrid and Tokensは黄diffだったねえ

アルゴリズムってなんでこんな仰々しい名前多いんだろ
連鎖行列積問題とか行列積コスト最小化問題って書いてたら、何となくやってること分かりそうなのにわざわざ難しく書く

matrix chain multiplicationの直訳だからじゃない
日本語だと仰々しいが英語だと簡潔
どっちも最適化する対象が名前からわからんけど

そもそもそれDPでとける問題の名前であってアルゴリズムの名前じゃなくない？

行列積コスト最小化問題だと行列が3つ以上あるように見えないな
英語のchain要素は欲しい

行列鎖積が限界じゃない
方鎖積とか言い出すと意味が取れなくなって危険

こっちのスレ快適すぎだろ

もうあっち見てもいない。いい感じで隔離できたね

あっちはゴリラ
こっちは人間

8問楽しみだ
1問1問にどこまで固執して良いのかな見極めが重要そう

500点問題が俺でも解ける難易度になってて欲しい

緑～水difの問題生やすの難しそうだよな…Writerは頑張って欲しい

詰まらず、より早く解くのが求められそう

D以降全部青以上とかいう地獄ありそう

どうせすぐに灰灰灰灰黄黄黄黄になるでしょ

そういえば4問ABCから6問ABCに変わった初回はunratedになったのを思い出した
今回も参加者増えてジャッジ詰まらないか心配

今回参加者増える要因ある？

171 仕様書無しさん sage 2021/07/30(金) 19:51:47.26
IDありの方でいい感じに自演してるけど楽しい
こっち見てない人多そうだししばらくバレなそう

ここまで自演

今日は yukicoder と Educational なこどふぉです

まあIDなしスレの方でこのスレについて適当に煽るやつが出てくるのも自然ななりゆきだな

20年前の2ちゃんねらーみたいなやつやな

ABCとインド被ってて困る

ABC unrated なら インド優先でいいんでないか
トーナメントは知らん

直近コドフォAの考え方教えてください
自分は小中大のスライスの数が3:4:5なので、その辺りから必要な枚数をO(1)で導こうとしたのですがうまくいきませんでした
答えが小中大の枚数に関わらず(n+1)/2*5だなとわかった人はどんな発想でそうなったのか知りたいです
よろしくお願いします
ちなみに関係ないかも知れませんが女子中学生です

>>64
小中大も単位枚数当たりにかかる時間が同じ

拡張ユークリッド互除法の観点から、ある程度大きな数の偶数は、6 と 8 のペアの組み合わせで作れるみたいなのがある (実際には 6 以上の整数すべてが 3 つのペアから作れる)

8問ABCか
黄パフォラインは1-2-3-4-5-6の組み合わせで6完とかかな？

確かに重い5を飛ばすかの駆け引きがありそうだね

4問から6問への移行のときも参加者増えてたし今日は少なくとも9000人は参加しそう
多けりゃ1万

4問から6問のときはrated対象変化のほうが大きそう
今回はそこまで変わらないと予想

問題数の多さに嫌気さして減るまであるかもね。実質何にも変わらないとしても

6解いて55に逆転の目があるの面白そう

解説放送、スタイル変えないなら深夜3時コースじゃん

snukeさんだけ貧乏くじか

問題多い方が満足感あるな

Fが実装難でGが数論の中レベル典型という感じで難度逆転か
数学問はAtCoderだとみんな解くからね

Fが実装辛すぎて震撼してたが、終わってみるとこれに数十分掛けてるようでは。。という気持ちになるんだよな
実装難問題はだいたいそうなんだけど

今日のC問題、
Bだけソートして、
二分探索でB[l]<=A[i]<B[r](l+1==r)となるl,rを探して
min(今までの最小,min(abs(A[i] - B[l]),abs(A[i] - B[r]))))
で最小値だそうとしたんだけど、WAが2つ。
ソートする前に10の9乗よりちょっと大きい数字とその負の数をBに付けた。TLEはない。

なんで？
…とここまで書いてちょっと大きい数を
10**9+20から3*(10**9)に替えたら全部通った。
ドンマイ、俺

つまらない実装ミスでF問題落として魂抜けた
ちゃんと大きめのサンプル作って試していればよかったのに

Aの提出者数8554 -> 7822か
700人くらい減ったな

ratedの人でGH解けてる人どれくらいいるのかな

G は知識があればなんとかなる
H は畳み込みをブラックボックスとして使ってた人は厳しいかも

rated だけど E までは簡単で考察も実装も F より G の方が軽かったし、G は無限人解けてそう
H は知らん

難易度若干シグモイドっぽいの解消して欲しいな(難しいとは思うが)

Gは位数とか原始根みたいなちょっと進んだ整数論を学んでたら知ってるような概念割とそのまんまなので、考察負荷も確かにそんな高くない
Fも考察の本体は「あるバスに乗ったあとに乗るバスがあるとすれば一意に定まる」に気づいて超頂点を作るだけな気がするけど、ダブリング二分探索みたいなおまけ部分が重い
AtCoderで重実装問の後ろに軽い数学問出したらそらそっちに流れるわなという

>>83
C茶、D緑、E水、F青を目指してたんだろうなと思ってる
CDEはその点ちょっとブレただけで割と悪くないのでは？
Fは運営がユーザーの実装力を過大評価してたといういつものやつ

>>85
いまグラフ作ってたんだけどまさにその通りだったわ



Fがもう少し低ければめちゃくちゃいい勾配のセットだったんだな、惜しい

>>86
やっぱFだけおかしいね
どうすりゃよかったんだろう
最初から逆有向森？みたいなのを明示的に与えてあげるか、バスに乗ってる時間を無視してよいとするか

Fは100分6問のFならもっと解かれたはず
解けそうなやつがGにいっただけ

fとgの逆転は120分にすれば解消されそうだけど

同程度の難易度の問題が500と600にあったらコスパ良い600の方が解かれるのは当然
600の方がちょっと難しかったとしても、つまり難易度は逆転していないとしても、diffが逆転することは全然ありうるよな
そういう意味でdiffを重視しすぎるのはどうかと思う

今回のE問題までのほぼ直線的に解いていくしかないような問題配置以外では、diffは問題難度を評価する指標として微妙だとは思う

確かにこの難易度帯が解ける人にとっては実装が重そうなこの問題よりも発想さえ出来れば解ける得点が高い方に流れるか

そうなると問題数増えて時間同じままだから、実装重い問題は忌避されていくんだろうなあ

問題単体の難易度をより正確に評価できるようなdiffに代わる指標ってありうるかな？
diffの定義式にちょっと変更を加えるとかでも

昨日のE解けなかったのめちゃくちゃ悔しいわ
だいぶ冷えた

昨日のE解けなかったのめちゃくちゃ悔しいわ
だいぶ冷えた

大事なことなので2回言いました

Eは俺はTDPC-Rグラフの変形だと思って解いたね
全頂点対だとO(N^3 logK)だけど一頂点対についての問題だから大分計算量節約できそう的な

tdpc-rってsccしてdag作ってトポロジカルソートするやつじゃなかったっけ？
共通点が見えんけど

Heuristicの方ってABC全完できるくらいの地力ないと難しいかな？
楽しそうだけど実装の方針がよく分からないです

多分 EDPC R と間違えてる
自分には補グラフの形式で与えられてることが本質だと思った

>>98
マジだ
すまん、EDPC-Rのwalkの方だな
どっちもRで大体この辺にあったグラフの問題だよなあって感じで覚えてて、問題開いてよく確認してないから間違えた

遷移の節約がメインって考えると確かに補グラフが本質か
むしろ行列累乗の発想を使えないからwalkの本質的な部分とは遠いかもしれない
そもそも俺はDPを一から生やすのが苦手な方だから、DPのテンプレとして既知問題が役に立ったという感じかな

>>99
俺もheuristic全然できないけどそんなことはなさそう
基本的なアルゴリズムの組み合わせで解を探索してあげるのが主だからそんなに高度な知識はいらないって聞いたことがある

ナップサックだと嘘になるような貪欲でもheuristicだと十分な解法になり得る
ちゃんとした貪欲が書けるだけどもかなり強いよ

コドフォやります

>>99
Heuristicsは貪欲書けてBFSとDFSができれば何もできないってことはまずないと思う
あとは勇気を持って噓貪欲書いて、結果をビジュアライザで見ながら改善していけばいい

クエリのやつABCで復習したのですんなり解けてうれしい

おめでとう

制約がn=2*10^5とかで想定解がO(n)なのって出題者の優しさでしょうか
それとも定数倍とかの関係？
O(nlogn)解で通った人←

N と NlogN の区別はなかなか厳しいことが知られております
N 個の入力を与える問題なら問題を解くより入出力を捌く時間の方がネックになるなんてこともある

入出力数がO(n)ならn=10^7とかにするとそこがボトルネックになって非本質ゲーになりがち
あと遅い言語でO(n log n)落としてO(n)通すように設計するとC++ではO(n log n)が普通に通るなんてことがある
logを落とす力を評価するコンテストサイトもあるっぽいけど、AtCoderは入出力ゲーとか言語格差とかそんなに好きじゃないのであまりそういう力は問わない

一応ABC189-Cがlogの有無を意図してるっぽい

POJで鍛えなさい

logは2つつくとめちゃくちゃ速度落ちるよね

セグ木上の二分探索とかlog二つをlog一つに落とせて嬉しいパターンが結構ある気がする

https://atcoder.jp/contests/abc208/tasks/abc208_f
これは割と変なlogつけると通らないんじゃないかな

logって2つあるほうが早いんじゃないんです？

log x × log xのことじゃね
log log xではなく

最近競プロで必要そうな知識を整理してて、集めるとそれなりの分量になるなと思った反面、AGCの難問には基本的な知識しか問わないけど難しいものが結構あるよね
多分知識入れただけじゃ解けるようにならなそう
どうやって練習してる？

天才以外お断りパズルコンテストだぞ

高1でatcoder赤になった奴、東進全統高で上級生抑えて一位だな。
プログラミングと受験勉強の配分はどうなってるんだ?

全方向に才能が溢れていた結果としてAtCoder赤になったのであれば、受験勉強も軽くクリアできてもそんなに不思議じゃない

AGCもなんだかんだで練習量でそこそこ溶けるまでは解ける
個別の練習はやってないや

✕　溶けるまでは解ける
◯　解ける

>>119
https://www.oreilly.co.jp/books/9784873114057/
読んだことある？

>>123
結局演習量という話はよく聞くね

>>125
ありがとう、読んだことないや
目次を見たけどかなり競プロと相性がよさそうだね

なんかのめり込んでる時期はAGC全然勝てなかったけど一旦離れてたらいい感じに力抜けて苦手意識なくなったな

あるある
めちゃくちゃやってた時期よりもレート伸びてるわ今

ここしばらくコンテストしか出てないけどレートなんやかんや上がってるわ

エレガントな問題解決ポチった
数オリの問題も結構含まれてるっぽくて楽しみ

>>130
英語版の公式サイトに解説マニュアルあるよ。載ってるのは選ばれた問題だけだけど

PaizaってAからやたら計算量ギリギリな問題が多くなる気がする...
TLEで一発終了なのがキツい

>>131
ありがとう
届いたから読んでるけどまさに算数パズルという感じの問題が集まってて面白い
普通に演習問題の中に難しいのも結構あるから世話になるかも

132だけどやっとA取れました...
茶色になった記念でpaizaに挑戦したけど意外と苦戦した

Aの美術館のセキュリティって問題でasin,acosが出てきて三角関数の逆関数の使い方を色々学べて楽しかった(これだけじゃネタバレにならんと思う)
asinは終域が-π/2～π/2で全単射
acosは終域が0～πで全単射だからモジュールの仕様で出てくるradianに気をつけないといけないんよね

paizaの問題は話さん方がいいよ

ぶっちゃけアウト臭い書き込み

解答の本質とは関係ないぐらいの書き込みなんだろうから直ちにアウトってレベルじゃないと信じるけど、事前に要求知識が分かるだけでも微妙なのでやめといた方がいいと思う
あれ提出までの時間も評価対象だし

一切言及しないほうが無難

誰も聞いてないのにスレチのpaizaのネタバレを始める茶色

rated砂漠の時ってみんな過去問解いたりしてんの？

山ほど溜まってるコンテスト中にACできなかった問題を処理してる
rated 砂漠時に限らないけど

leetcodeのLISをO(nlogn)で解くってググれば出てくるんで典型なんですかね？
もしコーディング面接だったら解ける気がしないですね

典型だけど覚えてなきゃまあ無理だね

diffよりも正確な問題難易度の指標ってないだろうか
chokudaiはdiff信仰をやめろって言ってるけど現状問題点数が全くあてにならないから結局diff見るしかないんだけど

正確な難易度指標がほしいモチベがなくない？

>>145
勉強として考えるなら適正問題探す意味は薄いけどさ
今の実力でぎりぎり解けたり解けなかったりする問題がすぐにわかったらゲームとしては遊びやすくて嬉しくない？

>>146
その使い方なら diff 程度の信頼度でも十分だと思うけどどう？

>>147
た、たしかに…

一元的な指標を作るのは難しいね
ただ点数、diff、平均AC時間、ABC or ARC or AGC、コンテスト中の問題の位置あたりを使えば何かしら予測できそうではある
あと難易度評価と言えばAOJ-ICPCの投票システムとかも悪くなさそう

Tree Gameとか問題だけ見たら黄diffがいいところなのにAGC-Fに置いてあるってだけで赤diffなんだよな
diff、点数、出題時期、傾向、コンテスト時間、点数、問題位置あたりをパラメータにしてなんかすごいパワーで問題単体の指標が出来たら嬉しそう

2文目、149とほとんど同じこと言ってたわ

>>150
そんなことあるのか…今回のABCも8問になったから多すぎて終わらんくてHが赤difとかになってしまったのだろうか

分割統治FFTはtwitterの人々の反応をみても知識レベル的に橙～赤はあるようには見えるし、今回はそんなに極端に上がったわけではなさそう
ただ、今回のFレベルの問題が仮にHの位置にあったら橙diff上位になるみたいなことは普通にありえそう

こどふぉでます

どうぞ

8問制になったことで今まで以上にdiffの信憑性がイマイチになりそうなんだよな
EFGHのうち典型3問、実装1問だとしたら
実装問が難易度的には一番易しくても橙diffとかになりかねないし
diffにとらわれず全部覚えろという意見ももっともだが、なるべく効率的にやっていきたいので
やっぱりよりよい指標ができたら嬉しい

せめて120分にしたらもう少しdiff下がるよね

ビット演算系やめてください><

EをFGHと同じ括りにしてるのよくわからないけど
毎週高々三つなら全部やればいいじゃんとしか

新しい知識週3つ身につけるのって結構しんどくないか

Fは500点問題としては難しかった。6問の時のFのままの難易度では。

くまくまここ見て誕生年変えただろ、案外見てるもんなんだな

そういうのはあっちでどうぞ

ABCで明らかにRatedが解けない様な問題たくさん出してるのってどういう意図なのかな

高難度典型枠は高レベル向け典型90としてみるとありがたいけど、だったらストレートに高レベル向け典型90という形で出してもよかったんじゃないかなあとも思う
界隈の知識レベルを向上させる？みたいなコンセプトそんなに悪いとは思わないからさ

ratedが解けない問題出す云々は他のコンテストでもそうじゃないか？
ARCの後ろとかもそんなもんだと思う

ARCもAGCもratedで全完が出るかどうか、くらいの回が多いしABCもそうなっていくのかね
一般論としてはratedが全完同士のスピード勝負になるよりは上から下まで点数の勝負になるほうが健全と思うけど、
ABCは上位のかなりの人数が2400になるから全完多めでも問題ないはずなんだよな

平成ABCでのまぐれ全完が最初で最後の全完になった

ABC全完しても2400パフォ出ない簡単回が続いてた頃より今の方が好みだな

そのうち5完で2400出る回が出そう

まあ色々文句も出てるけど、e問題までは確実に以前の難易度に戻ったから良かったと思う

それはほんとに思う　Eまで大分解きやすくなったよね　ありがたい

EはABC198以前の難易度になった感じかな
まだサンプル2だしE青パフォとかになることもありそう

社長曰く
Easy/Easy/灰-茶/茶-緑/水-青/青/黄-橙/黄-橙

辺りを狙っていくとのことだったので、E青は全然ありうると思う
現時点ではFが思ったより難しいのがアナウンスと異なる点

easyは1個ではダメなのかな

それな
試してもないのに解ける問題数が～みたいな社長の妄想によりそうなってる
初心者にオススメのコンテストは英語に抵抗なければCF Div. 3だわ

こどふぉは Div.3 だろうが A の時点で for かけないとキツい

>>167
なるほど、たしかにRatedで全完する人がいっぱいいると、スピード勝負になっちゃうもんな
全完をちゃんと狙うのはABC卒業してからだな

卒業どころか今のabcでの全完は橙が最低ライン感

for文書けない人に配慮する前に気にすべきことがあるんじゃないかとは思う

配慮できるところはしたらいいよ

こないだのA問題は実質的にfor書けない人配慮してないと思う

こないだのaは自信なかったんで全探で解いたわ

ACLにあるけどあえて自作したライブラリあったら教えてください
その理由も

理解のために全部自作した

Pythonなので自作せざるを得なかった

Pythonも非公式であるよ

前から持ってたやつが結構あって、自分で作ったやつの方が慣れてるからそっち使うことはよくある
ACLのが基本よくできてるが

ACLできた時点で大体持ってたな
floor sumとかconvolutionあたりは持ってなかったからACL使ってる

最小費用流
理

由は負辺対応してない、双対変数の復元がない、計算量が悪い

自分が知る範囲だとSSPで十分な問題ばかりだ

そういやACLが登場したけどまだABCでネットワークフローの問題でてない？

205F

>>194
あざっす

ちょうど最小費用流出て草

D重い方から考えてたけど軽い方からなのかー

くくく、このスレで予習できたかいがあったぜ・・・

うわー

全然GH見てる余裕なかったな
Gは時間が十分あったら赤diffというほどは難しそうに見えない、ARC中盤で出したら黄diff上位～橙diff下位ぐらい？

包除原理知ってるなら時間あれば解けるはず
多分橙もいかないと思う

って思ったんだけど ARC121E で橙あるのか、じゃあ橙行きそうだ

時間足りなくてコンテスト中に見れなかったけど、GよりHのほうが簡単に感じた

問題見たけどまさに負辺対応mincostflowを実装できますか？という感じだ

>>193
そういうCSっぽいのを出すと受験を控えた電通のご子息の負担になってしまうんよ

>>205
新ABCで3回は出てるし、皮肉が成立してなくないか

Eは典型とかFは典型とかいう意見を見たけどほんとに典型なん？あれをはい典型だねと思って解けるようになる未来が見えないんだけど

Fはけんちゃんのそのまんまの記事があるから流石にね

プログラミング初心者にアルゴ式勧めてる人ちょくちょく見るけど
AOJ の ITP とかのほうが良くないか？

Eは確かにありがちな貪欲っぽく見えるけど、典型だとしたらどんな名前がついてるのか気になるな

区間スケジューリング問題の類題じゃないの

>>211
お前すげえな。なるほど。

コドフォでます

Twitterと勘違いしてんちゃうぞ

チー牛なう

先週のDってKruscalとPrimのアルゴリズムを実装したことある人なら簡単だったのかな
緑だと厳しくて水の人らはそこそこ解けてるからこの辺り知識差がでたのか

マトロイドってやっといた方が良いの？

マトロイドは勉強したけど青黄往復レベルの自分だと直接的にそこまで役に立ったことはまだないかな
クラスカル法の一般化として理論は面白い、電気通信大の資料で勉強した
問題に出てくる対象がマトロイドになってるとわかると直感的に明らかでない場合も貪欲でできるとわかって嬉しい
けどそもそもマトロイドであることを初見で見抜いて示すのがそこまで簡単じゃない
自分の認識はこんなもんだけど橙以上の上位陣がよく話してるマトロイド交差みたいな上位典型もあって、自分が把握してない活用法がまだまだありそう

あとこの前のABC-Dではあまり最小全域木アルゴは意識したつもりはなかったけど、辺を段々追加して動的に管理するみたいな発想は確かにそのあたりのアルゴの影響で思い付けた可能性はあるかも
どちらかというと主客転倒がメインで、辺が寄与できる範囲の木を作ろうという気持ちだった

辺の寄与考えると小さい順にやるのがよさそうで、これクラスカル法じゃんとはなったな
俺はどっちかというとABC120-Dのお陰で思いつけたかな

>>216
ちょうど水色でなんとかそれ解けた、ってレベルだけど、
似たようなアイデアを断片的につかう問題をいくつもやってたからたまたま解けたって感じ。
やっぱ解きまくって典型解法に習熟するのが重要なんじゃない？
初等レベルの算数でも足し算、掛け算、割り算の筆算は練習しまくらないと慣れないし。

ちなみにクラスカルは楽勝に実装できるけど、プリムのやり方忘れたやべえ。マトロイドはなんのことだか知らんがな、って知識量。

それはunion-findがあるからですかね？

せやな。UnionFind覚えとけば簡単やろ

ウニオンフィンド(´・ω・｀)

こどふぉでます

div3なのにムズくないですか？

Eの後ろから見るアプローチ天才過ぎる
類題あったりします？
ゴールから考えるのに近いですかね

E は今日の div.3 の中では一番 adhoc 気味かもしれん
後ろから見るというより最後に付け足した文字列は何になるかというのを考えると自然かもしれん

ほどよい難易度だったね

ABC214-Dが茶色予想だったってchokudaiがあーだこーだーで言ってたね
・辺をコストでソートする
・Unionfindで管理する
って普通の人はクラスカル法を理解してないと着想難しいし、あれが茶色は流石にないでしょう

逆にクラスカル法理解してれば無だからなあ
どの知識が何色かなんてこの漢字は何年生で習うでしょうってくらい難しいししょうもない

最小全域木やるだけが茶色くらいなイメージあるな

dpやるだけ

クルスカル法を想起させたいなら最初から木構造にすな

あれそんなにクラスカル法結び付く問題かなあ、実装方針が外形的に同じなだけで本質的な部分は別だと自分は感じたけど

クラスカル法とはあんまり関係ない気がする

おれもそう思うわ
たまたま実装方法がクラスカルっぽくなっただけと感じる

解いてるときも、別にクラスカルのことは連想しなかったけど、解けたし。

考察全部終わってからクラスカルだなとはなったけど最初からクラスカルは違う気がする

最小全域木やるだけは水色くらいありそうな気がするが…
ufやるだけが茶～緑くらいのイメージ

一昔前ならUF使えて茶色なんてこと絶対なかったと思うんだけど、厳しすぎない？

知識問のdiffはこれからも下がっていきそう
昔より初級者はちゃんと勉強しないとレートが上がらないゲームになってるとは思う

クラスカルとは全く違う

クラスカルは最小の和が欲しいから、小さい方から貪欲に見ていくのであって、今回のは各辺の寄与をみるのに小さい方からみるとうまくいくというだけ

アルゴリズムが本質として違いすぎる

クラスカルとは違うけど枝を小さい順から見ていってunionするとか、プリムとは違うけど頂点集合のカットから最小の枝を選ぶとかの考え方を1度やっておくと
別の問題に帰着できそうね

今月ARC一回だけか。。

今日のFGHなにが出るだろうか
幾何系がそろそろ出てもおかしくないよね

CHT使うdpとか

Rustのメモリ安全性はボローチェッカーによって担保されているが、
Nimと比較してRustはタイプ量が多い事により限りなく低い生産性と
C++のような高い難読性、超巨大なバイナリ生成性能を兼ね備えています

Nimはバージョン1.5.1でRustのボローチェッカーに似た「View types」が実装されれば、
GC無しのView typesで参照の有効性を検証することによってメモリ安全性を保証しつつ
限りなく抑え込まれたタイプ量で高速化したCのソースコードを吐き出せます

Nimソースコード ==nimコンパイラ==> Cソースコード ==Cコンパイラ==> バイナリ

なので、nimコンパイラが通った時点でメモリ安全性が担保されませんか？

Nimの実験的特徴
著者： アンドレアス・ルンプ
バージョン： 1.5.1
http://nim-lang.github.io/Nim/manual_experimental.html


Nimは限りなく抑え込まれたタイプ量で高い生産性とPythonのような高い可読性を実現し
ているにもかかわらず、高速なCのソースコードを吐き出せるのでC言語でリモートワーク
されている方は割り振られた仕事が早く終わっても終わってないふりをして怠けることができる

「怠け者とはこうあるべきだ！」と言うとても大事な事を Nim は我々に教えてくれます

今回は比較的調整がうまく行ってる方なのかな？
Gは困難というほどでもないし、Fもちょうどいい塩梅

今日のC問題、26^8の並べ替えは全探索は無理と思ってたけど、8^8の並べ替え考えればいいんだな。

原理を知ってると応用がきくって基本だけど大事よな
今回のD

noshiさんの言ってるTaylor shiftやっと理解した
f(x) = \sum_{n=0}^N c_n x^nとする
二項定理から
f(x+a) = \sum_{n=0}^N c_n (x+a)^n
= \sum_{i=0}^N (\sum_{n=i}^N a^{n-i} c_n \binom{n}{i}) x^i
これは二項係数をばらしてj=N-i, k=N-nとして
\sum_{j=0}^N x^j /(N-j)! \sum_{k=0}^j (a^{j-k}/(j-k)!)((N-k)! c_{N-k})
になる

この後ろの部分をよく見ると畳み込みになってて、
g(x) = \sum_{n=0}^{N} (a^i/i!) x^i
h(x) = \sum_{n=0}^{N} (N-i)! c_(N-i) x^i
の畳み込み(g*h)(x)のi次の項に1/(N-i)!倍すればいい
これでO(NlogN)でFPSの平行移動が計算可能

さすがにleetcodeは無理

>>252
FPSではなく、多項式かと。

何言ってるのかと思ったけど一般の FPS だと定数項を含む式は合成できないってことか

Rustのメモリ安全性はボローチェッカーによって担保されているが、
Nimと比較してRustはタイプ量が多い事により限りなく低い生産性と
C++のような高い難読性、超巨大なバイナリ生成性能を兼ね備えています

Nimはバージョン1.5.1でRustのボローチェッカーに似た「View types」が実装されれば、
GC無しのView typesで参照の有効性を検証することによってメモリ安全性を保証しつつ
限りなく抑え込まれたタイプ量で高速化したCのソースコードを吐き出せます

Nimソースコード ==nimコンパイラ==> Cソースコード ==Cコンパイラ==> バイナリ

なので、nimコンパイラが通った時点でメモリ安全性が担保されませんか？

Nimの実験的特徴 バージョン1.5.1
http://nim-lang.github.io/Nim/manual_experimental.html

第二プログラミング言語として Rust はオススメしません Nim をやるのです
https://wolfbash.hateblo.jp/entry/2017/07/30/193412


Nimは限りなく抑え込まれたタイプ量で高い生産性とPythonのような高い可読性を実現し
ているにもかかわらず、高速なCのソースコードを吐き出せるのでC言語でリモートワーク
されている方は割り振られた仕事が早く終わっても終わってないふりをして怠けることができる

「怠け者とはこうあるべきだ！」と言うとても大事な事を Nim は我々に教えてくれます

>>254
>>255
ありがとう
最初Nが有限じゃなきゃ意味のない式だから確かにFPSじゃなくて多項式において適用可能か程度の認識で読んだけど、そもそも根本的に定数項を含むFPSを他のFPSに代入しちゃダメなのか
恥ずかしながら理解してなかった
確かに一般のFPSに1を代入したら容易に定数項が発散してしまうね
0に何掛けても0なので0次の項が爆発してしまう

ARC125-DのBIT使って解くパートがよくわからん教えて

dp[i]を先頭i個について最後の要素を必ず使う場合の答えとかしてそのままBITに乗せればいい

競技プログラミングは役に立たない

Competitive programming is useless
https://kislayverma.com/organizations/competitive-programming-is-useless/

ざっくり読んだけど、大意としては白カピさんが前言ってたようなことと大体似たような感じ？
優秀なITエンジニアを目指すことと競プロを突き詰めることは分けて考えた方がいいというのはまあそうだよねという感じ

青くらいまで取れたら十分でそれ以上は趣味かな

独創的な問題じゃなくて、
「このような要件を持ったRailsアプリを作りなさい」

というのが実際に求められることだからな

あと競技プログラミングで作ったものって
他の人の役に立たないよね？

あんなに優秀（笑）な人が時間をかけて作業してるのに
競技プログラミングの成果は無駄になる

ものづくりのためにあるプログラミングなのに物を作らない
ものづくりに必要ない技術の競技なってるから役に立たない

入り口の段階でコーディングに慣れたり頭の体操ができる的な効用はあると思うけどねー
まあ趣味なので一定レベル以上でそんなに実用的な期待のもとにやってる人は少ないと思う

黄 abc卒業、一つの到達点
青？
水 アルゴカンスト
緑 業務上は十分
茶 入色！

なんか青だけ中途半端だな。自分の立ち位置をうまく説明できなくて就職も失敗しそう

クイズ・頭の体操・コードゴルフ

プログラミングのお題スレとか、上田隆一のシェル芸と同じ

Codeforces の時間です

Codeforces の時間は終わりました
来週の放送時間は未定です

>>266
それ書いた頃から色１つ以上ずれてる予感
最大流が青以下で出てない以上黄色でもカンストしてないし、灰色で高度なグラフや最適化アルゴリズムを実用レベルで使うことも可能でミスリーディング

今のatcoderはアルゴリズムをダシにしたただの算数パズル

アルゴ力カンストしてます！とか言われても笑ってしまうわ

白カピを信仰しろ

こどふぉは B で詰まりまくって爆死した
整数1, 2個与えて計算してくれみたいな感じの問題が苦手っぽい

グラフアルゴリズムを使えなくても、整数問題と漸化式と関連してdpが使えれば最悪青までいけるように調整してきたのがatcoder、受験生に優しい

門外漢に説明する場合実態よりも社長のブログ記事やから

こどふぉB、所謂整数1,2個系っぽくはない気がする 普通のDPであまり数学っぽくはないというか

全然参加してないっぽいね

ad hoc coder

牛ゲーっていうんだこれ
G問題なのにad hocで妙だなって思ってたけどちゃんと高度典型に関わる問題だったんだね
牛ゲーへの帰着よりad hoc解の方が簡単で結果みんな解けているけど

Gまで比較的簡単だったことを考えるとなおさらHが際立つね

公式自体は知ってたけど固定されてるパターンしか見たことなくて応用できなかった

ああGは区間スケジューリングみたいな貪欲でいけるんだ
天才では？

牛ゲー理解したけど、これ知ってても帰着に訓練が要りそう

最短経路問題に帰着したあと、負辺に悩んだ末にグラフの特殊な形を利用して準線形にしたけど
解説見てなるほどなあとなった
初手で反転するタイプのやつ全般、いつも見落としてしまうな

システムテスト弱forces

Combined で E 通してる人と同室になる確率が低い

もしや解説でないとかあるのか？

なんの話かは知らんけど解説そのうち出すよといって何年も放置されてる問題は存在する

日本語圏を掘るだけでもかなりの知見が発掘できるように中国語圏にも知見がたくさん集まってると思うんだけど、なんかまとめてるサイトとか知ってたりする？

ジャッジでよく聞くのはluogu libre uojとか？
個人ブログはcsdnで書いてる人が多いイメージ

>>290
ありがとう
csdnはUIがどことなくredditに似てるね
多分zennとかqiita的なサービスなんだと思うけど
競プロは競争性編程(の簡体字)というみたいだ

libreは見れたけどluoguは接続できないな

https://oi-wiki.org/
ここにまとまってる知見だけでもかなりの量

すごいwikiですね

大半は日本でも広く知られていそうだがときどきマニアックなのが紛れ込んでるな

>>293
これはすごい…
Chtholly Treeとか初めて聞いたな
前のABCに出てきたLGV公式とかも当然載ってる

牛ゲーのことを差分约束と呼んでるのか

Eみたいなの新しいデータ構造を作ってみようみたいな感じで面白いと思ったな

vEB木って俺の考えた最強のデータ構造感があってかなり好き
実践では使わないけど

https://www.slideshare.net/catupper/nazoki
catupperさんがスライド出してる謎木だね

実装重すぎforces

二次元壁画問題やめてください><

Eで時間使いすぎた…

c嫌い

逆にCみたいなのがプログラミングしてる感あって好き

DPだと添字いくつあってもいいのに
幾何学が絡むと二次元でも頭が爆発するのなんでだろう

単純に幾何に慣れてないだけとちゃうの

その通りでございます

算数パズルと叩きまくれば普通のプログラミングやアルゴリズムの問題が増える

https://twitter.com/kyopro_friends/status/1436693258298482688
を見るとABC218-Gがpriority_queueでも解けるように読めるんだけど、今回みたいにバックトラックが必要な場面でもこのテクニックは使えるもの？
multisetみたいに任意の要素を削除できないと厳しい気がするんだけど
https://twitter.com/5chan_nel (5ch newer account)

誰かが削除可能priority_queueのテクニックを紹介してた

出来はするけど面倒だからmultisetで書いた方が楽だと思うよ

https://twitter.com/maspy_stars/status/1436690222465486848?s=21
これ？
https://twitter.com/5chan_nel (5ch newer account)

>>313
C++書いててちょーショック

なるほど…確かにこれなら削除できるね
言われてるようにmultisetのほうが楽だからあまり使わなそうだけど、勉強になったよ
ありがとう

なるほど
priority queueのメリットといえば定数倍の速さだけど、こっちの方が速かったりするのかな？
maspyさんはコドフォでは普通にC++を使ってるイメージ

priority queueから削除が要る時は、追加する値を2倍+1、削除する値は2倍にして
同じキューに突っ込んで、取り出した値の下位1ビットが0の数だけスキップする
最強園児の選別でそんな感じのものを使った気がする

レート付き園児が出てくるやばい問題ね
min、maxおよび定数個のk分位点の取得はpriority queueでほぼ代用可能ということかな
検索は大体どの言語にもあるunordered_setで代替できる
lower_boundとかは無理そうか
まあ、平衡二分探索木の代用だとクエリ先読みできるんなら座圧BITの方が直感的にわかりやすい気がするけど

Ruby だと想定解通りに書いても遅くて通らないの何なの?言語差別なの?俺にCrystalの道を示してるの?

Rubyが遅すぎるんじゃないのかな使ったことないから知らんけど
余り遅すぎる言語に合わせるとC++とかでクソ解法が通ってしまうからしょうがないような気もする
一応Pythonなら通せるようにする方針らしいけど

Rubyはインタプリタとしては遅いわけではないが、JITコンパイルでもあまりはやくならないのが厳しい。PyPyのように速くなるものがあるといいんだけどね。

C++の軍門に下るかCrystalを極めるかしかないのか
昨日と先々週のD問題は想定解書いても通らなかったし、悔しいけどもうRubyじゃ無理なのか

Ruby書けるならCrystalはすぐ書けるようになるよ。ほとんど同じ。

むしろ型アノテーションが使える分、Crystalの方が書きやすいまであるかも。個人の感想です。

crystalはほんとよくできてるよね。静的型、null安全を実現しつつもrubyistがこだわる「rubyらしさ」がほとんど損なわれていない

RubyはC++と比べると100倍ぐらい遅かったりするんでしょ？
制限時間を緩めてもらわないとさすがにキツそう

コンテスト前に抜くとパフォーマンス出ないジンクスあるからコンテストある日は禁欲してるんだけど、
みんなはそういうのある？

パスタじゃなくて米を食べるようにしている
なんか知らんが気分的に米の方がパフォーマンスが出る、自分にそう言い聞かせてるだけかもしれんが

テンションの上がる音楽をかけながらだとパフォーマンスが上がる気がする
だいたいシューティングゲームのボス戦の曲だが...

>>328
こういうのはお好みですか？




;t=103s
または

;t=728s
あるいは

うんち！w

おしっこ！w

トイレの使用時間がT秒以下の時は「おしっこ」、超えるときは「うんち」と出力せよ

Cを差分に言い換えてあぼん
いやまあ差分の方針でもいけないことはないけど見通しが悪い

C問題、よく見ると双対取ったら二変数のLPだからSeidel法でexpected O(N)？
気づけなくて悲しい

今回のHは典型知識なのかな
あんまりad hoc要素を感じないけどかなり強い人でも解けてない気がする

Gは木を二部グラフ(V1×V2)とみなして大頂点S, Tを追加してSからTに最大フローを流した状態の残余グラフについて考えたら解けた

v1 ∈ V1, v2 ∈ V2がマッチしているとして、v1 → S → … → v2 → v1みたいなサイクルがあることがv1を消しても別のマッチを作れる条件で、
v1, v2, Sがすべて同じ強連結成分に属するなら消してもOK、だめならv1は消せない、と考えると通った

「残余ネットワーク上の貪欲は正しい」としか覚えてないので厳密な証明はよくわからない……

↑別に難しくなかった
最大フローを流した状態の残余グラフをGとして、GからS->v1->v2->Tに流れているフローを押し戻してv1を消したグラフをG'とする
G'にSからTへの増加パスが存在することが、v1を消しても最大マッチングの大きさが減らない必要十分条件である

G'にSからTへの増加パスPが存在するとする
Pがv2を含まなければPを伝ってSからTに行った後、T->v2->v1->Sと戻ってくるのがG上のサイクルになっている
Pがv2を含んでいる場合はPを伝ってSからv2に行った後v2->v1->Sと戻ってくるのがG上のサイクルになっている
どちらの場合もv1, v2, SはG上で強連結

逆にv1, v2, SがG上で同じ強連結成分に属するとする
v2->v1->SはG上で一方通行のパスだから、Sからv2へのv1を含まないパスが存在して、これにv2->Tを加えるとG'上でSからTへの増加パスである

(v2を消す場合もv1, v2, Tに関して同じことが言える)

この方針なら二部グラフでもO(M sqrt(N)))とかで解けてそう

>>337
いまいちわかってないんだけど
V1 = {2}
V2 = {1, 3}
2-1
2-3
という二部グラフで S->2, 1->T, 3->T みたいに張るとS を含む強連結成分ってSのみにならない？
ST両方について解いてる？

>>338
GやG'は残余グラフのほうを指してるつもりだった
その例で言うと、最大マッチングとして2-1を選ぶとGは

S <- 2
2 <- 1
1 <- T
2 -> 3
3 -> T

で、この場合、1, 2, Tは同じ強連結成分に属しているので2を消してもS->Tへの別の増加パスが見つかる
S, 1, 2は同じ強連結成分に属していないので1を消すと増加パスが見つからない

フリーランスに立ちはだかる「常駐」の壁。慣例を打ち壊し、
“テレワーク”案件3割→8割へと成長を遂げた「クラウドテック」の軌跡

リモートワーク求人専門サイト「プロリモート」がリニューアルオープン、業務委託契約の求職者と企業をマッチング

1/3以上が採用につながる高マッチング率、リモートワーク×エンジニア・デザイナー専門の
人材紹介サービス「ReworkerAgent」正式リリース場所からも時間からも自由な働き方を実現！

茨城県日立市、県外からの「テレワーク移住者」に最大151万円の助成金

長野市、市内に移転・事業所設置し、移住することで最大550万円の支援金を支給

フリーランスが活用できる「最大1,000～3,000万円・補助率50%～75%」の
『ものづくり・商業・サービス補助金』とは？概要や条件を解説

『ReWorks（リワークス）』リモートワーク特化型転職サイトとして 3月5日 リニューアル

最近某ngtの質問箱に毎日のようにキモいのが送られていて、流石にかわいそうになってきたな。

最近始めたけどついさっきああでもないこうでもないおかしい計算が合わないみたいなこと延々とやってC問題一つ解くのに2時間半かかった
辛い

実験エスバーって鍛えることできんのかな

数学ではよくある考え方やテクがABC-Cから登場すると思うけど、基本的なものでも初見だと難しいものが多いと思う
最初からスムーズに解ける人たちは散々似た考え方に慣らされてきた人たちだと思うし
ABC-Cぐらいの数学的思考の素養ぐらいは身に付けておいて損はないと思うから、慣れてみるといいんじゃないかな

競技プログラミングは役に立たない！！！１１１１１

グラフや木の問題だったら手癖でよくあるケースを作れるようにしたりして実験そのものをスムーズにできるようにしたり
愚直解の実装を早めにやるように心がけたり
ありがちな注目すべき量(パリティー、剰余、木の葉の数、木の直径、頂点の次数、連続する二項の差分、転倒数、総xor…etc)の知識が増えてくるとエスパー精度上がりそう、俺自身実験エスパーそんな得意じゃないから知らんけど

C問題ぼちぼち解けるかなくらいのレベルなんだけど時々手も足も出ねぇ…ってのが紛れてて辛い
まぁそういうのは大体みんなの正答率も低いんだけど

AGCの問題の解き方わからんね
昨日も、Bは不変量見つける感じで典型要素があるといえばあるけどAとかアドホックすぎる

文字種を減らして考えるの典型かもしれん

不変量見つけられなくて死んだ

AtCoderの「第二回 アルゴリズム実技検定」のテストケースはどこにありますか？

dropbox に上がってないのなら無いんじゃないか

ちょっとずれた話題になるけど競プロ好きな人ってどういう方向の就職が向いてるのかな
よくある金融系とか医療とか販売サイトとかそういうのが全然ピンとこない。ロジックを考えるのが楽しいのであって何を作るかにあまり興味ないというか…

無職

paizaのSを全解き目指してるレベルの者だけど、>>345の意見には納得するところがある。
競プロやる前は、クラス定義してDictionaryでどうこうすれば、大抵の問題は片付いた
わけだが、競プロの問題ではクラスなど定義していたら時間切れになってしまうので、
配列だけで何とかするという、文法的にはレベルの低い書き方をして、いかに実行時間を
短くするかということに主眼がおかれていると思う。ビジネスで使うには10の何乗という
データ数はない場合がほとんどだし、計算に１週間程度掛かるのも問題ないことが多い。
競プロ的な書き方をすると、他のプログラマーとコーディングスタイルがかなり異なって
しまうと思う。

>>355
>>345だけど長文キモイ死ね

>>355
個人で開発するとき役に立つよ

いや役に立たない

paizaはatcoderと比較して時間制限が緩いし、その制限に間に合わないときは、
他に最適なロジックがあるってことだと思うよ

あと競プロを解いていると、自分が知らないやり方とか、効率の良いやり方を
知ることができるということが大きいと思う

意外と文字列と時間の細かい扱い方とか知らないことがあるので
それを知るきっかけになるので勉強になる

その是非や影響の議論は置いといてAB難化は事実だと思うんだけど、copilot対策という噂は本当なのかな？

ソースは特に見当たらないけど、それ以外にABを難しくするモチベがあまりなさそうだからそう言われてる
あとは精々、企業コンではあまりにもひねりのない問題の出題は避けてるとか？

競技プログラミング的なロジック組んで金になる方法考えてみようぜ
とりあえず俺は自動取引系ソフトに一票

取引系の問題は未来が見えてることが前提だからなあ

ABC226-H の解説に類題として挙げられていた以下の問題が解けません
> 区間 [0,1] 上に一様ランダムに区切り線を n－1 本入れて n 個の区間に分けた時、 k 番目に短い区間の幅の期待値は？
ABC226-H 自体はすんなり解けたのですが上の問題は正直N=3の時点で自分には手が出なくて、困ってます

まず、k=1はわかりますか？
これは期待値がx以上になる確率を考えるとできるはず（累積分布関数を考えているという点が類似ポイント）

で、一般の場合は包除原理を適用するとできる

途中式省くけど答えは1/n (1/n + 1/(n-1) + ... + 1/(n-k+1))になります

ええと、k=1の場合は
P(x) を x 以上となる確率として \int_0^{\infty} P(x) dx が求められれば良い
x 以上となるような区切りの入れ方は[0, 1-nx] に区切りをn-1本入れて、各区切りの間に幅xを挿入したものと一対一対応するので
P(x) = (1-nx)^{n-1}
よってk=1の答えは \int_0^{\infty} P(x) dx = 1/n^2
みたいな感じでいいでしょうか

競技プログラミングは役に立たない！！！１１１１１

>>367
355だけど、役に立つよ。頭の体操になる。数学の問題を手で解くより面白い。

月刊はスルー

問題解くときの計算用紙代わりにブギーボードとかの電子メモ帳を買ったんだけど書き心地良いしかなり良かった
おすすめ

>>366
0とmax取るか積分範囲を1/nまでにしないと壊れると思うけど合ってる

>>370
何インチのやつ使ってる？

>>372
10

ipadええぞ

「ゲームで金儲けする時代止められない」ＣＣＰゲームズ代表インタビュー

「CCPゲームズ」のヒルマ・ベーガー代表は14日、オンラインインタビューで最近、
話題に浮上した「プレイトゥオン（Play to Earn 儲けるゲーム）」について「世界のゲーム業界には、
すでにゲームアイテムを取り引きする2次市場が存在する」とし「儲かるゲームは以前にもあったし、
これからも止められない流れになる」と診断した。
CCPゲームズは、世界的な人気ゲーム「イブオンライン(Eve Online)」を開発・運営する。イブオンラインは、
世界で4000万人以上が楽しんでいる。
CCPゲームズは最近、NFT（代替不可能トークン）コンテンツを披露し、注目を集めている。
「アライアンス・トーナメント」というゲーム内の大会商品でNFTコンテンツを配った。

最近勉強始めたばかりの初心者だけど動的計画法でつまづいている
部分構造最適性っていうけど、損して得取れというか一部では損でも全体で見れば最良になるような問題やケースは無いのか？って思う

ないことを証明して使うんだぞ

枝刈り全探索だと思うとよさそう ナップサック問題でいうと大きさは同じなのに価値が低い組みたいにどう頑張っても得にならないケースは使わないように大きさごとに価値が最大のものだけ持っておく感じ？

動的計画法がいまいち理解できない人には、メモ化再帰バージョンを試してみてほしい
と、個人的には思うんだけど、再帰呼び出しそのものが難しいかしら？

馬鹿みたいだけどちょっと大きめの表を手で埋めてみるといいんじゃ

近頃再帰少しずつ書けるようになってきてメモ化再帰も試してはいる
ただたとえばフィボナッチなんかはわかりやすい。同じ計算してるからメモしておくっていうのは
でも経路とかの問題でmemoは違う値にならえないのか？ってなる。値が更新されてたらそれを返すっていうけどさらに更新される可能性はないのか？って

競技プログラミングは役に立たない！！！１１１１１

>>381
違う値になりえる場合は使えないよもちろん

正当性が証明できるときだけ使うし、正当性が担保できるようにアルゴリズムを組むんだよ
これ以上は具体的な問題見ないとなんとも

競技プログラミングは役に立たない！！！１１１１１

白カピを讃えよ

新スレどこやねん

>>386
新スレはここです
向こうに新スレは立ちません

ABCが待ち遠しい
2週間も待てない

ﾜｯﾁｮｲがなんだ実害はないぞ

別にわっちょい怖くなんかないけど、人がおらんとどうしようもない。向こうのスレコンテスト後の数時間はクソスレ極まってるけど、日常のバカ話で人を引き止めてるところはあるのかもしれない

>>390
>コンテスト後の数時間はクソスレ

すまん「コンテスト後の数時間以外はクソスレ」の間違い

くんすこ

常時クソスレだろ？

ごみ

どうして制限時間内に解けないのに、制限時間が終わった途端解法が思いつくのか……俺こういうことよくあるんだけどなんでだろうね

実力が足りてないからです
〜完〜

>>395
何物にも縛られない「自由な動き」が創造性を高めると判明！
https://nazology.net/archives/103764

多分これが一番近い理由だと思う
創造性とは少し異なるけど競プロも発散的思考の要素はある
拘束とも少しずれるけどそれに似た緊張が不調なタスクには絡んでると見てる

>>396
結果だけみて判断するのは他人をフィルターにかけるときは傾向が収束するから合理的だが、個々の事案に向き合うときには不十分だと思うで

風呂に入ってたら思い付いたアルキメデスの原理の逸話もあるし、精神状態に応じて辿り着ける思考は違うんだろうね
特にコンテスト終了前後じゃ劇的に違うだろう
考察得意な人は意図的にその辺のモードをコントロールするのが得意だったりしたりするのかも？

ロシア情勢がキナ臭いけど、CodeForces大丈夫だろうか

ややズレるがchokudaiもコンテスト中は自分は天才だと思い込まないと解ける問題も解けなくなると言ってるな
強い人はメタ認知が上手いと言っていいと思う

昨日のABC-Ex, 答えの値が求まるのはいいんだけど復元ってどうやるの？

解説読んでも理解できないとなかなかつらいものがある

それは本当に実力が足りてなくて悲しくなるやつじゃん

フリーランスに立ちはだかる「常駐」の壁。慣例を打ち壊し、
“テレワーク”案件3割→8割へと成長を遂げた「クラウドテック」の軌跡

リモートワーク求人専門サイト「プロリモート」がリニューアルオープン、業務委託契約の求職者と企業をマッチング

1/3以上が採用につながる高マッチング率、リモートワーク×エンジニア・デザイナー専門の
人材紹介サービス「ReworkerAgent」正式リリース場所からも時間からも自由な働き方を実現！

『ReWorks（リワークス）』リモートワーク特化型転職サイトとして 3月5日 リニューアル

副業・兼業マッチングサービス「クラウドリンクス」登録者数2万人突破
中小企業で進む副業人材の採用、96％が継続採用を希望

茨城県日立市、県外からの「テレワーク移住者」に最大151万円の助成金

長野市、市内に移転・事業所設置し、移住することで最大550万円の支援金を支給

フリーランスが活用できる「最大1,000～3,000万円・補助率50%～75%」の
『ものづくり・商業・サービス補助金』とは？概要や条件を解説

ここが新スレですね

こどふぉのE、思い付く過程が知りたい

むこうのスレもうだめかもしれんね

こっちでまったりやるか

うんち！w

おしっこ！w

今日のABCの感想はこっちでやればええんか？

おれもこっちにする

むこうってどこ？

まともな会話ができるならどこでもええで

競プロ関係のツイートに対して言及するならまだしも写真に対して色々言うのは終わってる

ABCでます

うーん、FよりもさっさとGに取り組むべきだったか

EFGHも50点ずつでもいいから点差欲しいな
ABCDF>ABCDEだろうし

Eの解説賢い
累積和とダブリング使って解いたわ

低レベル帯は上位アルゴいらないって誰かが言ってたけど今回のEとかみたいに考察省略できるのはアドだよなぁ

ワッチョイ有りだとガイジスレとイクが居なくなるのでは？

Bがこの重さってまじ？
もう新規囲い込む気ないよねこのサイト

>>420
>>421
ワッチョイ一致してるけどスマホをwi-fiに接続しただけで自演の意図はないです
紛らわしくてごめん

BCDの3問がCCCになってる

普通にナイーブだったし何も気にしてなかったけど、diff見るとたしかにB高いな
Fもなんかむずかったし、また文句出そうだな

プログラミング入門者で、競技プログラミングやってみよーって人が今回のABCのBをみたらどう思うだろうね
これじゃあ人なんて増えないわ

Fみたいなやつ実装爆発して終わってまう

bよく読めばそんなに難しくないんだけどな
出題者がdiff低く見積もったのもわかる気がする

ABC255のBのdiffを余裕で越してきたな
歴代最難関Bか

ABCで今回のよりもdiffが高いBが出たのは少なくとも5年前

灰や茶にとってはちょっと難しい要素が複数詰め込まれてた感じか？
問題文がちょっとむずい
8方向遷移がちょっとむずい
順番に並べて整数を作るのがちょっとむずい
みたいな

Bはひたすら面倒くさかった

二次元配列の8方向見ていくやつはスニペットとして持っとくべきだよね

水色の自分にとってはEが面白くて、頑張って解いたらレート上がって楽しい回だった

Bはchokudai作問だったか
確かにC問題の難易度だよなあこれは

B問題はdiff200くらいにしてあげるのが新規ユーザーも心折れずに、それでいてチャレンジできるから良いと思うの

競技プログラミングって実際にはプログラミングというより
基礎学力、算数の力を問うようなものだろ

実際超有名進学校の生徒が多いし

>>437
そもそも競技プログラミング(計算機科学)は数学の一分野

>>436
diff200くらいだろうと思ってb問題にした結果です

昨日のBは実際難しかったね
あまり競プロ界隈は読解力で差がつくということを認めない傾向があると思う(実際は高校生大学生レベルでもそこで差がつく層はかなり多い)

今回の問題ってどこでみられるの？

何の？

PAST？

>>439
chokudaiさんだっけ？B問題作ったの
確かにただのループだけで解けるならdiff200くらいで済んだかもしれんが
マスの外に飛び出しても良いってのが難易度上げちゃったんだろうな

不馴れだと8方向それぞれループ書くことになるし

Bはcodeforces div3, 4あたりで頻出だし個人的に簡単だったけどAtCoderだけやってる人は実装めんどかったと思う

atcoder は実装弱いって話はホントなの？

chokudaiがそんなこと言ってた気がする
基本的に考察できたらすっきり解けるパズルが多いみたいな

O(1)の数学問題はめっちゃ解かれるよね
文系の俺、順位表のAC数見ていつも涙目

実装強いほうが実務では役に立つんだよな

AHCっていうのがありましてですね

AHC012、ずっと任意の向きの直線考慮しててラスト一時間でようやく縦横だけのほうがスコア出るってたまたま試して気付いたんだけど、
初期から縦横だけでやった人はどうやって縦横だけで十分って気付いたの

エンジニア力を養成するためにコンテスト途中で仕様変更があるatcoder

実装弱者だから、斜めの線引いたときのスコアの計算方法が分からなかったんだよ

任意の向きで考え始めると時間かかるからとりあえず縦横に制限すれば楽だな→意外と点取れるな
って感じだったが
苺はランダムだから、まずは直線の向きどうこうよりは囲んだ面積のほうが個数に寄与しがちだと思った

まともにスコア計算を高速化できない方針に短時間コンで手を出すべきじゃないんだよな
となると縦横が第一候補になるのは自明じゃないか？WaveletMatrixとか使えるのだから

色々ありがとう
初手とりあえず広めに解を取ってしまいがちなんだがもうちょっと色々考えてみる

アルゴは解けなかった問題を解けるようにする/解ける問題を速く解く、で強くなれるけど、
ヒューリスティックはどうやったら上位勢との差が縮まるのか分からん

そういうのこそ社長に聞いてみるべき

焼きなましや山登りは試行回数が命だからアルゴが役に立つとか言ってたな

だめだdiv2のD全然分かんねえよ爆死だわ

ヒューリスティック頑張るとしたらやっぱりマラソンマッチの過去問やりまくるとかがよかったりするんだろうか

一問やりこむことのが大切な気がする

あっとこ黒字化したんだな

自身が解けない問題をしっかり理解するきっかけになるからあえてレートよりdiffが高い問題を解説したら実力伸びる気がしてきた
ただ解説の精度に著しい問題が発生しそう

他人の実力を下げることにも貢献して、レート上昇に効果的かもしれない

自分の色がわかるように書いておけばいいよ

競プロ得意じゃない人が競プロ解説するの、実務能力のない層がプログラミング教材作って荒れてる駆け出しエンジニア界隈となんら変わりないのでは

一色上のdiffくらいなら許されないかな
大筋は公式解説に則れば間違いも少ないと思うし

赤は何を解説しても許されるので赤になりたい

公式解説を解説するだけのメタ解説記事になりそう

黄色か橙くらいあれば diff 関係なく理解さえできれば解説書けそう
それ未満は自分が正しいこと書いてるかの判断もつかなさそう

書いた時点でのレートもつけとけば別に書くの自体はご自由にという感じだけど

そもそもインターネットを汚さないでください
勝手に書くのはもちろん自由だけど公開せずに非公開のまま独りで満足してね

寒色の人に限ってはすべてこのようによろしくお願い致します🙇

表現の自由
はい論破

これでqiitaに2色上の問題解説してるやついたらスレ民バレしそうだな
ちょっと温めとこ

炎上、身バレに対する一番の対処はやっぱり沈黙なんだな

ムイタerの集合とマイタerの集合は背反なのでム板に書き込んでることがバレてもノーダメのはずです＞＜

蟹江ってどこに行ったんだ
最近聞かないにょ

猿者は追わず

阿部ちゃん大丈夫かな🙏

俺の晋三...😭

R.I.P.

うにくんtwitterやめたの？

普通にアカウントある気がする？

喪に服して賞金はしばらく廃止しよう

最近発言やばかったしやめたほうがいいと思う

安倍の死を悲しむべきかくんの復活を喜ぶべきか

うにくんって社会人なの？

最近か？
酔ってる時はずっと発言ひどいイメージだけど

>>489
コンテストに出て「実力を発揮できないパフォーマンスだった」と病むんだから全然めでたくねえよ

競プロやるな、まずはvimをやれといわれたけど本当ですか
手がホームポジションから離れるだけのロスですら命取りらしい

emacsかVScodeしか勝たん

>>493
ABC卒業したらそういうところも気にする必要あるのかもね