usakdsteen

ゆうさくですてぃーん

2021年09月13日(Mon)の独り言

inwardly

の呟きは 86

 < の独り言 | の独り言 | の独り言 > 
  •  #

    わかった
    足りてない部分わかった

    •  #

      (omitted)

    •  #

      マジか
      足りない部分足したが
      スタックオーバーフローで死んだ・・・

      •  #

        これは、想定しておくべきものだろ・・・

        •  #

          これだから・・・
          オンラインジャッジ使わせろヨ・・・クソ

      •  #

        スタックメモリ増やしたが
        今度はヒープメモリ不足・・・

        •  (UPD ) #

          オンラインジャッジ使わせろや、コノクソ

          •  #

            低スペックPCに無慈悲な問題・・・

        •  #

          ヒープメモリを増やしたら
          堕ちずに最後まで動いたが、

          速度が足りない・・・
          TLE解法なのか
          あるいはPCのスペック不足なのか分からない

          速度が3倍以上にならんと話にならん・・・

          •  #

            3倍とまでは言わんが2.5倍くらいはないと厳しい

            •  #

              CPU25%制限を突破できないので
              どうしようもないが・・・

              •  (UPD ) #

                論理コア1つじゃなく物理コア1つで動いてくれれば
                もしかするとそれなり速度アップするかもだが

                CPUの占有率(CPU時間?)がどの程度か分からんから
                なんとも・・・

                物理コア1個のCPU50%で2倍の速度でるならいいけど、たぶん、2倍にはならなそう

                •  #

                  C++で書いたプログラムならCPU100%なるから
                  物理コアを2個使って計算できるってことになるが・・・？

                  •  #

                    このPC、物理コア2個ってことになってたはずだけど、それは嘘なの・・・？

                    それとも賢いCPUさんがオート並列化とかすんの？

          •  #

            入力40MBとはワロタ

            •  #

              重すぎ

  •  #

    すでにチャンスは無いけど
    定年45歳とかになったら
    もっとチャンス無くなるね

    僕アラフォー職歴なし無職なんですけど・・・

  •  #

    アレ
    解けなきゃダメなやつなのか・・・？

    •  #

      time is over

      ダメ

  •  #

    塩分とりすぎでダメ

  •  #

    shower timeしないと

  •  #

    思いのほか、歳の近い人ばかり見ていたのか・・・

  •  #

    マジか
    全然違った・・・

    •  #

      カスってすらいないな・・・

      •  #

        普通にTLE解法でいいだろうアレ

        •  #

          低スペックPCが悪いんじゃなかったね
          PC君、疑ってごめんネ！

          •  #

            俺がゴミ解法を捻出したのが悪い

      •  #

        軽く眺めただけじゃ解説分からん・・・

        shower time後にちゃんと読むか・・・

      •  #

        UFで大きい順に構築で全通りの組み合わせを求める・・・
        これ典型では・・・

        •  #

          解説のその後のDPがまだ解せぬ

          •  #

            全通りの総スコアをUFで求めたから
            あとは切断時スコアを特定したいってとこだと思うのだが
            最初の再帰はそれを求めるための準備的な処理だとは思うが
            よくわからん

            •  (UPD ) #

              2つ目の再帰は
              切断時のスコアを求める処理だろうけど
              再帰的に求めてる理由などよくわからｎ

              •  #

                俺のは前処理計算を4回の再帰で求めるだから、うーん、

                •  #

                  俺のは答えは合っててもTLE解法だからね・・・ダメ

                  •  #

                    3～4倍は遅い

                •  (UPD ) #

                  俺のやつで再帰2回分を追加する前のやつが
                  ちょうど切断相当のスコアを求めるための前処理のやつだが

                  •  (UPD ) #

                    この再帰2回後のスコアを求める処理がO(C*C*2N)になっており
                    おそらくこれがTLEの根本原因な気がするが

                    •  (UPD ) #

                      俺のやった再帰4回は4*O(C*N)なわけだから
                      コスト高いわけがない・・・

                      いあ、高いか・・

                    •  #

                      なるほど
                      解説コードのほうはC*Cにならない工夫がされている・・・

                      •  #

                        俺のやつは余計に値を持ちすぎ、ということか・・・？

                      •  #

                        難しいすぎて
                        まだ完全に理解に至ってねえ

              •  #

                1つ目の再帰が
                戻り順でノードに到達するノード総数を起点に集める形で集約する(D値)(戻り順なので親から来る数は含まれない

                2つ目の再帰は
                現在ノードに繋がるエッジ全部（親からのエッジを除く）において考える感じで
                親から子を見たとき子の持つD値(到達ノード数)は子へ繋がるエッジから見たときそこで伝播がストップされるノード総数に見える
                親が持ってるD値(到達ノード数)はその子からの伝播分(到達数)も含まれてるからそこから子からの伝播分を除去すると(U値)、エッジに取ってもう一方から伝播がストップされるノード総数と同じに見える、なのでD*Uをすると、そのエッジを除去した場合のスコア減少分に相当する、ということか？

                •  #

                  再帰で子に辿るとき
                  親から子に設定されたU値は
                  親側から子にまで到達するノード数に相当するから
                  親と同様に繰り返し子に対して計算してくと
                  イイカンジにエッジ除去時の減少スコア分の計算に役立つ、と

                  •  #

                    そこまではいいんだけど
                    感じのスコア計算時に
                    キャパ大きいほうから小さいほうへ順にD*Uを計算してるんだけど
                    1つ大きいほうのD*Uを引いてる部分が
                    まだ理解できていない・・・

                    •  #

                      これはDやUをキャパごとに計算してまとめてる部分の理解から足りてないせい

                    •  #

                      ところで解説とコードでソコの部分の説明が食い違ってません？？？
                      解説だと大きいほうから小さいほうを引いているような・・・？

                      •  #

                        どうでもいいけど解説コードのUnionFind
                        名前にunionがあるのにメソッドはunionじゃなくmerge
                        今回の問題ではrankは使用しないはずだけどrankも計算されているのな

                        あとDP用の配列、余分に容量が確保されるという、競プロ界の慣習も・・・

                        •  (UPD ) #

                          このunionfind、findが再帰使ってるから
                          スタックオーバーフロー気をつけないと死ぬな・・・(使用する言語や実行環境によるだろうけど

                          •  (UPD ) #

                            安易に真似ると死ねる
                            （まぁそもグローバル変数使い放題だしな・・・(言語によってはグローバル変数は・・・

                      •  #

                        ともかく
                        このD*Uのキャパ別引き算の理屈を理解できないと
                        実装できん

                        •  #

                          Dの値は
                          伝播する際に
                          そのエッジのキャパ以下の値を全部足しこんでいる
                          ノードごとにDの初期値は全キャパにおいて1になってる
                          つまり小さいキャパのほうにノード数の重複がある・・・

                          •  (UPD ) #

                            重複はまぁ最初からわかってたけど
                            (D[i]-D[i+1])*(U[i]-U[i+1])
                            ではないのはナンデだ？
                            D[i]*U[i]-D[i+1]*U[i+1]
                            なのはナンデだ？

                        •  (UPD ) #

                          そもエッジの両端に到達したノード数であるところのDとUだが
                          組み合わせを見るときに
                          より小さいほうのキャパになるよう組み合わせる必要性あるから
                          俺のやつだとO(C*C)の処理をしてたわけだけど
                          これはそれをやっていない
                          どういう理屈なんだ・・・？

                          •  (UPD ) #

                            DやUのキャパ小さいほうにノード数の重複があるから
                            例えばD[1]*U[1]はキャパ1のほうに抑えた場合の全組み合わせ数にはなる・・・？

                            いあ、そうはならず
                            キャパ1以外同士の積もキャパ1として計算されてしまう

                            •  #

                              キャパ2で考えたい場合

                              一方側(X)のキャパ2のノード数と
                              もう一方側(Y)のキャパ3以上のノード数との積
                              および、Y側のキャパ2とX側の3以上のノード数との積
                              および、X側とY側のキャパ2同士の積
                              これらの和になるはず・・・？

                            •  (UPD ) #

                              仮に
                              D[1] = d[1]+d[2]+d[3]+...+d[c]
                              U[1] = u[1]+u[2]+u[3]+...+d[c]
                              とすると(cは対象エッジのキャパ)
                              欲しいのは
                              d[1]*(u[2]+u[3]+...+u[c])
                              + (d[2]+d[3]+...+d[c])*u[1]
                              + d[1]*u[1]
                              であるはず？

                              ここで単純にD[1]*U[1]をすると
                              (d[2]+d[3]+...+d[c])*(u[2]+u[3]+...+u[c])
                              という余分な項が発生する

                              •  #

                                D[2] = d[2]+d[3]+...+d[c]
                                U[2] = u[2]+u[3]+...+d[c]
                                とするなら
                                D[1]*U[1]の余分な項はD[2]*U[2]に他ならない・・・！！

                                •  #

                                  なるほど、ね

                                  かなーりテクニカルな・・・

                                  •  #

                                    (omitted)

          •  (UPD ) #

            (omitted)

  •  #

    さっさとshower time

  •  #

    https://jvndb.jvn.jp/ja/contents/2021/JVNDB-2021-001383.html

    おーおー
    怖いなあ

  •  #

    R1、6800人弱が通過か・・・マジやべえな

    •  #

      R1までは本気出さない人も多いせいであれだが
      R2でスコア取れる人間4000人くらいはいそう

      •  (UPD ) #

        去年のR2は2000人未満・・・？去年は1500人がシャツ？
        一昨年のR2は1028人・・・？

        スコアボードの人数、おそらく、サブミット有の人数だわ・・・サブミット無しはスコアボードにいない
        スコアボードにいる0点はvalidation(?)を通したあとの本番サブミットでヘマした人、スコアボードにいない0点はvalidationすら通せなかったか不参加だったか

        •  #

          例年R2は2000人未満しかスコアボードにいないうえに得点できてるの1000未満な年もあるし
          今年シャツ2000人って
          問題を優しくでもするのか・？

          •  #

            (omitted)

        •  #

          validationは時間制限ない(?)から
          まぁ愚直でも通せなくもない・・・

  •  #

    https://gigazine.net/news/20210913-facebook-censoring-open-source-mastodon/

    マストドンってそんなに脅威なのか・・・？

    •  #

      日本人向けのマストドンの巨大インスタンスたちの末路を考えると・・・

      •  #

        マストドン
        小規模コミュニティ同士が繋がる仕組みはあれど
        基本はその小規模コミュニティ単位でインスタンス用意しなきゃならんし
        ハードル高い木がするが・・・

        無料でインスタンス作り放題ならともかく
        それならdiscordとかでもよくね？ってなるが

  •  #

    https://gigazine.net/news/20210913-starbucks-cookie-timeout/

    ドラクエの選択肢かよｗ

  •  #

    https://gigazine.net/news/20210913-remote-work-effects-microsoft/

    減少したコミュニケーションを増やすための新しいアイデアでも持ってくるのかと思ったら
    単にリモートワークをやめるだけの方向性でしか考えないのか・・・

    •  #

      変化していくのではなく
      元に戻ることを望むのか・・・

      •  #

        普通の人間は
        人とコミュニケーションとらないとメンタルがダメになる
        というのではなく

        外向性の人間と内向性の人間と世の中には半々いるみたいな話がどっかであったような気がするから
        前者の外向性主体の人間にとってリモートが厳しすぎるってことなんだろうな

        •  #

          リモートワークに適応できてるのは
          内向性主体の人間ばかり・・・？

  •  #

    UF持ってたっけ・・・？

    •  #

      持ってなさそう

  •  #

    DSUって何？

 < の独り言 | の独り言 | の独り言 >