競技プログラミング総合スレ 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

2022/09/11(日) 00:49:02.92

上位者は本番中に問題を解ける思考モードへの入り方がうまいっぽい
chokudaiか誰だったか忘れたけど、本番じゃないとAGCの問題解くの難しいって言ってたな
かなりメンタルが影響するらしい

2022/09/11(日) 00:51:45.15

数オリで中国チームが全員満点って話あって、情オリ見てみたけどこっちでも上位4は中国チームのメンバーで独占してるんだなあ・・・
https://stats.ioinformatics.org/results/2022

と思ってもっとよく見てみたら6位まで全部中国人やんけ

2022/09/11(日) 11:51:48.46

>>737
Exというのはどの問題のことでしょうか？

2022/09/11(日) 12:15:21.09

>>747
ABCの八問目で一番最後の問題
昔はHだった

2022/09/11(日) 12:33:26.32

>>748
ありがとうございました。

『プログラミングコンテストチャレンジブック第2版』のp.325に、

「したがって、先ほどの長方形を左半分と右半分の一辺dの正方形に分けると、それぞれの正方形には、
点はたかだか3個しか含まれません。」

と書いてあるのですが、たかだか2個ではないですか？
3個になる例はありますか？

2022/09/11(日) 12:37:14.74

3点となる例がわかりました。
でも4点の例がないことはどうやって証明するのでしょうか？
直感的には3点であろうと思いますが。

2022/09/11(日) 12:39:35.27

>>743
競プロ初心者だけどC、40分くらい考えた末解けて自分天才だろと思ったのに茶diffだったんだな
みんな頭いいな

2022/09/11(日) 12:40:58.84

初心者で今回のCが解けるなら大したもんだよ

2022/09/11(日) 14:17:40.92

>>750
コンテスト中だと直感で済ませちゃうけど、ちゃんと証明書こうとするとめんどいやつだ

全ての点対の距離がd以上であるような4点が正方形領域内にあると仮定する。
この四点をA,B,C,Dとし、四角形ABCDを考える。
(1)全ての頂点の角度が180°未満のとき
角度が90°以上である頂点が存在、これをAとしても一般性を失わない。
ここで余弦定理より、BD^2 = AB^2 + AD^2 - 2 AB AD cos∠BAD >= AB^2 + AD^2 >= 2 d^2
よって、BD >= √2d
(2)ある頂点の角度が180°以上のとき
角度が180°以上である頂点をAとしても一般性を失わない。
ここで、∠BAC+∠DAC>=180°なので∠BACと∠DACのいずれかは90°以上。
∠BACを90°以上としても一般性を失わない。
(1)と同様の議論により、BC >= √2d

正方形領域内の点対距離は√2d未満（座標計算普通にやれば示せると思う）
(1),(2)のいずれの場合においても矛盾が生じる。
（証明終）

2022/09/11(日) 14:26:08.97

あ、(1)も(2)も不等式評価で角度が180°以下であることを使ってるけど、ちゃんと書いてないからキモい雰囲気の証明になってるな

2022/09/11(日) 15:12:26.47

凸包の最遠点対という特徴量、いかにも重要そうだけどあまり競プロで使った覚えがない
ABC234Exなんかは最近点対問題の解法と似た発想かもしれない、さすがにABC234Exの方が難しいけど

2022/09/11(日) 15:27:05.90

本質は無なので無料です

2022/09/11(日) 15:46:11.70

逆に最遠点対どうやってNlogNで求めるんだっけって思ったが、凸包求めてキャリパー法でくるくるか
幾何系はド典型でも全然頭に定着しない

2022/09/11(日) 16:55:39.75

昨日のABC、Dの実装でバグらせる予感しかしなかったからEから解いて何とかギリギリ解けたけど難易度E>Fだったんだな
F典型って聞いたけど青くらいまで行けば典型に見えるんだろうかたしかに取り組みやすそうな問題ではあったけど

2022/09/11(日) 17:29:18.43

>>753
証明ありがとうございました．
うまい証明ですね．

2022/09/11(日) 17:37:25.16

>>751
今，解こうとしていますが，難しいですね．
素朴な方法だとΘ(N^2)ですね．
回転前の喜ぶ人の人数から，回転後の喜ぶ人の人数が簡単に計算できないかと考えているのですが，うまくいきません．

2022/09/11(日) 18:18:32.35

>>751
幅3のパルス波が押し寄せてくるイメージを思いつきました．
なんとなく解けるような気がします．

2022/09/11(日) 18:57:12.47

>>751

半日かかりましたが，Θ(N)のアルゴリズムを作ってパスしました．
これじゃ，コンテストでいい成績は残せませんね．

2022/09/11(日) 20:29:08.05

ARC出ません

2022/09/11(日) 23:13:18.91

E問題解きたかったなあ…

2022/09/11(日) 23:24:22.70

最終的にはわからない問題を考え続けるのが一番の練習法らしいから、解説を見ないで解く体力が長い目で見て実力に寄与する気がするし、ABC-Cを半日考えて解くのは上等
ただ、ABCだと知識ゲーの要素があるから、最初のうちは解説見た方がサクサクレートが上がる場合もあるし、悩みどころだ

2022/09/12(月) 07:10:41.31

「Closest pair of points」を求めるアルゴリズムについてですが，『プログラミングコンテストチャレンジブック第2版』の
説明だと説明が全く不足しています．

この本を褒める人がいますが，信じられません．
確かに他に少し高度なこの類の本がないというのは事実だと思いますが．

CLRSの計算幾何学の章に非常に詳しく解説が書いてありますので，そちらを読もうと思います．

2022/09/12(月) 07:12:15.09

『プログラミングコンテストチャレンジブック第2版』ですが，完全な解説ではなく，スケッチ程度の説明集だと
思います．

ネット上の解説などもそのようなものがほとんどだと思います．

2022/09/12(月) 07:57:57.20

そうなんだ

2022/09/12(月) 11:21:41.15

4点の証明よりめんどい行間ある？って思ったけどマージソートの部分か
x座標で点集合を分けたあと、各ステップでx座標的に隣接する点集合を合わせることを繰り返すわけだが、そこでマージソートの要領でy座標をソートすることで、時間計算量を増やさずにy座標のソートができる
ある程度のレベルの学術書で単体で行間埋められる本の方が珍しいし、別に行間だらけだから良書じゃないなんてことはないと思うがな

2022/09/12(月) 17:30:34.33

>>769
確かに有益な本だとは思うのですが，もう少し解説が丁寧だといいなと思います．
完全に理解するために，ソースコードに頼ることが非常に多いので．

何かおすすめのAtCoderの問題はありますか？
難しすぎると解けないので，初心者でも解けるくらいで面白い問題が希望です．

2022/09/12(月) 18:09:25.90

>>770
このサイトはAtCoder Problemsといって、各問題のdifficultyという数値を見ることができる
https://kenkoooo.com/atcoder#/table/

difficultyとはなにかと言うと、半分ぐらいの確率でその問題を解けるであろう人のレートを推定したもの
ここでdifficultyの二分探索でもすれば自ずと丁度いいぐらいのところに行きつくと思う
基本的には自分のレートと同じか一色上ぐらいがやってて楽しい
初心者でプログラミング自体はできるんなら、最初はABC-C、ARC-Aぐらいの問題が丁度いいレベルと思う
面白さについて言えばAtCoderの問題は大体パズル的には面白いはず、ただそこも好みだな
高度な知識をたくさん使いたいんならCodeForcesの方が面白いかもしれない

2022/09/12(月) 18:15:28.92

>>771

詳しく丁寧にありがとうございました．

時間をかけて解いていきたいと思います．

2022/09/12(月) 18:20:46.33

蟻本が解説に関して親切設計な本ではないのは確か
今は蟻本よりもっと初学者向けの競プロ本がたくさんあるから、その中から選ぶのも手ではある
最近は鉄則本なんていうのも出て、それも蟻本に比べたら多分初学者向け
https://kato-hiro.github.io/AtCoderClans/books/

ただ厳密数学的な意味で丁寧な本ってあるんか？自分は蟻本以外読んだことないからよくわからん

2022/09/12(月) 18:38:46.03

>>773
リンクありがとうございました．

2022/09/13(火) 06:55:02.21

こどふぉで自分のレートのdifficultyの問題をずーっとやってるんだけど、
簡単に解けるのと全然歯が立たないのがある…

2022/09/13(火) 19:26:09.73

外国人と日本人で結構な得意な問題が違う気がする

2022/09/14(水) 09:18:47.48

github.com/drken1215/book_algorithm_solution/blob/master/solutions/chap04.md

この4.6のコードですが、本当にO(N*W)ですか？

ボトムアップ型の動的計画法がO(N*W)というのは分かりますが、4.6は違うような気がします。

2022/09/14(水) 09:24:01.59

>>777
これは、部分和問題のコードのメモ化再帰のコードです。

2022/09/14(水) 11:19:03.17

ざっと見た感じはO(NW)で合ってそう

2022/09/14(水) 11:35:22.59

引数のwが負になりうる実装で、そもそも壊れてそう

2022/09/14(水) 11:39:04.72

issue 立ってるけど放置されてるな、やる気はその程度か

2022/09/14(水) 13:32:56.43

文字列の編集距離について質問です。
S、Tを文字列とする。
dp[i][j]をSの最初のi文字からなる文字列とTの最初のj文字からなる文字列の間の編集距離とする。

■変更操作（Sのi文字目とTのj文字目とを対応させる）：
S[i-1]==T[j-1]のとき：コストを増やさずに済みますので
chmin(dp[i][j], dp[i-1][j-1])
です。
S[i-1]!=T[j-1]のとき：変更操作が必要ですので
chmin(dp[i][j], dp[i-1][j-1]+1)
です。
■削除操作（Sのi文字目を削除）：
Sのi文字目を削除する操作を行いますので
chmin(dp[i][j], dp[i-1][j]+1);
です。
挿入操作（Tのj文字目を削除）：
Tのj文字目を削除する操作を行いますので
chmin(dp[i][j], dp[i][j-1]+1)
です。

2022/09/14(水) 13:34:32.86

「S[i-1]==T[j-1]のとき」と書いてありますが、これは
「S[i]==T[j]のとき」が正しいというわけではないですか？

2022/09/14(水) 13:34:44.34

>>779-781

ご回答ありがとうございます。

2022/09/14(水) 13:36:39.23

>>782
は『問題解決力を鍛える!アルゴリズムとデータ構造』という本に書いてある解説です。

2022/09/14(水) 13:38:36.60

配列は0始まりなのでこれで間違っていませんね。

2022/09/14(水) 13:44:17.21

>>782

S[i-1]==T[j-1]のとき：コストを増やさずに済みますので
chmin(dp[i][j], dp[i-1][j-1])
です。

これをSの最初のi文字からなる文字列を編集により、Tの最初のj文字からなる文字列に最小の手間で
変更するには、Sの最初のi-1文字からなる文字列を編集により、Tの最初のj-1文字からなる文字列に最小の手間で
変更すればいいということを言いたいのだと解釈しました。

Sのi番目の文字を変更したとしてもトータルの編集の手間が少なくなることはないというのは証明が必要ではないでしょうか？

2022/09/14(水) 13:46:31.88

>>782

の他のところについても同様の疑問があります。

2022/09/14(水) 15:14:15.25

そうなんだ

2022/09/14(水) 15:24:09.35

適当なこと言うけど
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.95

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文字目のどちらかを使わなきゃいけないことに注目する

2022/09/15(木) 09:32:52.27

>>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に
編集する最小の手間である。

2022/09/15(木) 09:35:19.04

間違えました。以下のように訂正します。

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に
編集する最小の手間である。

2022/09/15(木) 09:38:28.08

また、間違えました。以下のように訂正します。

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に
編集する最小の手間である。

2022/09/15(木) 13:41:42.51

SをTに最小の手間で変換するオペレーションが以下の画像の通りだとする。
オペレーションを実行する順序には関係なく、SはTに変換されることに注意する。

imgur.com/GSQfWoU.jpg

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

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

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

2022/09/15(木) 13:41:55.18

(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に変換する最小の編集方法になる。

2022/09/15(木) 13:43:21.05

こう考えたのですが、これでいいでしょうか？

2022/09/15(木) 14:20:18.89

多分、dp[i]を、i番目まで揃えたときの最小手順数だって定義してると思う
その次のインデックスの文字を揃えるために出来ることがその3パターンしかなければ、そうなんじゃないかなぁ
dpを更新したときに、定義が崩れてしまわないか？を集中して考えてみると良いと思う

2022/09/17(土) 14:19:59.56

最近競技プロ出来てねー
まぁ2年くらいやったし飽きたのかも

2022/09/20(火) 09:38:15.86

パイザってサイトに『エンジニア騎士とクエリの魔女』の『暗黒の地』って
競技プログラミング風味のものがあるんだよ。まあまあ面白くて
これで12位になったので、ソース公開するね。
https://paiza.io/projects/Me-9l8aRopclovpRhczITg
ソースを読んだ感想を書いてくれたりしてくれると嬉しいです。みんなもやってみよう

2022/09/20(火) 11:41:19.73

いいね！
すごいね！

2022/09/20(火) 13:54:44.15

この問題わかんね
https://twitter.com/SSRS_cp/status/1571996174604963840
https://twitter.com/5chan_nel (5ch newer account)

2022/09/20(火) 14:02:43.97

平方分割すればできるのはわかるけど、想定解はそうじゃないっぽいし

2022/09/20(火) 14:51:16.41

Lだけの話に限定するけど、
Lの効果をインデックス毎に保管しておいて、（入力例１なら[-1, -2, 2, 0, 1]）
それのセグメント木を作れば区間最小値をlogNで取り出せるようになるからいけるんちゃうか？

2022/09/20(火) 16:42:42.75

耳DPをセグ木に乗せるだけやろ

2022/09/20(火) 17:00:13.31

>>804
問題は、Rも同じようにインデックス毎に効果を保管するとして、区間内で和が最大になるLの効果とRの効果のペア（Lの効果のインデックスよりRの効果のインデックスの方が右になければならない）をO(1)とかO(logN)で取り出さなきゃいけないことだと思うけど、そこが難しくないか？

>>805
耳DPというと、左の区間外、Lの区間、元の値をそのまま使う区間、Rの区間、右の区間外みたいな感じの状態の持ち方？

2022/09/20(火) 17:17:04.14

>>806
たし蟹
ぱっと考えただけだとペア探しにO(N)かかってまう
ちょっと分からんわ

2022/09/20(火) 18:28:08.02

まずaについて、各項の隙間ごとにLはその左でRはその右にあるような置き換え方での和の最小値を求めておいて、区間が限られたらその区間にある隙間に対して区間minして端の分を補正したらいいんじゃないの

2022/09/20(火) 18:44:31.27

うんち

2022/09/20(火) 19:40:54.03

>>808
なるほど、と思ったけど、
N=4
A=[0,1010,1010,0]
L=1000
R=1000
Q=1
l,r=1,3
みたいなときに厳しそう

2022/09/20(火) 20:06:23.92

>>810
めちゃくちゃ嘘だったわ

2022/09/20(火) 20:08:23.68

普通にx毎に最小になるyを取れるようにする方針だけど
それだと幅*Qぐらいだから多分無理なので改良として
セグツリーかなんかで[x,..)の領域に対して一発でy取れるようにすりゃいんじゃねって思った
ちなワイ茶色

2022/09/20(火) 21:29:32.52

超思いつきだけどさ、
L<Rの場合、Lのテリトリーを譲ってまでRの幅を広げる必要はない気がするんだよな
だからLについては貪欲に最小拾っていいとかないかな？

2022/09/20(火) 22:04:05.16

耳DPのトロピカル行列をセグ木に乗っけて終わりとちゃうんか

2022/09/20(火) 22:05:42.62

全区間についての答えの和とかは解けんのかな
オーバーフローはないもんとして

2022/09/20(火) 22:19:34.98

耳DPの遷移を表すトロピカル行列が
L ∞ ∞
A_i A_i ∞
R R R
になってて、積についてモノイドになってるからセグ木に乗る
区間積求めてあとは(0,∞,∞)^tに作用させればおｋってこと？

2022/09/20(火) 22:21:34.19

>>813
なんかこれはこれで正当化できそうな雰囲気がある

2022/09/20(火) 22:25:23.85

結局正解っぽいやつについて自力で全然思いつかなかったの悲しい

2022/09/20(火) 23:18:52.20

>>800
paizaってOpenCV使ったりするような問題出るんだ

2022/09/21(水) 00:43:34.61

行列積の定数倍が重いせいで平方分割落とす制約にできないのか

2022/09/21(水) 11:31:22.73

情報の保持って観点じゃトロピカル行列は
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.83

あと区間長さえ保持しとけば

2022/09/21(水) 12:17:44.87

>>819
あ、opencasは私個人的な
ローカル環境での
動作確認、デバッグ用です
そういうのつけとけば
参加してくれる人いるかな
的な意図もあります

2022/09/21(水) 16:22:14.70

ふつうにLとの差分の累積和とって右から全探索でいいんじゃないのか？

2022/09/21(水) 18:13:16.60

N,Q≦10^5の制約だけど、それは2secで通る？

2022/09/21(水) 20:13:31.40

Nだから普通に通るよ

2022/09/21(水) 20:48:04.88

具体的なやり方が読み解けないけどクエリごとに全探索したらO(NQ)なのでは？

2022/09/21(水) 20:52:43.66

もしかして、元々の問題ABC263Dの解法の話してる？

2022/09/21(水) 21:08:22.89

昔のadminがりんごさんだったころのSRMってAGCとかに役に立つ？

2022/09/21(水) 22:35:20.54

>>828
ごめん話題変わってた？

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

説明やばいけど勘弁して

2022/09/22(木) 00:37:51.08

ABC263Dの解法としてはそれでOK
リンクされたツイートではさらに、元々の数列のうち区間[l,r)の部分に限った数列について元々の問題を解く×Qって設定になっていた
その解き方だとO(NQ)でTLEするので、これがちょっと難しかった(もう解法は発表されたけど)

2022/09/22(木) 01:37:50.90

正直、4つ持つことになんの意味があってどう嬉しいのか全く分からんぞい
耳dpってやつなの？

2022/09/22(木) 03:17:37.64

4つ情報を持ってないと、モノイドにする（≒結合則を成り立たせる）上で情報が足りないからセグ木に乗らない
このモノイドが代数的な言葉で言えばトロピカル行列に対応している
ちなみにこのトロピカル行列は耳DPの遷移だから、そっちから考えても同等の解答に行き着く的な感じ
明日気が向いたらこの辺ちゃんと書く
何か言葉は仰々しいけど別にトロピカル代数の知識なくても、上書き区間左側確定 T/F 上書き区間右側確定 T/Fで値持って区間をくっつけること考えたらどういう演算をしたらいいかは発想できると思う

2022/09/22(木) 03:22:21.63

自分の理解だとさらに区間の長さも必要そうだから厳密には必要なのは5つの情報かな？

2022/09/22(木) 11:18:12.70

半環上の正方行列が積が結合則満たすのって実正方行列での証明考えれば自明だけど、それが行列積だと分かってない状況だとかなり直観的に分かりづらいよな
そもそも行列積自体、初見で線形写像の幾何学的な話もなしだと結合則が成り立つと見抜くのが無理そうな意味不明な演算に見えるし

2022/09/24(土) 18:24:44.81

大槻の本に、比較によってソートするアルゴリズムの最悪計算量は、 Ω(n * log(n)) であると書いてあります。

最善の計算量が O(n * log(n)) よりも良いようなものって存在しますか？

2022/09/24(土) 18:33:53.75

nがあります

2022/09/24(土) 18:36:10.29

ボゴソートは最良計算時間nですよ

2022/09/24(土) 18:38:34.03

例を挙げてください。

2022/09/24(土) 19:08:37.47

最善って意味だと挿入ソートはO(N)

2022/09/24(土) 19:21:32.49

バブルソートはソート済みの列に対して O(n)

2022/09/24(土) 19:24:43.12

>>837-838,841

ありがとうございました。確かにバブルソートはそうですね。でもマージソートとか最善の計算量と最悪の計算量が同じ計算量のものが多いですね。

2022/09/24(土) 22:42:30.99

A問題、A問題の難易度じゃないだろ

2022/09/24(土) 22:53:45.20

Aこの難易度でも良いけど、ビギナーコンテストなんだから9割くらいが解けるDくらいまでにすべき、１０問は多すぎ
Dも昔は愚直にやって通るくらいの難易度だった気が

2022/09/24(土) 22:56:24.67

D問題が greedy じゃダメな理由がわからん……
解説に反例があるのは見たけど納得できない