の呟きは 48
- (UPD ) #
原因わかった
範囲最小を取る構造体を作ったつもりになっただけで
その通りに動作してない(omitted)
んー、もしかして解法に範囲最小は不要だったりする・・・??
不穏な手ごたえを感じつつある
まさかのまさかだった
愚直に組むだけで通った・・・・orz頑張って範囲最小を組んだ僕・・・
無駄に無限時間を消耗した・・・
要するに
愚直に組んだ際の計算量がわかっていないのが原因
(計算量わかってないのが原因で死ぬのよくあるな・・・計算量を見積もれない俺が全て悪いわけだが・・・
- (UPD ) #
O(N^2)だと勝手に思ってたけど
おそらく平均的(?)な処理量(?)のアレで
O(Nlog(N))に落ちるとかなんじゃ・・・?アルゴリズムとかデータ構造とかの
計算量を求める理屈とかのやつ
先生どころかテキストすらも説明カットすること多いからな・・・
学生への課題であるじゃねえんだよ
正しく求められてるかの判定すらできないもん課題にすんじゃねえええよおおおお(いあ、出来たら先生に評価してもらいにいくってことなのか・・・?コミュ力の試験・・・?まさかO(N)の可能性すらあるのか・・?
計算量どうやって見積もるなの・・・- (UPD ) #
O(N)は計算量の上界値を示して
Ω(N)は計算量の下界値を示して
Θ(N)は上界値と下界値の両方を示している・・・?
上界値は
計算量がO(N)以下に抑えられますよ~的な意味らしく
下界値は
計算量がΩ(N)未満になることは理論上絶対に不可能ですよ~的な意味らしい?
大学時代のテキストをさらっと読んでみたΩ表記のあるものは
アルゴリズム的改善は不可能で
せいぜい実装下手による無駄コストを削る高速化くらいしかない・・・?ハードウェア的改善は汎用性を無くして特化するとかになるかもだが
物理的な変化の速度は量子コンピュータやらが期待されているらしいが・・・
テキストには
最悪計算量を求めるのは比較的簡単だとかどうとか書いてあって
平均計算量は数学的にとか確率とか平均とかどうのこうの・・・そして、俺がいま必要としてるのが最悪計算量なわけで・・・
計算量はステップ数をどうのこうの、とか書いてあったが・・・- (UPD ) #
某問題の最悪時間量(ステップ数?)
N*(N+1)/2に見えるけど・・・
何か見積もり間違ってるのか・・・?こないだもN*(N+1)/2な問題にやられたが
こないだのは他の係数もあって10分の1以下に落ちてたぽいわけだけど、
今回の、落ちそうな情報があるようには見えない・・・普通に数秒かかるよね・・・
https://ideone.com/z965H3- (UPD ) #
おそらく最悪ケースが入っていない
平均時間量なら間に合う系(?)平均時間量
マジで確率分からんとどうにもならんので
計算無理
- (UPD ) #
きょーぷろでは空間量とか言ってるやつ
テキストでは領域量って表記だな
時間計算量とか空間計算量とかいう言葉も無い
時間量(時間手間)と領域量を両方まとめて計算量と呼ぶみたいに書いてあるが・・・
全体のページ通して時間量・領域量って書かれてるな、まぁ平均時間量とか最悪時間量とかは書かれてるけど、
計算量という呼び方は最初の用語説明時以降は全然ないな
正解率高いわけだ・・・
典型ですらない・・・
マウスの左ボタンの感度悪い・・・
まーた失敗
評価がダウン・・・
最高値から-116...
もうだめぽ。。。眠気強くて思考回らないのも一因としてはあるが
まぁ言い訳はダメ解法まるでわからん・・・
https://pkg.go.dev/search?q=neetsdkasu
んん??????
なんでfizzbuzzのやつ登録されてんだ・・・?俺のローカル環境では
環境変数でちゃんとdirect設定してるから登録はされないはずだが・・・・??色々ガチャガチャやってたときに
何かgoまわりのバグでも踏んだんだろうか・・・?あー、
おそらくバグではなく
登録をしてしまうコマンド(あるいは引数)を使ったのかもしれないドキュメントを見ずに適当にコマンド打つから・・・
しかもv1.0.1のほうが登録されているの謎すぎるが・・・?
やる気が無限消滅
今朝の超上級問題の解法わからねえ
どう思考しても
計算量爆発発生しゅりゅ2割もの人間が通してるし
何らかの解決策はあるんだろうけど
制約とよくにらめっこして
浮かんだ解法で通った・・・
愚直に近い解法・・・これ計算が間に合う証明はわからない・・・俺の頭じゃ無理・・・
コーナーケースありそうだけど
俺の頭じゃ閃かないし
アリなのかナシなのかすら感覚的には分からない・・・まぁこの解法限定のコーナーケースになろうから
任意の解法を落とせるケースというわけではなかろうけど・・・
思いついたコーナーケースだと
まぁO(N^3)くらいかかるけど
制約的には全然余裕、か
まーたTLE解を出した気がする