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

2021/07/28(水) 21:58:48.02

!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
https://medaka.5ch.net/test/read.cgi/prog/1626625368/

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

2021/08/30(月) 00:04:52.56

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

2021/08/30(月) 02:38:00.45

システムテスト弱forces

2021/08/30(月) 03:40:50.80

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

2021/08/31(火) 01:37:25.41

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

2021/08/31(火) 03:50:25.65

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

2021/08/31(火) 18:30:11.43

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

2021/08/31(火) 21:10:30.18

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

2021/09/01(水) 12:14:20.08

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

2021/09/01(水) 12:15:18.08

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

2021/09/03(金) 17:59:41.58

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

2021/09/03(金) 18:06:19.71

すごいwikiですね

2021/09/03(金) 18:30:45.42

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

2021/09/03(金) 23:09:38.04

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

2021/09/03(金) 23:16:13.01

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

**デフォルトの名無しさん** (JP 0Hff-Sfec) · 2021/09/04(土) 22:47:23.13

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

2021/09/04(土) 23:10:09.45

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

**デフォルトの名無しさん** (JP 0Hff-Sfec) · 2021/09/04(土) 23:20:56.78

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

2021/09/06(月) 01:35:28.67

実装重すぎforces

2021/09/11(土) 22:40:52.42

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

2021/09/11(土) 22:41:48.93

Eで時間使いすぎた…

2021/09/11(土) 22:52:30.32

c嫌い

2021/09/12(日) 01:13:19.29

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

2021/09/12(日) 01:33:19.35

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

2021/09/12(日) 01:41:12.36

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

2021/09/12(日) 01:43:36.75

その通りでございます

2021/09/12(日) 04:27:40.04

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

2021/09/14(火) 04:13:51.06

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

2021/09/14(火) 05:25:48.22

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

2021/09/14(火) 07:41:25.33

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

2021/09/14(火) 11:44:56.93

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

2021/09/14(火) 14:42:52.17

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

2021/09/14(火) 14:59:12.87

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

2021/09/14(火) 15:42:22.96

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

2021/09/14(火) 18:34:53.52

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

2021/09/14(火) 19:14:04.78

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

2021/09/19(日) 08:00:29.80

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

2021/09/19(日) 12:40:14.90

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

2021/09/19(日) 13:16:18.07

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

2021/09/19(日) 14:43:04.37

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

2021/09/19(日) 15:23:37.00

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

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

2021/09/19(日) 17:32:36.92

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

2021/09/19(日) 17:42:41.13

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

2021/09/24(金) 23:47:31.60

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

2021/09/25(土) 07:46:07.75

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

2021/09/25(土) 09:58:53.83

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

**ハノン** ◆QZaw55cn4c (ﾜｯﾁｮｲ b247-+9yW) · 2021/09/25(土) 13:30:23.74

>>328
こういうのはお好みですか？
https://www.youtube.com/watch?v=CZiHhS7r6M0

https://www.youtube.com/watch?v=4IgQ6LNE9Yo&;t=103s
または
https://www.youtube.com/watch?v=4IgQ6LNE9Yo&;t=728s
あるいは

2021/10/16(土) 03:00:16.89

うんち！w

2021/10/16(土) 12:28:23.59

おしっこ！w

2021/10/16(土) 19:45:04.31

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

2021/10/16(土) 23:50:11.18

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

2021/10/17(日) 00:05:50.78

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

2021/10/17(日) 23:29:51.69

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

2021/10/17(日) 23:42:38.80

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

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

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

2021/10/18(月) 21:30:25.41

↑別に難しくなかった
最大フローを流した状態の残余グラフを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)))とかで解けてそう

2021/10/18(月) 23:04:34.93

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

2021/10/18(月) 23:21:33.28

>>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を消すと増加パスが見つからない

2021/10/21(木) 16:15:46.81

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

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

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

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

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

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

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

2021/10/24(日) 20:18:53.47

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

2021/10/25(月) 00:43:40.20

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

2021/10/25(月) 04:27:00.29

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

2021/10/26(火) 22:34:52.78

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

2021/10/26(火) 22:38:10.35

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

2021/10/26(火) 22:43:03.70

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

2021/10/30(土) 01:57:46.41

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

2021/11/01(月) 14:31:29.29

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

2021/11/01(月) 17:13:19.31

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

2021/11/01(月) 18:46:47.15

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

2021/11/04(木) 22:10:01.18

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

2021/11/04(木) 22:38:53.47

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

2021/11/13(土) 00:38:47.84

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

2021/11/13(土) 13:07:06.56

無職

2021/11/13(土) 23:13:52.96

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

2021/11/13(土) 23:22:26.39

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

2021/11/18(木) 20:07:30.91

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

2021/11/18(木) 20:15:30.78

いや役に立たない

2021/11/18(木) 20:46:20.19

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

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

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

2021/11/28(日) 10:44:07.64

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

2021/11/28(日) 10:56:10.69

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

2021/11/28(日) 13:18:03.58

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

2021/11/29(月) 02:15:40.60

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

2021/12/01(水) 02:28:23.44

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

2021/12/02(木) 20:39:33.36

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

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

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

2021/12/04(土) 08:39:45.51

ええと、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
みたいな感じでいいでしょうか

2021/12/04(土) 11:45:52.27

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

2021/12/04(土) 12:33:36.19

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

2021/12/04(土) 13:13:02.72

月刊はスルー

2021/12/04(土) 17:52:55.15

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

2021/12/04(土) 18:44:46.61

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

2021/12/04(土) 23:30:13.88

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

2021/12/05(日) 00:26:27.51

>>372
10

2021/12/07(火) 22:01:44.64

ipadええぞ

2021/12/18(土) 14:36:12.14

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

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

2021/12/21(火) 13:47:34.46

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

2021/12/21(火) 14:46:04.05

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

2021/12/21(火) 18:49:26.20

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

2021/12/21(火) 20:30:24.97

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

2021/12/21(火) 21:03:00.48

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

2021/12/22(水) 02:28:33.78

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

2021/12/22(水) 07:21:37.51

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

2021/12/22(水) 22:28:18.00

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

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