競技プログラミングにハマるプログラマのスレ 159

**仕様書無しさん** · 2024/02/22(木) 22:45:21.47

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

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

前スレ
競技プログラミングにハマるプログラマのスレ 157
https://medaka.5ch.net/test/read.cgi/prog/1707621659/
競技プログラミングにハマるプログラマのスレ 158
https://medaka.5ch.net/test/read.cgi/prog/1708272894/

**仕様書無しさん** · 2024/02/24(土) 22:49:31.31

そらまあDの問題設定なんて5秒で思いつくレベルだし、解放も自明だから既出じゃ無いわけないだろ

**仕様書無しさん** · 2024/02/24(土) 22:51:01.69

中国父さん企業なので中国忖度データ構造ボス問回だったというわけか

**仕様書無しさん** · 2024/02/24(土) 22:51:02.42

むしろDが今までに1度も出題されてなかったらびっくりするわ

**仕様書無しさん** · 2024/02/24(土) 22:51:20.84

>>340
なりすましだろこれ

**仕様書無しさん** · 2024/02/24(土) 22:52:16.69

共有してたらEもFも解けるだろうし、ただ単に既出なんじゃないの？
双対セグ木の活用法としてはひねりなさすぎだし

**仕様書無しさん** · 2024/02/24(土) 22:52:38.76

ABCDGの中国人大量にいるんだけど中国典型なのかな🙄

**仕様書無しさん** · 2024/02/24(土) 22:54:08.75

高度データ構造問題は中国勢が大量に解くからdiff下がるって数日前に言われたばかりでしょ

**仕様書無しさん** · 2024/02/24(土) 22:54:35.57

もうGで高度データ構造出すのやめろ😡
中国勢にレート取られちゃう😭

**仕様書無しさん** · 2024/02/24(土) 22:54:43.10

過去レス精進してきますね

**仕様書無しさん** · 2024/02/24(土) 22:55:18.34

作用側だけ効率良く扱いたい→双対セグ木はガイジスレ典型だな
ガイジスレ精進を真面目にやってれば余裕で全完可能
何分で全完できるかが重要

**仕様書無しさん** · 2024/02/24(土) 22:55:23.16

中国支配的かぁ

**仕様書無しさん** · 2024/02/24(土) 22:55:56.41

双対セグ木は高度データ構造というほどでもないだろ

**仕様書無しさん** · 2024/02/24(土) 22:56:26.81

双対セグ木連想は操作内容から自明だろ　典型ですらない

**仕様書無しさん** · 2024/02/24(土) 22:56:35.93

これ625はおかしくないか?高々600だし550-575でもよさそう

**仕様書無しさん** · 2024/02/24(土) 22:57:10.41

>>344
ちげーよ
お前こそマスくんに粘着し過ぎだろ

**仕様書無しさん** · 2024/02/24(土) 22:57:26.05

高度データ構造でARC出てないインコに負けるとキレそう

**仕様書無しさん** · 2024/02/24(土) 22:57:48.97

双対セグ木の遅延伝播させる必要今回は無かったのか(毎回根まで辿った方が楽)
G方針あってたのにそれでバグってたわカスが

**仕様書無しさん** · 2024/02/24(土) 22:58:01.31

インコが舐められてるだけ
実際、チャイナインコに対してジャップインコは全然解けてないし

**仕様書無しさん** · 2024/02/24(土) 22:58:20.42

チャイナインコ>>>>>>ジャップインコ
種として劣ってて悲しいよ

**仕様書無しさん** · 2024/02/24(土) 22:58:33.25

悔しかったら北京大学に入り高度データ構造を学びましょう

**仕様書無しさん** · 2024/02/24(土) 22:58:59.39

POJで精進してるとか書き込んでたせいじい以上のガチ爺元気にしてるかな

**仕様書無しさん** · 2024/02/24(土) 22:59:46.16

3回前のGをいじったら解けたよ

**仕様書無しさん** · 2024/02/24(土) 23:00:16.33

>>355
すまん
マス君ファンだからつい気になった

**仕様書無しさん** · 2024/02/24(土) 23:01:04.10

平方分割系とかでもゴリ押せなくはなさそうだったけど双対セグ木もどきでやった

**仕様書無しさん** · 2024/02/24(土) 23:01:32.65

遅延させなくていいの賢すぎる

**仕様書無しさん** · 2024/02/24(土) 23:02:13.03

椅子温めてただけのインコのABやるだけ発言ほんと好き

**仕様書無しさん** · 2024/02/24(土) 23:03:21.68

遅延セグ木をソラで書く練習をしてれば

**仕様書無しさん** · 2024/02/24(土) 23:03:28.42

そこでしかイキれないんだから許してやれ

**仕様書無しさん** · 2024/02/24(土) 23:03:54.88

ABCがratedなわけないので立ち回りとか気にせずFから解いたが普段のFより簡単で、これより先に解かれるGってどんだけ簡単枠なんだよとビビったな

**仕様書無しさん** · 2024/02/24(土) 23:04:36.57

インコはマス君判定問題も解けないんですかという話

**仕様書無しさん** · 2024/02/24(土) 23:05:47.41

普段のFより簡単かは微妙じゃね？
いつものFの方が本当に考察要素が殆どない典型やるだけ問題置かれてるイメージ(前回とかもそう)

**仕様書無しさん** · 2024/02/24(土) 23:06:03.74

マスくん46分3完かぁ

**仕様書無しさん** · 2024/02/24(土) 23:06:04.76

マスくん46分3完かぁ

**仕様書無しさん** · 2024/02/24(土) 23:07:05.33

流石に色落ちしたら引退する

**仕様書無しさん** · 2024/02/24(土) 23:07:33.64

期待値DP+いもすか遅延か区間和貰うDPでディーラーの期待値を計算(ここまでは自明)
その後勝率を計算する方法の発想(ほぼ自明)
まぁ青diff中位くらいはあるんじゃない？

**仕様書無しさん** · 2024/02/24(土) 23:08:57.70

Dに数学問が置かれてる回は安心感があるな

**仕様書無しさん** · 2024/02/24(土) 23:10:02.27

超既出っぽい見た目してるけど既出じゃないのか?

**仕様書無しさん** · 2024/02/24(土) 23:10:40.73

>>377
D

**仕様書無しさん** · 2024/02/24(土) 23:10:40.80

今日は運が悪かっただけと割り切って次に賭ける

**仕様書無しさん** · 2024/02/24(土) 23:11:06.13

>>374
流石に色落ちはしないと思う

**仕様書無しさん** · 2024/02/24(土) 23:11:08.44

Dの見た目はゆきこっぽい

**仕様書無しさん** · 2024/02/24(土) 23:12:14.09

だから誰でも一瞬で思いつける問題設定だからゆきこっぽいとかですらないだろ
ちょっと上のレスくらい読んでから書き込め

**仕様書無しさん** · 2024/02/24(土) 23:12:56.73

運運運！
環境環境環境！

**仕様書無しさん** · 2024/02/24(土) 23:13:01.15

知るかボケ

**仕様書無しさん** · 2024/02/24(土) 23:13:53.66

Dでキャッキャしてるような寒色インコに酷なことを求めるな

**仕様書無しさん** · 2024/02/24(土) 23:15:28.51

運ゲーつまらない...

**仕様書無しさん** · 2024/02/24(土) 23:17:15.31

Dの0が非本質って騒いでるインコいるけど流石に0含めてるのは意図的だし考察パートの一部だろ(そうでもなければCに置いてもいいレベルで簡単すぎる)

**仕様書無しさん** · 2024/02/24(土) 23:17:26.36

デアスレ終了

**仕様書無しさん** · 2024/02/24(土) 23:17:46.48

一生才能ある分野見つけられずに愚痴り続けて死んでそう

**仕様書無しさん** · 2024/02/24(土) 23:18:07.32

Eの実装が重いと言っているインコが大量発生

**仕様書無しさん** · 2024/02/24(土) 23:18:15.32

Dはマジで同じ問題設定のやつを考えたことあるな
競プロコンテストの問題だったかすら思い出せないが

**仕様書無しさん** · 2024/02/24(土) 23:18:21.57

しょうもない人生せいぜい楽しめよとしか

**仕様書無しさん** · 2024/02/24(土) 23:18:26.98

マスくんer

**仕様書無しさん** · 2024/02/24(土) 23:18:54.30

Eが重いと感じるインコはこどふぉdiv3,4バチャいっぱいやって体力つけましょう

**仕様書無しさん** · 2024/02/24(土) 23:19:46.12

Dって寧ろアレ単体で問題考えるというよりは、問題の一部品として使う程度でしょ

**仕様書無しさん** · 2024/02/24(土) 23:20:17.54

原神にハマれるだけでしょうはある人生なんだよなぁ

**仕様書無しさん** · 2024/02/24(土) 23:20:28.13

E、次に乗るべき電車を求めるパートの1行だけがめんどくさいだけで、実装はほぼただのダイクストラだからむしろ軽いだろ

**仕様書無しさん** · 2024/02/24(土) 23:20:39.67

D、平方数で割りまくること思いつかなかったけど場合分け+ osa_k法使って解けて良かった

**仕様書無しさん** · 2024/02/24(土) 23:21:12.01

Eは実際解いてみたら見た目に反して全然重実装じゃないぞ

**仕様書無しさん** · 2024/02/24(土) 23:21:23.53

過学習すぎるだろ
発想は算数っぽいから中受算数からやり直しなさい

**仕様書無しさん** · 2024/02/24(土) 23:22:01.96

重実装というよりはパラメータ多くてバグってたら怖い感じ(ただのダイクストラやるだけなので)

**仕様書無しさん** · 2024/02/24(土) 23:22:13.70

ドラケン算数が続いてたらなぁ

**仕様書無しさん** · 2024/02/24(土) 23:22:53.94

実質今回のDの発想ってドラケン算数で取り上げられてもおかしくないレベルの中受算数典型＆お手軽テクニックではある

**仕様書無しさん** · 2024/02/24(土) 23:23:25.96

今の頂点と電車に乗る時間からいつまでに電車に乗るか調べる
lとdから何本目か計算、ただしk以下
1本目より後に間に合うなら追加

3行ってとこじゃね？
重実装とは？
1行に全部の計算式詰めれば1行でも行ける

**仕様書無しさん** · 2024/02/24(土) 23:24:15.70

今回のG遅延セグ木だと(多分)無理で双対じゃないと解けない例で良問だな
双対セグ木が遅延セグ木の完全なる下部組織ではないということ

**仕様書無しさん** · 2024/02/24(土) 23:24:38.75

一番つらいところは電車の時刻計算な気がするがそもそもそれは実装とは関係ない

**仕様書無しさん** · 2024/02/24(土) 23:25:09.08

重実装というか、ABC-Eで紙を使ったのは久々だった

**仕様書無しさん** · 2024/02/24(土) 23:25:58.51

やるだけコン

**仕様書無しさん** · 2024/02/24(土) 23:26:29.17

>>404
割り算とかどっちに寄せるかとかk本目以降の電車はない辺りとか後ろから辿る部分とかちょっとバグらせそうなパーツは散らばってるから普段の数分で解けてバグらせようもなさそうなEと比べたらめんどいという話

**仕様書無しさん** · 2024/02/24(土) 23:26:31.55

双対セグ木が遅延セグ木の下部組織じゃない話は既にガイジスレで議論されているな
ガイジスレ既出問出しすぎだろ

**仕様書無しさん** · 2024/02/24(土) 23:27:06.29

インコは過去スレ精進しなさい。

**仕様書無しさん** · 2024/02/24(土) 23:27:40.38

>>409
E面倒くさいという意見は否定してなくて、E重実装という意見を否定しています

**仕様書無しさん** · 2024/02/24(土) 23:28:00.96

遅延させない双対セグ木の存在を初めて知ったな

**仕様書無しさん** · 2024/02/24(土) 23:28:37.72

>>412
そういうことね　確かに重実装という表現は不適切かも

**仕様書無しさん** · 2024/02/24(土) 23:29:25.11

Eにぶたんする方が面倒そう

**仕様書無しさん** · 2024/02/24(土) 23:32:00.90

にぶたんでいけるのか？

**仕様書無しさん** · 2024/02/24(土) 23:32:17.52

終電ってこんな風に求めれば良いのかって解きながら感心したな

**仕様書無しさん** · 2024/02/24(土) 23:32:57.43

Gってオフラインダイコネみたいにセグ木に乗せたあと永続遅延でundoもどきしてもいい？

**仕様書無しさん** · 2024/02/24(土) 23:33:36.53

>>417
これ思った
今まで感覚で電車に乗っていたので

**仕様書無しさん** · 2024/02/24(土) 23:33:52.67

最近の配点バグリちらかしていて全く信頼できない

**仕様書無しさん** · 2024/02/24(土) 23:35:26.81

終電考えるなら目的地から逆算するのは自然な発想でしょ

**仕様書無しさん** · 2024/02/24(土) 23:35:43.64

Eは業プロっぽさある

**仕様書無しさん** · 2024/02/24(土) 23:36:53.16

マスくん、逆からダイクストラをやるところまでは見えてるのに解けなかったのか
根本的に頭悪いんじゃないか

**仕様書無しさん** · 2024/02/24(土) 23:38:59.30

終了1分前に質問に回答される淫夢くんかわいそう

**仕様書無しさん** · 2024/02/24(土) 23:39:17.24

実装ダルそうと思ってもとりあえず手を動かすことが肝要だな

**仕様書無しさん** · 2024/02/24(土) 23:39:19.58

競プロ難しい
やめようかな

**仕様書無しさん** · 2024/02/24(土) 23:40:12.79

せめて人間、最悪インコ大王くらいにはなっておけ
野生に帰るには早すぎる

**仕様書無しさん** · 2024/02/24(土) 23:44:25.14

>>423
それは流石に誰でも見えるだろ…
細かいところをしっかりと詰められるかが問われてる問題だぞ

**仕様書無しさん** · 2024/02/24(土) 23:47:10.69

そいつマスくんerだから気にすんな

**仕様書無しさん** · 2024/02/24(土) 23:47:15.60

爺angryとげんな爺,テンプレート使わないであの速度なのおかしいよ

**仕様書無しさん** · 2024/02/24(土) 23:49:49.50

爺angryG多分一から書いるのに4分とかで通してるの異常すぎ
セグ木コピペしてちょっと弄るくらいならソラで書いた方が早いレベルなんだろうな

**仕様書無しさん** · 2024/02/24(土) 23:50:58.48

俺もセグ木ソラで書けるようになった方がいい？
ちなみにインコ

**仕様書無しさん** · 2024/02/24(土) 23:52:01.35

原理は再帰/非再帰/遅延/双対のいずれも理解してないといずれやられる

**仕様書無しさん** · 2024/02/24(土) 23:52:37.47

かけるとうれしいことはある,例えば今回のようなaclをいじるだけじゃ難しいようなものが簡単に通せるようになるとか，あとは内部構造の理解が深まる(?)とか

**仕様書無しさん** · 2024/02/24(土) 23:53:17.65

げんな爺Fで凡ミスしてるのもったいねえ
それなきゃ1位だったろうに

**仕様書無しさん** · 2024/02/24(土) 23:53:49.27

ジャップに賞金渡ってなくて草

**仕様書無しさん** · 2024/02/24(土) 23:54:23.68

lとdをミスったのか

**仕様書無しさん** · 2024/02/24(土) 23:55:50.66

編集距離1で草

**仕様書無しさん** · 2024/02/24(土) 23:57:23.26

Eって重いっていうか、
１．問題文が読めるか？
２．辺を逆向きにすることを思いつくか？
３．最短距離問題に似ているが、ダイクストラで解けるか？
４．細かいところを詰められるか？
で段階が多くて大変

**仕様書無しさん** · 2024/02/24(土) 23:59:02.51

げんな爺でも6分半かかってるからな