競技プログラミング総合スレ 64

2022/10/02(日) 17:43:58.66

↑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/

※前スレ
競技プログラミング総合スレ 63
https://mevius.5ch.net/test/read.cgi/tech/1627477128
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured

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

2022/12/20(火) 03:06:34.58

全域ってのがよく分からんが、木なら難しくない
総和が分かれば平均は分かるから総和の話をするとして、各辺についてその辺が距離に寄与する分を足せば良い
これはこの辺を消した時にできる2つの木の頂点数の積だから、木DPを1回すれば求まる
O(|V|)

2022/12/20(火) 08:11:20.58

>>841
いや、それを憲法のようにずっと変えないのはおかしくない？って言ってるんだが
全体的な底上げがされてるならその限りではないでしょ
2年前の青と今の青って解ける問題が違うよねって話。

**デフォルトの名無しさん** (JP 0Hf6-3jwL) · 2022/12/20(火) 09:41:10.31

レートに対する評価は絶対評価じゃない
解ける問題が多少変わろうが評価は大して変わらなかったってだけ

2022/12/20(火) 12:00:03.38

>>848
回答サンクス
木だけど、重み付きなんだよね

計算式がかなり複雑になると思うんだ

2022/12/20(火) 12:42:02.98

重み付きでも難しくないよまず適当に頂点を選んで、根にする
根からdfsをして、各頂点を根とする部分木のサイズを計算する(nums[v]: vを根とする部分木のサイズとする)

辺(u,v,w) (頂点uとvを結ぶ、重みwの辺)
が2点間の距離の総和(=sum(dist(u,v)) (1≤u<v≤N))に寄与する量は、
uとvの内、根から遠い方がvなら、w * (N-nums[v]) * nums[v]
根から遠い方がuなら、w * (N-nums[u]) * nums[u] になる

典型だから、ABCに転がってないか探したけど見当たらないな(CFならありそう)

2022/12/20(火) 13:25:55.01

とりあえずコード書いてみたわ、こんな感じで合ってるか？
https://ideone.com/oTWtMA

2022/12/20(火) 13:39:41.85

kotlin読めないけど、合ってると思う
min(subtreeSize[edge.source], subtreeSize[edge.target])のところが場合分け減らせてて良いね

2022/12/20(火) 15:11:54.66

>>850
atcoderの立場として発言してるだけかと。
アルゴリズムの研究者が水色とかあるっぽいし、競プロにフィットしなければ緑以下が普通だろうけど、時間で競ってパズル色も強すぎる競技と、アルゴリズム力は結構離れてると思う。

2022/12/20(火) 16:32:33.88

>>850
手繋いで皆でゴールとか好きそう

2022/12/20(火) 18:29:54.55

はてなブックマークのテクノロジーに再帰は遅いって記事が載ってたわ。

2022/12/20(火) 20:11:04.77

そりゃそうだ

2022/12/20(火) 20:47:10.47

遅いといっても定数倍が遅いだけだし

2022/12/20(火) 21:04:04.81

なんで遅いの？

2022/12/20(火) 23:20:27.24

>>853
なるほどおおおお
ただ、理解できそうで理解できない
確かにその式だと、平方完成したときに距離がn/2で最大になることがわかりそう。
ただ、なぜx*(N-x)になるのかがいまだに理解できていない。。

確かに遠い方を選べばx = Nにはならないから、0にはならない、これはわかるが。。
例えば直線だった時に最初の根で中点を選んでしまったとき、
根だから当然部分木のサイズはNになり、N回の寄与しかできない
中点だからもっと大きい数寄与できるはずでは。。
混乱してきた。。

2022/12/20(火) 23:24:41.27

https://imgur.com/a/7XCo1vG
まずこれがn=5の場合に中点を選んだ時のツリー

2022/12/20(火) 23:29:16.90

https://imgur.com/a/urLR8OE
cdの辺(４)は遠い方だから、dの部分木サイズ２、
つまり2×3だから6
なるほど、、たしかに6回寄与してる。。。しかしなぜN-nなんだ。。
2項定理の基本がわかってないのかな

2022/12/20(火) 23:37:55.90

まてよ、なるほど
自分自信を含んだ場合のそれより下の部分と上の部分が何通りあるか、それをどこまで伸ばせるかということか
なるほど、わかりそう

2022/12/20(火) 23:43:39.65

一人で連投すまない
なるほど！！めっちゃ理解した
木構造であっても直線であっても、そのノードが双方向から挟まれてるとしてどの位置にいるかっていうことが一定になるんだね

いや凄いな、典型っていうけどこういうの当たり前に理解してる人たちなのか。。
感動した

2022/12/21(水) 00:05:31.28

理解したかおめでとう！
じゃあ次は全ペアのパスの長さの平均じゃなくて中央値を考えてみてね

2022/12/21(水) 00:08:11.19

>>867
サンクス！！
中央値。。。。。
n(n-1)/2通りある中から実態のある中央値を考えるのか

一晩考えさせてください。

2022/12/21(水) 00:20:21.60

>>867
最初に聞かせてほしい
いじわる問題じゃなく本当に求まる？

2022/12/21(水) 00:24:15.31

https://imgur.com/a/kHjv6cK
この場合は8が中央値
2分探索を使うわけでもないし不可能な気が。。

2022/12/21(水) 04:04:43.89

中央値は結構難しいような
中央値だから二分探索を使うというのは良いと思っていて、でも二分探索の判定部分で、
長さx以上のパスの個数を計算する必要があって、これを計算するのは難しい気がする

2022/12/21(水) 04:29:36.11

え、中央値解けるん？
考えたこと無かったわ、やってみるか
重み付きだよね？重み無ければ重心分解して畳込めば終わりだし

2022/12/21(水) 05:22:01.10

自分はそもそも重心分解を知らなかった正しいか分からないけど、
重心cからbfsをして、各頂点v(1≤v≤N)までの距離d[v]を求めて、各d[v]を座標圧縮してBITに記録する
各d[v]について、d[u]≥x-d[v](1≤u≤N)となるuの数がBITで計算できる (x-d[v]もd[v]とまとめて座標圧縮する)
このままだと重心から見て、同じ部分木に属するパスを含んでしまうから、
重心から見て、vと同じ部分木に属する頂点uについてのみ、d[u]を座標圧縮してBITに記録して、
d[u]≥x-d[v]となるuの数を引く、とかで合ってるかな？

2022/12/21(水) 05:56:39.59

https://judge.yosupo.jp/problem/frequency_table_of_tree_distance

2022/12/21(水) 13:26:19.80

重心からの距離をソートして頭と尻からそれぞれ見ていけばデータ構造使わなくてもカウントはできる
（結局ソートでlogつくが）

二分探索と分割統治の分を合わせてlog3つになるのかな

2022/12/21(水) 13:55:04.06

確かに座標圧縮もBITもいらないか
O(N * (log^2)N * log(Nmax(w))) か (重すぎる)

2022/12/21(水) 16:51:57.69

あー、なるほど理解した
確かに中央値求まるな……重すぎるけど

2022/12/21(水) 17:20:24.15

ちょっと待て待てなんかすごいことになってる
重心分解なんか聞いたことないぞ

2022/12/21(水) 17:48:02.52

重心分解と座標圧縮について調べてみた

重心分解の条件が部分木が全てN/2以下になっているっていうことは、直線の場合が最大でっていう理解であってるよね？(直感的には明らかだけどなぜn/2以下ならといえるのか厳密な定義があれば教えてほしい）

後、画像圧縮も調べてみたけど、これってどういうときに使うものなんだろう

2022/12/22(木) 00:38:14.06

毎回ソートする必要なくてlog1個落ちる？

2022/12/22(木) 00:44:54.15

競プロ力って言うか、実務とかのプログラミング力ってどうすれば鍛えられるかな
持ってる知識は同じだとして
基礎体力が強い方が勝つんだろうけど、これってワーキングメモリの保持力だったりするんだろうか

2022/12/22(木) 01:03:51.33

実務とかのプログラミング力、っていわれても環境によって求められるものが違いすぎてなんともだけど、きみがいうプログラミング力ってなんなん？
個人的に「プログラミング力がある」って感じるひとは、それに比例して知識量もあるし、知識が同じなら差がつくとはどうしても思えない

なかには知識は全く同じはずなのにプログラミングすげえ！みたいな天才マンがいるの？
そんな人に出会ったことないし想像できない
というか仮にいたとしても技巧的なコードばかり書いててメンテできなそう

2022/12/22(木) 02:41:47.06

英語鍛えりゃいいんじゃね
今まで見てきた凄腕はみんな英語が達者で情報を日本語以外で取り入れまくってた

2022/12/22(木) 03:01:13.83

英語を鍛えれば有能になるんじゃなくて有能人材は元々英語くらいなら余裕だから因果関係が逆な気もする

2022/12/22(木) 03:05:02.66

競プロでも強い人がこどふぉとかの英語問題文で困ってるの聞いたことないし

2022/12/22(木) 05:40:46.21

例えば高専で、JavaScript, Python をやっていても、
なんだ、Ruby on Rails, Docker, AWS Solution Architect もやっていないのかと、
ウェブ系企業では全く相手にされない

そういう香具師でも、英語さえ出来れば、GAFAM では採用される。
まあ、競技プログラミングもそこそこ出来るし、まあ雇っても良いかという感じ

印象としては、Linux のシステム構築運用できない香具師が、GAFAMに受かる感じ

2022/12/22(木) 06:18:15.61

英語力はchokudaiが既に反例だから違うだろ
英語力がある方が有能だけど
実務とかのプログラミング力はどれだけ色々なことに手を出してきたかだと思うな、凄い奴は経験してる分野が多岐に渡ってて、何聞いてもそれなりに理解してる答えが返ってくる

2022/12/22(木) 08:53:39.96

別にGAFAM受かっているから優秀とは思わないけど、DockerやAWSみたいな個別的な技術の知識より学術的な情報科学に強い人材の方を重視しているから、一見モダンな知識がないように見えるだけなのでは？
そんなの入社後必要に迫られて勉強すればすぐ身につくようなものじゃないか

2022/12/22(木) 09:04:09.07

CodeForcesの問題文は謎の登場人物、ストーリーが面倒くさいだけで、別に競プロの問題を抽出して理解するのにそんなに英語力いらない気がするな
英語圏の中学生向けの小説の方が難しいと思うわ

2022/12/22(木) 09:48:19.57

>>879
重心探索のアルゴリズムで重心が定まったとき、重心とされた頂点の親の方の連結成分の成分数がn/2以下と言えるのか？という疑問かな？
であれば、重心を根とした部分木の頂点数はn/2より大きいから、親の方の連結成分＝重心を根とした部分木の頂点数はn/2以下になるって感じかな？（全然違う疑問だったら言ってくれ）

あと、画像圧縮と座標圧縮は別物だね
座標圧縮の方が簡単で競プロで頻出

2022/12/22(木) 09:54:55.85

座標圧縮って競プロだと当然のように使われるけど実際に業務とかでも活用されてるのかな(まあ大した実装量じゃないからわざわざ名前をつけてないだけなのかもしれないけど)

2022/12/22(木) 09:55:19.15

>>890
あ、
×親の方の連結成分＝重心を根とした部分木の頂点数
〇親の方の連結成分＝重心を根とした部分木を元の木から取り除いた連結成分の頂点数
ね

2022/12/22(木) 11:36:03.34

>>891
画像、科学計算分野とかゲーム開発では使うかもしれない
勤怠管理ソフトで使ってるのは聞いたことない

2022/12/22(木) 11:53:21.34

普通はハッシュマップかマップをまずは使いそう

2022/12/22(木) 13:07:07.73

座標圧縮っぽいことは思い出してみると業務で使ったことあるけど座標圧縮だと意識してはいなかった気がする

2022/12/24(土) 10:36:20.69

クリスマスイブだけど今日も競プロ参戦するぜ

2022/12/24(土) 12:37:53.51

プログラムで活躍としては
センスのみ<知識のみ<<<知識+センス
なんだよ
これで勘違いが起きることが多い

知識のみしかもってないと一見最上なんだけど、実は何も産み出さない

知識のみでも誰かがセンスを持ってると一気に有益なものが産み出される
つまりピースを埋められる存在になれるかどうかで活躍は変わってくる

2022/12/24(土) 18:09:57.90

今日のコンテストはどうなるんですか

2022/12/24(土) 22:41:01.66

ギリギリ解けたけどEムズいよ

2022/12/24(土) 22:46:01.54

E解けないからFから解いたんだけどFもFで計算量的に大丈夫なのか？って疑ってた最初の方に思いついた解法(ユーザー解説の奴)が他の解法で悩んだ挙句普通に通ったからあまりスッキリしない

2022/12/24(土) 22:55:16.29

D計算時間を解決できなかった
配列とコンテナで管理するのが速いのかー。
アイデアはあったけどどれが最適かわかんなかった

2022/12/24(土) 23:18:12.92

Eのdp複雑すぎて草

2022/12/24(土) 23:24:36.98

最近のE難しい気がする

2022/12/24(土) 23:30:32.81

D、問題文誤読して違うことやってたのにACになってた
（誤答になる入力が存在することは確認済み）

2022/12/24(土) 23:35:14.60

(a(b)a)がyesでも通るって話題になってるね

2022/12/25(日) 10:23:23.93

yesでも通るというかNoが通らず不正解になると言う方が状況を誤解なく伝えられるんじゃね

2022/12/25(日) 10:47:58.50

ABC283
そもそもの難度調整が下手すぎないか？よく考えて作ってるのか疑問

2022/12/25(日) 10:54:07.27

難易度言うならそもそもABCでD以上出さなくていんじゃね
D以上はARCに回せばいい
レーティングも400まででいいよ

2022/12/25(日) 12:35:37.19

黄色以上は解答できなくして賞金も貰えないようにすればいいよ

2022/12/25(日) 13:12:05.09

昔青だった人が水色なんだからビギナーコンテストはmax水色~緑下で十分すぎる

2022/12/25(日) 14:00:20.35

AGCって1200無くても受けて良いの？
暇だし受けてみようかな

2022/12/25(日) 15:04:24.59

レートつかないだけで参加できると思うよ

2022/12/25(日) 15:41:34.02

ABC上位中国勢ばかりやんけ
少し前より青→黄の難易度かなり上がってそう

2022/12/25(日) 19:32:07.15

>>912
あー、レートつかないのか。なら後日でも良いか

2022/12/25(日) 19:34:29.29

人類の5人に一人が中国人だから。
石を5個投げれば一つは中国人に当たる。

2022/12/25(日) 19:45:56.78

rated上位はマジで中国人がほとんど

2022/12/25(日) 19:48:23.57

理由はしらんけど、どうやら中国勢は現在のレートが実際の実力に追いついてないひとが多すぎるから
だから中国人がたくさん参加するとパフォがちょっと渋くなるかもしれんなあ

2022/12/25(日) 19:49:02.80

中国って中高生くらいで強い人多いけど競プロの塾とか競プロの中国語の参考書とかもあるのかな

2022/12/25(日) 19:52:07.11

この前2012年生まれの中国人の赤いたぞ
年齢詐称じゃなかったらすごいな

2022/12/25(日) 19:56:16.55

>>918
塾はあるらしい
情報オリンピックで活躍できたら、好きな大学に入れるから高校生ががんばるらしい

参考書については、おれたしか2008年くらいにICPC対策の英語の参考書みたいなの買ったことあるんだけど、たしかそのオリジナルが中国語だったはず（俺が買ったのは英語に翻訳されたバージョン）
まあ今ならきっとかなりたくさんあるでしょ

2022/12/25(日) 20:13:44.45

なんだ塾があるのか。
勉強したらできて当たり前だな。
中国人はしょせん中国人にすぎないな。

↑って、ネトウヨが言い出しそう。

2022/12/25(日) 20:23:10.79

中国なら有り得そうとも思うが同時に詐称も沢山いるしなあ

2022/12/25(日) 20:40:15.68

ネトウヨって結局、清和会のために統一教会を支持してる奴らだろ？
国益だの愛国だの言ってるけど、その国というのは韓国のことだろう。

2022/12/25(日) 21:12:16.73

ITは超左だからそういうのはないんじゃ

2022/12/25(日) 22:10:30.90

>>923
頭が悪いからパヨクになっちゃうの？
それともパヨクだから頭悪くなるの？

2022/12/25(日) 22:17:25.74

>>925
いまは社会科で習わないのか？
ネトウヨは自民党清和会、つまり韓国朴正煕派閥。
パヨクは社会党、つまり朝鮮総連派閥。

2022/12/25(日) 22:39:50.62

>>926
最近のネトウヨは嫌韓じゃないのか・・・
清和会のせいでややこしいな

2022/12/25(日) 22:43:35.02

>>927
金大中暗殺未遂事件とかも習わないのか？

2022/12/25(日) 23:25:15.62

>>927
元々ネトウヨを作ったのが韓国人だろ。
いいように操られやがって。

2022/12/25(日) 23:27:58.85

私を貶しても何もでないよ🥺

2022/12/25(日) 23:32:02.62

>>930
なんか出せよ。

2022/12/25(日) 23:45:09.06

統一教会は日本で、ゆとりある教育を提唱しているが、韓国では全く逆のことを言ってるからな。
騙されるなよ。

2022/12/25(日) 23:46:50.19

三角関数は高度な数学じゃないぞ。
全員が知っていなければならない基本的な算数だからな。
統一教会派の国会議員に騙されるなよ。

2022/12/26(月) 00:01:23.73

snukeさん滑り込んだな
にしても中国が多い

2022/12/26(月) 00:03:13.58

tourist敗れるのも日常風景になってきた

2022/12/26(月) 00:06:51.77

前の二つの状態を持つDP、前日のABCでもあったのにDPしなくても掛けていけば求まると迷走して1完遅解きだからダメダメだ
Bもどう実験すれば思いつけるのか

2022/12/26(月) 00:07:49.33

タイムリーだね
すぬけさんやtouristいなかったら本当に中国勢が強い
横綱さんもかなりすごい

2022/12/26(月) 00:11:02.93

chokudaiも3000の実力ないとか言いながらしっかり34位か

2022/12/26(月) 01:50:16.22

すみません、くんerですけど明日からこっち書き込みます

2022/12/26(月) 01:57:43.17

ワスも本格的にこっちに進出じゃい(´・ω・`)

2022/12/26(月) 02:03:28.25

もしngしたかったら
1週間毎にｵｯﾍﾟｹ Sr1f-v7GxのｵｯﾍﾟｹSr以外の部分をngお願いします(前2桁はよく変わるので)

2022/12/26(月) 02:07:40.38

こんな感じで

2022/12/26(月) 02:07:53.69

変わってねぇ...

2022/12/26(月) 02:07:56.66

くんer真面目かよ

2022/12/26(月) 02:46:07.41

うんち！w

2022/12/26(月) 03:47:58.81

誰

2022/12/26(月) 08:20:22.77

今の日本の若い人って頑張らないし甘やかされてるしそりゃ全体的な競争力低くもなるわ

2022/12/26(月) 12:27:01.64

競争力を上げるためにはもっとスパルタにせねば、とお考えなのですね