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

■ このスレッドは過去ログ倉庫に格納されています
1デフォルトの名無しさん (ﾜｯﾁｮｲ 1f9f-qCnf)
垢版 |
2021/07/28(水) 21:58:48.02ID:nljYiy+l0
!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
790デフォルトの名無しさん (ﾜｯﾁｮｲ de2a-62hs)
垢版 |
2022/09/14(水) 15:24:09.35ID:9+y+r6nn0
適当なこと言うけど
Sのi番目の文字を変更したとしても、最終的にはSのi番目の文字をTのi番目の文字に合わせないといけないから、
Sのi-1番目までの操作に置き換えられるということじゃないかな

例えば、bookをdeskに合わせるなら、
bookのkを適当にaに変える→booa
でも最終的には最後の文字はkにしないといけない
booaの最後にkを挿入→booak
booakっていうのは、bookのbooの部分にaを挿入したものと考えられる
こういう感じで、結局Sのi-1番目までの操作と考えることができるっていうことだと思う
2022/09/14(水) 15:30:11.95ID:5xlFzeB+0
S[i-1]==S[j-1]で、Sのi文字目かTのj文字目を変更したときに、dp[i][j]<dp[i-1][j-1]とするとdp[i-1][j-1]<dp[i-1][j-1]が導かれるようにできるよ
dp[i-1][j-1]未満の編集距離で揃えるにはSのi文字目かTのj文字目のどちらかを使わなきゃいけないことに注目する
792デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/15(木) 09:32:52.27ID:3elqjdXs0
>>790-791
ありがとうございました。
まだ、よく分からないので、少し質問の仕方を変えてもう一度質問させてください。

以下がなぜなのかが分かりません。
いかにも成り立ちそうですが、証明ができません。

S = 'LOGISTIC'
T = 'ALGORITHM'

(1)
Sの最後の文字CをTの最後の文字Mで置き換える。
Sからその最後の文字を除いた文字列を、Tからその最後の文字を除いた文字列に
最小の手間で編集する。

(2)
Sの最後の文字Cを削除する。
Sからその最後の文字を除いた文字列を、Tに最小の手間で編集する。

(3)
Sの最後の文字Cの後ろに、Tの最後の文字Mを付け加える。
SをTからその最後の文字を除いた文字列に最小の手間で編集する。

(1)、(2)、(3)を実行するのに必要な手間のうち最小の手間が、文字列Sを文字列Tに
編集する最小の手間である。
793デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/15(木) 09:35:19.04ID:3elqjdXs0
間違えました。以下のように訂正します。

S = 'LOGISTIC'
T = 'ALGORITHM'

(1)
Sの最後の文字CをTの最後の文字Mで置き換える。
Sからその最後の文字を除いた文字列を、Tからその最後の文字を除いた文字列に
最小の手間で編集する。

(2)
Sの最後の文字Cを削除する。
Sを、Tに最小の手間で編集する。

(3)
Sの最後の文字Cの後ろに、Tの最後の文字Mを付け加える。
SをTからその最後の文字を除いた文字列に最小の手間で編集する。

(1)、(2)、(3)を実行するのに必要な手間のうち最小の手間が、文字列Sを文字列Tに
編集する最小の手間である。
794デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/15(木) 09:38:28.08ID:3elqjdXs0
また、間違えました。以下のように訂正します。

S = 'LOGISTIC'
T = 'ALGORITHM'

(1)
Sの最後の文字CをTの最後の文字Mで置き換える。
Sからその最後の文字Mを除いた文字列を、Tからその最後の文字Mを除いた文字列に
最小の手間で編集する。

(2)
Sの最後の文字Cを削除する。
Sを、Tに最小の手間で編集する。

(3)
Sの最後の文字Cの後ろに、Tの最後の文字Mを付け加える。
Sからその最後の文字Mを除いた文字列を、Tからその最後の文字Mを除いた文字列に最小の手間で編集する。

(1)、(2)、(3)を実行するのに必要な手間のうち最小の手間が、文字列Sを文字列Tに
編集する最小の手間である。
795デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/15(木) 13:41:42.51ID:3elqjdXs0
SをTに最小の手間で変換するオペレーションが以下の画像の通りだとする。
オペレーションを実行する順序には関係なく、SはTに変換されることに注意する。

imgur.com/GSQfWoU.jpg

(1)Sの最後の文字の右にInsertオペレーションがある場合。

Sの最後の文字の後ろに、Tの最後の文字を付け加える。
Sからその最後の文字を除いた文字列を、Tからその最後の文字を除いた文字列に最小の手間で編集する。

これが(1)の場合に、SをTに変換する最小の編集方法になる。
796デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/15(木) 13:41:55.18ID:3elqjdXs0
(2)Sの最後の文字の右にInsertオペレーションがない場合。

(2-1)Sの最後の文字に行うオペレーションがN（何もしない）の場合。

この場合、Sの最後の文字とTの最後の文字は等しい。
Sからその最後の文字を除いた文字列を、Tからその最後の文字を除いた文字列に最小の手間で編集する。

これが(2-1)の場合に、SをTに変換する最小の編集方法になる。

(2-2)Sの最後の文字に行うオペレーションがD(Delete)の場合。

この場合、Sの最後の文字を削除する。
Sを、Tに最小の手間で編集する。

これが(2-2)の場合に、SをTに変換する最小の編集方法になる。

(2-3)Sの最後の文字に行うオペレーションがS(Substitute)の場合。

この場合、Sの最後の文字をTの最後の文字に置き換える。
Sからその最後の文字を除いた文字列を、Tからその最後の文字を除いた文字列に
最小の手間で編集する。

これが(2-3)の場合に、SをTに変換する最小の編集方法になる。
797デフォルトの名無しさん (ﾜｯﾁｮｲ 6a55-V+uT)
垢版 |
2022/09/15(木) 13:43:21.05ID:3elqjdXs0
こう考えたのですが、これでいいでしょうか？
2022/09/15(木) 14:20:18.89ID:2rpOawCB0
多分、dp[i]を、i番目まで揃えたときの最小手順数だって定義してると思う
その次のインデックスの文字を揃えるために出来ることがその3パターンしかなければ、そうなんじゃないかなぁ
dpを更新したときに、定義が崩れてしまわないか？を集中して考えてみると良いと思う
2022/09/17(土) 14:19:59.56ID:ChhZpwg90
最近競技プロ出来てねー
まぁ2年くらいやったし飽きたのかも
800デフォルトの名無しさん (ﾜｯﾁｮｲ 5701-nNgT)
垢版 |
2022/09/20(火) 09:38:15.86ID:l9naZzzk0
パイザってサイトに『エンジニア騎士とクエリの魔女』の『暗黒の地』って
競技プログラミング風味のものがあるんだよ。まあまあ面白くて
これで12位になったので、ソース公開するね。
https://paiza.io/projects/Me-9l8aRopclovpRhczITg
ソースを読んだ感想を書いてくれたりしてくれると嬉しいです。みんなもやってみよう
2022/09/20(火) 11:41:19.73ID:Qcy/onU00
いいね！
すごいね！
2022/09/20(火) 13:54:44.15ID:gUImHuHP0
この問題わかんね
https://twitter.com/SSRS_cp/status/1571996174604963840
https://twitter.com/5chan_nel (5ch newer account)
2022/09/20(火) 14:02:43.97ID:gUImHuHP0
平方分割すればできるのはわかるけど、想定解はそうじゃないっぽいし
2022/09/20(火) 14:51:16.41ID:Y9OiSWpN0
Lだけの話に限定するけど、
Lの効果をインデックス毎に保管しておいて、（入力例１なら[-1, -2, 2, 0, 1]）
それのセグメント木を作れば区間最小値をlogNで取り出せるようになるからいけるんちゃうか？
2022/09/20(火) 16:42:42.75ID:fSXnXfcH0
耳DPをセグ木に乗せるだけやろ
2022/09/20(火) 17:00:13.31ID:gUImHuHP0
>>804
問題は、Rも同じようにインデックス毎に効果を保管するとして、区間内で和が最大になるLの効果とRの効果のペア（Lの効果のインデックスよりRの効果のインデックスの方が右になければならない）をO(1)とかO(logN)で取り出さなきゃいけないことだと思うけど、そこが難しくないか？

>>805
耳DPというと、左の区間外、Lの区間、元の値をそのまま使う区間、Rの区間、右の区間外みたいな感じの状態の持ち方？
2022/09/20(火) 17:17:04.14ID:Y9OiSWpN0
>>806
たし蟹
ぱっと考えただけだとペア探しにO(N)かかってまう
ちょっと分からんわ
2022/09/20(火) 18:28:08.02ID:yGxPr74E0
まずaについて、各項の隙間ごとにLはその左でRはその右にあるような置き換え方での和の最小値を求めておいて、区間が限られたらその区間にある隙間に対して区間minして端の分を補正したらいいんじゃないの
2022/09/20(火) 18:44:31.27ID:R7N7Rzx3r
うんち
2022/09/20(火) 19:40:54.03ID:gUImHuHP0
>>808
なるほど、と思ったけど、
N=4
A=[0,1010,1010,0]
L=1000
R=1000
Q=1
l,r=1,3
みたいなときに厳しそう
2022/09/20(火) 20:06:23.92ID:yGxPr74E0
>>810
めちゃくちゃ嘘だったわ
2022/09/20(火) 20:08:23.68ID:3RVLul1m0
普通にx毎に最小になるyを取れるようにする方針だけど
それだと幅*Qぐらいだから多分無理なので改良として
セグツリーかなんかで[x,..)の領域に対して一発でy取れるようにすりゃいんじゃねって思った
ちなワイ茶色
2022/09/20(火) 21:29:32.52ID:Y9OiSWpN0
超思いつきだけどさ、
L<Rの場合、Lのテリトリーを譲ってまでRの幅を広げる必要はない気がするんだよな
だからLについては貪欲に最小拾っていいとかないかな？
2022/09/20(火) 22:04:05.16ID:6eFEjyRr0
耳DPのトロピカル行列をセグ木に乗っけて終わりとちゃうんか
2022/09/20(火) 22:05:42.62ID:6eFEjyRr0
全区間についての答えの和とかは解けんのかな
オーバーフローはないもんとして
2022/09/20(火) 22:19:34.98ID:gUImHuHP0
耳DPの遷移を表すトロピカル行列が
L ∞ ∞
A_i A_i ∞
R R R
になってて、積についてモノイドになってるからセグ木に乗る
区間積求めてあとは(0,∞,∞)^tに作用させればおｋってこと？
2022/09/20(火) 22:21:34.19ID:gUImHuHP0
>>813
なんかこれはこれで正当化できそうな雰囲気がある
2022/09/20(火) 22:25:23.85ID:gUImHuHP0
結局正解っぽいやつについて自力で全然思いつかなかったの悲しい
2022/09/20(火) 23:18:52.20ID:gUImHuHP0
>>800
paizaってOpenCV使ったりするような問題出るんだ
2022/09/21(水) 00:43:34.61ID:x1slIPpsM
行列積の定数倍が重いせいで平方分割落とす制約にできないのか
2022/09/21(水) 11:31:22.73ID:KfFuyi/HM
情報の保持って観点じゃトロピカル行列は
A_i A_i
R R
の左下部分だけで十分ってことか
https://twitter.com/SSRS_cp/status/1572362117432643586?t=_MoRQwYnYHKZd2peSTfpbQ&s=19
https://twitter.com/5chan_nel (5ch newer account)
2022/09/21(水) 11:32:37.83ID:KfFuyi/HM
あと区間長さえ保持しとけば
823デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM8f-nNgT)
垢版 |
2022/09/21(水) 12:17:44.87ID:qEUpkz9TM
>>819
あ、opencasは私個人的な
ローカル環境での
動作確認、デバッグ用です
そういうのつけとけば
参加してくれる人いるかな
的な意図もあります
824デフォルトの名無しさん (ｱｳｱｳｳｰ Sa5b-lIjq)
垢版 |
2022/09/21(水) 16:22:14.70ID:AliPmZ5ga
ふつうにLとの差分の累積和とって右から全探索でいいんじゃないのか？
2022/09/21(水) 18:13:16.60ID:+9EfOb1n0
N,Q≦10^5の制約だけど、それは2secで通る？
826デフォルトの名無しさん (ｱｳｱｳｳｰ Sa5b-lIjq)
垢版 |
2022/09/21(水) 20:13:31.40ID:k2jdRmOoa
Nだから普通に通るよ
2022/09/21(水) 20:48:04.88ID:bmvBppJjM
具体的なやり方が読み解けないけどクエリごとに全探索したらO(NQ)なのでは？
2022/09/21(水) 20:52:43.66ID:bmvBppJjM
もしかして、元々の問題ABC263Dの解法の話してる？
2022/09/21(水) 21:08:22.89ID:bmvBppJjM
昔のadminがりんごさんだったころのSRMってAGCとかに役に立つ？
830デフォルトの名無しさん (ﾜｯﾁｮｲ bfd7-lIjq)
垢版 |
2022/09/21(水) 22:35:20.54ID:JxZ0RmNU0
>>828
ごめん話題変わってた？

左からLとの差分の累積和とって、左からi番目までで1番値が大きいやつのインデックスメモっておくのがO(N)
右から見てってiより右側はRにして、iより左側でLにするべき境目はさっき求めたからiの全探索でO(N)でいける認識

説明やばいけど勘弁して
2022/09/22(木) 00:37:51.08ID:7XNeWjKf0
ABC263Dの解法としてはそれでOK
リンクされたツイートではさらに、元々の数列のうち区間[l,r)の部分に限った数列について元々の問題を解く×Qって設定になっていた
その解き方だとO(NQ)でTLEするので、これがちょっと難しかった(もう解法は発表されたけど)
2022/09/22(木) 01:37:50.90ID:LfyHnz2g0
正直、4つ持つことになんの意味があってどう嬉しいのか全く分からんぞい
耳dpってやつなの？
2022/09/22(木) 03:17:37.64ID:FFFEjz5/0
4つ情報を持ってないと、モノイドにする（≒結合則を成り立たせる）上で情報が足りないからセグ木に乗らない
このモノイドが代数的な言葉で言えばトロピカル行列に対応している
ちなみにこのトロピカル行列は耳DPの遷移だから、そっちから考えても同等の解答に行き着く的な感じ
明日気が向いたらこの辺ちゃんと書く
何か言葉は仰々しいけど別にトロピカル代数の知識なくても、上書き区間左側確定 T/F 上書き区間右側確定 T/Fで値持って区間をくっつけること考えたらどういう演算をしたらいいかは発想できると思う
2022/09/22(木) 03:22:21.63ID:FFFEjz5/0
自分の理解だとさらに区間の長さも必要そうだから厳密には必要なのは5つの情報かな？
2022/09/22(木) 11:18:12.70ID:c1NDWA0LM
半環上の正方行列が積が結合則満たすのって実正方行列での証明考えれば自明だけど、それが行列積だと分かってない状況だとかなり直観的に分かりづらいよな
そもそも行列積自体、初見で線形写像の幾何学的な話もなしだと結合則が成り立つと見抜くのが無理そうな意味不明な演算に見えるし
836デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/24(土) 18:24:44.81ID:nZKOKQNY0
大槻の本に、比較によってソートするアルゴリズムの最悪計算量は、 Ω(n * log(n)) であると書いてあります。

最善の計算量が O(n * log(n)) よりも良いようなものって存在しますか？
2022/09/24(土) 18:33:53.75ID:hL268OjV0
nがあります
2022/09/24(土) 18:36:10.29ID:ewV+cEv/0
ボゴソートは最良計算時間nですよ
839デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/24(土) 18:38:34.03ID:nZKOKQNY0
例を挙げてください。
2022/09/24(土) 19:08:37.47ID:B/S/upiL0
最善って意味だと挿入ソートはO(N)
2022/09/24(土) 19:21:32.49ID:lQxqE4zm0
バブルソートはソート済みの列に対して O(n)
842デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/24(土) 19:24:43.12ID:nZKOKQNY0
>>837-838,841

ありがとうございました。確かにバブルソートはそうですね。でもマージソートとか最善の計算量と最悪の計算量が同じ計算量のものが多いですね。
2022/09/24(土) 22:42:30.99ID:JAEDuJ+F0
A問題、A問題の難易度じゃないだろ
844デフォルトの名無しさん (ﾜｯﾁｮｲ 9e71-mIyF)
垢版 |
2022/09/24(土) 22:53:45.20ID:cuZGjTPy0
Aこの難易度でも良いけど、ビギナーコンテストなんだから9割くらいが解けるDくらいまでにすべき、１０問は多すぎ
Dも昔は愚直にやって通るくらいの難易度だった気が
2022/09/24(土) 22:56:24.67ID:XN000lpY0
D問題が greedy じゃダメな理由がわからん……
解説に反例があるのは見たけど納得できない
2022/09/24(土) 23:04:41.84ID:Cc5Uw0Zt0
確かに直感的にはDはgreedyでもよさそうだけど、ナップサック法よろしく、整数が絡むと途端に直感greedyが壊れる
ABC-DからABC-Fぐらいの問題だとコンテスト中はgreedyがダメな理由を考えるより簡単に正当性を示せるDPを思いつくことを意識した方がいい
2022/09/24(土) 23:07:25.27ID:Cc5Uw0Zt0
反例に関して言えば2個取るという選択肢がないのが効いてる
2022/09/24(土) 23:16:48.66ID:Cc5Uw0Zt0
ExのFPS解面白い
確かにDP遷移で途中\sum_n {n a_n}みたいな形の式が出てきてめんどくさそうと思ったけど、こういうのはFPSならただの微分か
849デフォルトの名無しさん (ﾜｯﾁｮｲ 9e71-mIyF)
垢版 |
2022/09/25(日) 01:57:37.46ID:eKbCKhXa0
Dが水という事は、ビギナーコンテストだからC問題までの３問で良いじゃん
2022/09/25(日) 02:18:02.40ID:qNDnNxHD0
8問ABCは言うなればCodeForces Div. 2 + Div. 3 + Div. 4みたいな状態だから、Div. 3単独開催やDiv. 4単独開催が欲しいって話は分からなくもない
4問時代のABCがまさにそんな感じだったけど
コドフォが最近Div. 4増やしてるし、AtCoderも現ABCの下の区分のコンテスト作っていいと思うけどね
2022/09/25(日) 02:25:38.65ID:qNDnNxHD0
自分の感覚だと
CF Global = AC AGC
CF Div. 1 = AC ARC
CF Div. 2 = AC ABC-C〜Ex
CF Div. 3 = AC ABC-C〜F
CF Div. 4 = AC ABC-A〜D
ぐらいのイメージなんだけど、合ってる？
そんなコドフォ出てないから詳しくないけど、Div. 2以下の階級を全部ABCがカバーしている状態ではあるのは確かだと思っている
852デフォルトの名無しさん (ｻｻｸｯﾃﾛﾚ Sp47-Rupp)
垢版 |
2022/09/25(日) 09:32:03.84ID:HBsCeuHap
昨日のEってどういう思考過程をすれば二分探索が思いつけるんだ
言われたらそれはそうってなるけど
2022/09/25(日) 11:07:00.84ID:gbe15JeH0
>>845
肉を切らせて骨を断つ
無傷でいようとすると勝てないってわけよ
2022/09/25(日) 12:13:04.55ID:ODs0tVKRM
昨日のEは別に二分探索なんか使わなくても素直なやり方で解ける気がするが、判定問題が簡単で単調性がありそうならとりあえず二分探索試して損はない
2022/09/25(日) 12:15:43.34ID:ODs0tVKRM
ぐろふぉはAGCより取っつきやすい気がするな
2022/09/25(日) 12:46:21.45ID:ODs0tVKRM
Twitterみた感じEのO(NlogN)解は重実装扱いなのか
個人的には二分探索解と大して変わらんやろと思ったが
857デフォルトの名無しさん (ｻｻｸｯﾃﾛﾚ Sp47-Rupp)
垢版 |
2022/09/25(日) 13:15:51.54ID:JpevNCD6p
愚直にシミュレーションしようとしたらバグらせまくったから二分探索の発想が早い段階で思い浮かぶように出来たら便利だなって
2022/09/25(日) 22:01:15.20ID:IPCnGxrw0
端数は後でなんとかすることにしてだいたい何周すればいいか知りたくなって、周回数を決め打ちすれば何個減るかはO(N)でわかるから二分探索すれば良さそうとなる
2022/09/25(日) 23:58:46.25ID:5HnvgjcS0
ユーザー解説にO(NlogN)の実装があるから見たけど、そんな重実装かこれ？
二分探索より楽に見えるんだが
2022/09/26(月) 09:01:27.51ID:cpj0q9yVM
本来二分探索の実装ってかなりバグらせやすい方だと思うんだが、めぐる式で教育が行き届いている？のか、最近はみんな脳死で書ける印象
O(NlogN)解は量や内容は大したことないがアドホックなのが効いてんのかな
2022/09/26(月) 10:32:20.32ID:ncSKb+wV0
にぶたんの最後のシメを考えるのが苦手すぎる…
LRがどうなったら終わりで、どっちに答えが入ってるのか分からなくなるよ
2022/09/26(月) 11:47:57.47ID:ut+E4sGm0
そこでめぐる式よ 継続条件はwhile(abs(ok-ng) > 1)で答えはokに入る
2022/09/26(月) 12:49:10.56ID:QsR2IXV50
その式だけだとokがleftかrightか分からん
2022/09/26(月) 12:53:59.99ID:7xAfjatjM
別にleftでもrightでもどっちでもいいからバグらないと言える
位置関係より意味内容に忠実な表記
2022/09/26(月) 14:00:18.97ID:i/jndsoD0
ok、ngとかいいつつちゃんと定義域を渡さないといけないところらへんで、慣れてないひとは混乱するんだろうと思う
ok、ngではなくて、明確に定義域を指定するようなインタフェースに整えてあげると初学者には優しいでしょう

おれはいつも混乱しないように詳細を積めてから実装してるからok、ngなんて使わずhi、loで書いてるけど
2022/09/26(月) 14:31:20.74ID:QwvWOyok0
ok(ng)の初期値は条件が真(偽)だとわかっているところ
もしくは定義域の一個外にするけど
そんなに混乱するか？
2022/09/26(月) 14:51:56.76ID:i/jndsoD0
おれはしないから予想してるだけ
868デフォルトの名無しさん (ﾜｯﾁｮｲ 9210-A/T8)
垢版 |
2022/09/26(月) 15:55:48.24ID:50Eh55hb0
自分は二分探索、毎回コピペしてる
値が小さい方から大きい方にかけて、条件式がTrue, True, ..., False, Falseになるのと
False, False, ..., True, Trueになる2パターン用意しといて毎回コピペしてる
869デフォルトの名無しさん (ﾜｯﾁｮｲ 9210-A/T8)
垢版 |
2022/09/26(月) 16:10:31.34ID:50Eh55hb0
ん、めぐる式二分探索って、上の2パターンを一般化しますよっていう話か...
3年半も競プロしてんのに初めて知ったよ...
2022/09/26(月) 17:20:22.65ID:mM+PT8Od0
別にlo, hiやleft, rightの実装で全く困ってなければ知らなくてもいいと思う
位置と判定、境界を一緒に考えると頭がこんがらがる初心者にとって、めぐる式は判定関数とok,ngの初期値さえ与えておけば二分探索部分のコードは位置関係すら考えず貼るだけなので楽
2022/09/27(火) 00:33:47.81ID:OQZ1tOOg0
LRをどっちもokにしちゃうと無限ループしちゃうんだよな
まったくもう
2022/09/27(火) 00:51:50.39ID:ZwmfNOl50
あー、そういえば、めぐる式で一番重要なノウハウは、[left, right)の半開区間にすると処理が簡単、ってことだと思うわ

閉区間にすると考えることもコードも増えてキツイと思うんだけど、外人のコードだとかなり見かける
こないだのABC1位のひとでもこれでやってるんだよな
if check(mid)
l = mid + 1
else
r = mid - 1
2022/09/27(火) 01:56:33.69ID:f9wenpM60
中国って割と1-based・閉区間の派閥がいるイメージだわ
2022/09/27(火) 07:38:03.73ID:nRLJF7B50
取り敢えず区間扱うときは全て半壊区間が安定してるなぁ
2022/09/27(火) 10:17:28.55ID:RK9MOCkIM
そのあたりは情報処理能力やライブラリ化でごり押せるから、上級者でも筋の悪い実装方針でやってたりすることがあるイメージ
特に軽実装のAtCoderでは、まず算数パズルができるということが何よりも大事だから
876デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/27(火) 15:17:24.67ID:j2LDQh400
DAG上の最短路問題について普通のアルゴリズムとデータ構造の本には載っていません。
これはトポロジカルソート＋動的計画法によって、最短経路の求め方が自明だという考えからでしょうか？
2022/09/27(火) 15:31:56.76ID:ZwmfNOl50
さあ、ダイクストラでも大体十分だったりするから需要ないんじゃない？
2022/09/27(火) 16:05:50.65ID:RqBRw8Xlr
うんち
879デフォルトの名無しさん (ﾌﾞｰｲﾓ MM32-QTvv)
垢版 |
2022/09/28(水) 13:02:21.64ID:F+G1dH1CM
ABC263のDやってるんだけど、
kyopro_friendsさんの解説に出てくる累積minってググっても出ないんだけど、
nok0さんの解説のf(k+1)=min(f(k)+A[k+1], L*(k+1))のこと？
累積和使って最小値求めると、全体でO(N^2)になっちゃいますよね
2022/09/28(水) 13:33:58.07ID:E29MaAWV0
>>879
そのf(i)の意味を勘違いしてるかも。
例えばf(5)ならば、

①A1+A2+A3+A4+A5
②L+A2+A3+A4+A5
③L+L+A3+A4+A5
④L+L+L+A4+A5
⑤L+L+L+L+A5
⑥L+L+L+L+L

この６パターンの内の最小値って意味だよ
881デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 15:59:44.30ID:B1p+YPuG0
AtCoder Problemsが独自に算出したという「difficulty」ってどこで見れるんですか？
882デフォルトの名無しさん (ｱｳｱｳｳｰ Sa43-q+3U)
垢版 |
2022/09/28(水) 16:24:44.67ID:cIcLbxtta
AtCoder Problemsで見れます
883デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 16:38:42.88ID:B1p+YPuG0
>>882
Show DifficultyをONにしても表示されません。
884デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 16:47:43.15ID:B1p+YPuG0
大槻のAtCoder入門を図書館から借りてきましたが、やさしすぎますね。
2022/09/28(水) 17:47:31.56ID:ZeFU5MB7M
>>883
左の円の色とか円の中のゲージがdifficulty
886デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 18:08:29.44ID:B1p+YPuG0
>>885
ありがとうございました。マウスのポインターを円の上に持っていったら表示されました。
887デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/28(水) 21:41:22.84ID:B1p+YPuG0
大槻のアルゴリズムとデータ構造の本に、クラスカルのアルゴリズムの計算量が、
O(|E| * log(|V|)) であると書いてあります。

なぜ、 O(|E| * log(|E|)) と書かないのですか？
2022/09/28(水) 22:01:47.27ID:7KJ1BqpF0
文脈が分からないけど、単純グラフって仮定があるんなら|V|^2>|E|だからってことで深い意味はないと思う
強いて言えば|V|の方がlogのお得感が出るとか？
889デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/30(金) 12:34:13.21ID:aXocYaHs0
大槻のAtCoder入門という本に、頂点の数 N、辺の数 Mのグラフの構造の入力の受け取る処理に
O(N + M) の計算量が必要だと書いてあります。

O(M) が正しいと思いますが、どうですか？
890デフォルトの名無しさん (ﾜｯﾁｮｲ 9255-JEMU)
垢版 |
2022/09/30(金) 12:34:55.30ID:aXocYaHs0
>>888
ありがとうございました。
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況