/ 最近 .rdf 追記 設定 本棚

脳log[2021-11-07～]

最近

2021年11月07日 (日)

最終更新: 2021-11-12T21:42+0900

♪ [AtCoder] AtCoder Beginner Contest 226／E 問題 Just one

解けなかった。

 提出 #27107258 (WA×9 / AC×24)

これはコンテスト中の提出。WA と AC の比率からして惜しいのかなという感じ。おそらく 0 を返すべきケースで 0 が返せていない。それはどういうケースか。連結成分が８の字になっていたりして輪っかが１つではないケース。

しかしそれをどうやって検出するのか解らなかった。

 提出 #27118298 (AC)

これはコンテスト終了後の提出。さっきの WA 提出では UnionFind で閉路の検出(だけ)をしていたのだけど、もうちょっと細かく、ノード数と辺の数の両方がわかるように記録をつけた。

辺の数がノード数より１だけ小さい連結成分は木であり、辺の数はこれが最小。辺の数とノード数が同じ連結成分はループが１つとオプションで突起をいくつか持っている。辺の数がノード数より多い連結成分は複数のループを持っている。

題意を満たせるような連結成分は３種のうちの１つだけ。他の２つが存在すれば答えはゼロだし、適合する連結成分のみが A 個あったなら答えは 2.pow(A,998244353)。

ここまで考えがまとまるのに２時間かかってるんだよなあ。

 なもりグラフ

なんか「なもりグラフ」という名前があるらしかった。調べようとしたらゆるゆりの人と名前がかぶってて検索性が悪かったのだけど、別に間違ってはいなかった。なもりを検索してなもりが見つかるのは当然。

chokudai(高橋 直大)🍆@chokudai

F問題の由来です。（N頂点N辺の連結なグラフを「なもりグラフ」と呼ぶ人がいるのもこれが理由です。） https://t.co/saSTvA1lep

Twitter

F 問題って、AGC の F 問題「Namori」じゃないですかー(やだー)。赤 diff の精進は 10 年後も手つかずの見込みですから。

これもあった。ARC079-F「Namori Grundy」。橙 diff は、どうかなあ。解説 AC が１つあるだけだけど、10 年後は。

ツッコミを入れる

2021年11月06日 (土) [AtCoder] 精進。ARC070-D「No Need」(ギリギリ黄 diff)。N と K の上限が 5000 なんだけど、O(NK) を通すために C++ で殴ってしまった。提出 #27059260 (AC / 106 ms)。なんという甘え。なんという芸のなさ。しかし 11 個目の黄 diff AC であることに変わりはない。ないったらない。■Ruby でのすべての提出を見ると、しっかり Ruby で通している人がいますね。1241 ms、1010 ms、14 ms。これで全部。98 Byte/14 ms の提出は頭おかしいと言わざるを得ない。なんだよそれー。■自分の方針。ある要素に注目したとき、それ以外の要素を組み合わせて作れる和にある要素を足して初めて K に届くようなケースが１つでもあるなら、その要素は不必要ではない。それを左右からの DP で。■入力をソートしてみたりもしていたんだけど、大小関係を要不要の判断に活用する方法が思い浮かばなくて消してしまっていた。Ruby での AC 提出はどれもソートしている。大きい要素から順番に K 未満の和の集合を作っていくことを考える。和のどれかに現在の要素を加えて K 以上になったなら、その要素は不必要ではない。同時に、処理済みの要素(現在の要素と同じかより大きい)も現在の要素と交換することで不必要ではないと判断できる。最初の判断に利用した和の構成要素であったかどうかには影響されない。和の集合だけど、K 未満で K に一番近いものを１つだけ覚えておくのでいい。K に１足りないだけなら値が１の要素も必要にできる。７割８割くらいまではわかってたんだけどなー(負け惜しみ)。■K 未満で K に一番近い和だけど、要素を大きい順に処理していることで自然に求まるかと思ったけどそんなことはないよね。DP が必要。提出 #1172583 を理解するには考察が足りない。■N=4; K=100; A=70,50,49,1 という入力に対して、左右から DP をする自分の提出と、ソートして二分探索して両端をメモして DP の回数を抑えている(っぽい)提出 #4480840 が 0 を返しているところ、提出 #1172583 は 1 を返す。14 ms で Ruby 最速の提出は嘘解法ということでよろしいか。■Ruby で通った！ 提出 #27128108 (AC / 1997 ms)。AtCoder では TLE を確定するまでに３回くらい実行を繰り返すというような話を聞いたけど、2026 ms みたいに TLE だけど実行打ち切り(22xx ms など)ではなさそうなタイムの時は、再提出することで試行回数が増やせます。だけど提出直後の２回目の提出は、うっかりミスを訂正するよくある提出パターンとして許されているけど、それ以上の連続提出は規制されているそう。DoS 攻撃になっちゃうからね。■公式解説を読むと O(NK) と O(NKlogN) が想定解であって、O(NK) は速い方だった。ちょっと雲行きが怪しいぞ。自分がやってたのは O(NKK) の三重ループじゃあないですか(それでも通ってしまう C++ の犯罪性の高さよ)。でも Ruby のは二重ループだからっ。

ツッコミを入れる

2021年11月02日 (火) [Ruby] 読んだ。「YJIT: CRuby向けの新しいJITコンパイラを構築する（翻訳）｜TechRacho by BPS株式会社」「Rubyオブジェクトの未来をつくる「シェイプ」とは（翻訳）｜TechRacho by BPS株式会社」■２番目のリンク先の冒頭。「Rubyが他の言語に比べてときどき遅くなることがある理由を聞かれたら、私なら「もしも〜だったら」を筆頭の理由に挙げます。 Rubyの実装では、プログラムを実行するときに「もしもこうだったら、ああだったら」を考えるのに多くの時間を費やします。足し算のたびに「オーバーフローしたらどうするか」、メソッドを呼び出すたびに「メソッドがモンキーパッチされていたらどうするか」、コードの1行1行で「トレースが有効にされていたらどうするか」といったことを判断しなければなりません。」 型付けによってプログラマが違反に対するペナルティを引き受けるから、Ruby は高速で突っ走ってくれ、と指示するモードが欲しくなったりする。Ruby で導入されつつある型はそういう用途ではないらしいけど、「シェイプ」が期待に応えるという話。ペナルティはありません。■これも読んだ。「Async Ruby - Bruno Sutic」 すごく楽しみな機能。「A word of notice: Async does not get around Ruby's Global Interpreter Lock (GIL).」という前置きの解釈がわからないし、なんなら直訳も理解してないけど。共有リソースにアクセスすると全然 async にならないよ、ってことなら想定内だけど、デッドロックしない/させないやり方は想像できない。Fiber についても知らない。最後にこう書かれてるし、サンプルのチョイスもこの通りなので、「Async's strongest point is scaling network I/O operations, like making or receiving HTTP requests. Threads are a better choice for CPU-intensive workloads, but at least we don't have to use them for everything anymore.」、自分には使い道がないかもしれない。それでも「but ～」には同意するほかない。

ツッコミを入れる

2021年11月01日 (月) [AtCoder] 精進。ARC023-C「タコヤ木」(青 diff)。累積和の累積和の累積和の……を求めたいのだけど、累積和の項数と累積和を重ねる回数の、どちらかが N(≦2000)でどちらかが A(≦10^9)で制約されるので、手続き的に答えを求めることができない。とりあえず 10×10 の表を作って眺めてみて、Wikipedia で「パスカルの三角形」を検索した。そうしたらコンビネーションで求められることがわかった。提出 #26976714 (AC / 427 Byte / 64 ms)。同じページに「カタラン数」の文字も見えた。これは ABC の関連ツイートで見かけたことがある(が知らない)。■検索してブログを読むと、仕切りを加えた組み合わせを考えることで累積和やらパスカルの三角形やらを経由せず直接コンビネーションを答えに導けるようだった。それは高校で習ったし AtCoder の問題でも利用したことがある。知っているが引き出せなかった。むむむ。

ツッコミを入れる

2021年10月31日 (日) [AtCoder] 精進。ARC064-E「Cosmic Rays」(青 diff)。解けてみればド典型という感じだけど、初見ではグラフが見えなかった。問題を読むのは今日で２度目。提出 #26961806 (AC / 956 Byte / 1915 ms)。つい先日「辺に重みがあるんだから BFS ではなくダイクストラ法を使うべきだというのはあるかも。実装も定数倍も重くて気が進まないわけなんだけど」と書いたばかりで、重くて気が進まないプライオリティキューでダイクストラ法をした。ところで Ruby の他の提出を見ると 500 ms を切る提出がちらほらあって、プライオリティキューは使っていない。まねしてみたのがこれ>提出 #26962407 (AC / 413 Byte / 221 ms)。短くて速い。えっ？ どういうことなの？ N の総数が高々 1000 だからなのか完全グラフだからなのか。(完全グラフという数日前に初めて見た単語を使ってみた。Wikipedia によるとクリークと関連があるらしい。クリークの初見は３か月前>20210716)。

ツッコミを入れる

2021年10月27日 (水) [AtCoder] 精進。ABC169-F「Knapsack for All Subsets」(青 diff)。よくある DP をすると TLE が必至なので、A 数列の同じ値を和と場合の数にまとめてから頑張って掛け合わせた。提出 #26852407 (AC / 798 Byte / 841 ms)。そしたらね、Ruby で断トツ一番速い提出がこれ>#13965887 (195 ms)。numo/narray ですって。それ以外の提出は 600 ms 台に先頭集団がある他は１秒オーバーがほとんどなんだけど(「Ruby によるすべての提出」)、長さに関してはどの提出も自分の 798 Byte より短い。何か見落としがある！ これが短くて速い代表的な提出だけどほとんどワンライナー>#18041479。どういうことなの？ ×２するところを÷２にすることで要素の更新が省略できて速いらしいんだけど、そもそも持っているデータが違うから×２も÷２もないんだよね。■繰り返される配列の確保と初期化が重かったのでできるだけ短い配列で済ませるようにした>提出 #26862342 (AC / 717 Byte / 679 ms)。考察がへぼでも 600 ms 台に入った。添字 1 から A の値未満のところは初期値から更新されないので不要なのだけど、添字 0 のところに意味のある値が入っているのが邪魔。配列をローテーションしてから長さを切り詰めている。難解。へぼな考察を実装でごり押ししているのが悪い。

ツッコミを入れる

2021年10月26日 (火) [AtCoder] 精進。ARC063-E「木と整数」(黄 diff)。提出 #26833318 (AC / 1419 Byte / 463 ms)。すごく、難しかったです。ノードに持たせた情報は、入力で与えられた確定数字と、数字までの距離。たとえば数字が P で距離が D なら、そのノードが取り得る値は P-D から P+D の間で１つおきの数字のどれか。これを頑張って子ノード間でマージしながら矛盾なく根っこまでたどり着けたら答えは Yes。根っこの値を１つ選んで今度は下りながら子の数を確定していく。今のところ Ruby での AC は３つなんだけど(「Ruby によるすべての提出」)、どれも異なる考え方で書かれている気がする。どういうことなんだ？ さておきこれで黄 diff の AC は 10 個目。着々と増えている。■解説を読むとノードに持たせるのは数字と距離ではなく取り得る数字の範囲にすると楽そうだった。それでやると Corvvs さんのこちらの提出になるようだ>#4817029。自分でもやってみた>提出 #26837318 (AC / 722 Byte / 434 ms)。枠組みはさっきのとほぼ共通なんだけど、子ノードのマージ部分であれこれ考えずに min/max で済ませられるのがすごく楽。他にはプライオリティキューで解いている人もいますが……(根本の方針がさっぱり想像できない)。小さい数字から順番に埋めていってるっぽい。それで自然と均衡点が定まってくるというのはなんとなく想像できるけど、なんとなくだよ。そのやり方でうまくいくときは必ずうまくいくということに確信が持てない(ので自分では書けない)。こちらが参考になる>「ARC063E 木と整数(800) - tekiheiの日記」。ひっくりかえっても自分の頭からは出てこない発想。

ツッコミを入れる

2021年10月23日 (土)

最終更新: 2021-10-26T00:58+0900

♪ [AtCoder] AtCoder Beginner Contest 224／D,E

D 問題で TLE に苦しんだ。E 問題も TLE に苦しんだ。そのまま E 問題が解けなかったので F 問題は読めなかった。

 D 問題 8 Puzzle on Graph

全探索が許されそうな制約。重複チェックのためのハッシュ表のキーを文字列にするか配列にするかで悩んだ。結果的に文字列ベースの探索で AC になった。

 提出 #26768646 (TLE×1 / over 4 秒)
 提出 #26770107 (AC / 2275 ms)

欠けてる数字を９番目の要素にするのがちょっとした Tips. TLE 解消の決め手にはならなかったんだけど。

現在の状態からありうる次の状態(のうち初出のもの)をすべて候補にするという意味で感覚的に全探索と書いたけど、そういうのは幅優先探索と呼ぶらしかった。

 E 問題 Integers on Grid

時間は１時間ほど残っていたのに、結果的に１時間と 10 分が AC までに必要だった。

 提出 #26776942 (TLE×18)

D 問題の TLE×1 と違って全然惜しくない。どこの処理量が膨れ上がるかとソースを眺めてみると、遷移のための辺を逐一処理しているところがダメ。

遷移の方向は A の小さい方から大きい方に決まっているので、A の降順に遷移可能回数を数え、行と列にその回数をメモしておけばいい。今後この行(この列)から遷移先を探すものがあるならメモした回数だけ遷移できますよ、というメモ。A の降順に処理しているから参照したメモはいつでも有効。

ああいや、A の値が等しい別の点が書き込んだメモを参照しないようにだけ注意が必要。この辺の呼吸は珍しくないので心得たものである。

 提出 #26781610 (AC / 1230 ms)

あと 10 分あればなあ。

 提出 #26786787 (AC / 708 ms)

不要になった処理を消し忘れてた。

レートはちょっとだけ上がってる☞。しかしもっと上がりたかった。

ツッコミを入れる

2021年10月22日 (金)

最終更新: 2021-11-23T22:07+0900

♪ [AtCoder] AtCoder Regular Contest 120／C 問題 Swaps 2

精進ですよ。水 diff だけど難しい(まるで水 diff が簡単かのような……)。考えがまとまるまで１日かかった。

 問題の操作

隣接２要素をスワップして +1/-1 するというけど、考えやすいように複数の操作をまとめるとこう。

  1. ある要素 Ai を右に(左に)いくつか移動する。
  2. たとえば右に５移動するなら、移動先の値は Ai-5 になる。
  3. たとえば右に５移動するなら、飛び越された５つの要素が、移動先に空きを作るためと移動元の空きを埋めるために、１つずつ左に移動している。
  4. 左に１移動した５つの要素は値を +1 する。

 ポテンシャル

Ai の値は移動に伴って変化しているように見えるけど、実のところ位置に応じて決まった値をとっているに過ぎない。どういう値をとるかは、最初に位置 i で値 Ai をとっていた、ということで決まる。

A 数列の各要素が位置１でとる値をその要素のポテンシャルと呼ぶことにする。ポテンシャルから要素の位置を逆引きできるようにインデックスを作成しておく。

 B 数列

B 数列をスキャンしながら、要求するポテンシャルを計算し、該当する要素を A 数列の先頭に近いところから貪欲に引っぱってくる。

引っぱってくるに際していくつの要素と位置を交換することになるかは BIT で転倒数を管理することで数える。というか、知る必要があって管理している数字が転倒数と呼ばれている、が順序として正しい。

 提出 #26732769 (AC / 561 Byte / 491 ms)

難しい。これが水 diff ってどうかしてる。ちなみに Swaps の１はこれ>「Swaps」。黄 diff です。解けるまで９か月寝かせました(20191111p01→20200826p01)。２は１日寝かせただけで解けたんだから、妥当なのか？

ツッコミを入れる

2021年10月14日 (木) [AtCoder] 精進。ABC160-F「Distributing Integers」(ギリギリ黄 diff)。最近よく見る全方位木 DP。20210928p01.01、20211010p01.06。ノード間の式は ABC217-F「Make Pair」に提出したものと同じ(#25683515)。各ノードが自身を含めて A 個の子孫ノードを塗る方法(順番列)を B 通り持っているとき、２つの子ノード以下を塗る方法は B1×B2×(A1+A2 個から A1 個を選ぶ組み合わせ)で求まる。提出 #26559753 (AC / 1028 Byte / 1548 ms)。これで黄 diff の AC は９個目。かなり貴重。■■■全方位木 DP と言えば第八回 PAST の H 問題「最短経路」。制約が N≦3000 だから全ペア 900 万通りの全探索が想定解法かなーと想像したんだけど、Ruby にはやや厳しく見える数字。最近覚えた全方位木 DP で>提出 #26574539 (AC / 72 ms)。子ノードのマージ部分が全方位木 DP 問題唯一のアイデンティティ。各ノードに子孫ノードへの距離一覧をハッシュ表で持たせた。あとは全要素更新を避けるためのオフセット値を表とは別に持たせたりマージテクなどの時間節約術。ところで、提出した解法を全方位～と呼んでいいのかはよくわからない。全ノードを起点にした距離を調べてはいるんだけど、距離って指向性がないので頂点ペアを片方向しか調べなくていいわけなので、ただの木 DP と同じように根への１パスで処理が終わっている。■BFS で全点間距離を調べる方法はやっぱり厳しかった。ゴルフしながら１秒前後で通してる提出が多数あるからそうでもないのかなって思ってたけど、実際厳しかった。あの短いスクリプトのどこにどんなアルゴリズムがあるというのか。ともあれ最終的には BFS でも通った>提出 #26823765 (AC / 814 ms)。どういう時短術を使ったか。X を超える距離はすべて X 以上という扱いにしてそれより遠くの頂点は調べなかった。その場合でも最内ループでチェックをすると TLE がひどいので(#26823520 の 13 行目)、その１つ外でチェックをした(AC コードの 11 行目) (よく考えると TLE がひどいのは距離表の更新がスキップされてるからで、X を超えていてスキップするのはキューへの追加だけにすべきだった)。最も効いたのは、すでに距離一覧を調べてある隣接ノードの結果を流用したこと。そうすると、開始点から出る辺のうちの１本から先にあるノードは距離を調べずに済ませられる。そのために距離表はオフセット値とセットにして初めて実際の距離を表す。この点は全方位木 DP でのやり方と一緒。くらべて不利な点は、距離一覧ではなく具体的な頂点とのあいだの距離を一覧して持っていて等距離にある２点を同一視できていないので扱う数字が多いことと、結果の流用が辺の１本に対してしかできていないこと。これらの差で全方位木 DP に負ける。辺に重みがあるんだから BFS ではなくダイクストラ法を使うべきだというのはあるかも。実装も定数倍も重くて気が進まないわけなんだけど。■同じアイディアでちょっと前の ABC で制約が厳しくて想定解法のワーシャルフロイド法が通らなかった問題が通せないかな。

ツッコミを入れる

2021年10月13日 (水) [AtCoder] 精進。ARC089-D「Checker」(青 diff)。大きさが 2K×2K で黒白２マスずつの最小市松模様に 2N 個の点をプロットしておいて、K×K の枠内に最大でいくつの点が含まれるかを二次元累積和で求めるのだと思った。概ね正しかったのだけど、二次元累積和のサイズは 2K×2K ではなくて 4K×4K が必要らしかった。わからないが言われたように修正してみる。提出 #26544471 (TLE×8)。定数倍がたいへん厳しい。提出 #26544665 (AC / 956 ms)。元データが 2K×2K なのだから愚直にデータを展開せずとも計算で仮想的に 4K×4K を存在させられる。ところでこの人の提出>#2789430。すごく短いのと、累積和のサイズが 2K×2K だ。c と N-c を同時に答えの候補にしている部分がよくわからない。わからなくはないか。黒く塗るか白く塗るかだ。そうすると 4K×4K が必要というのも、K×K の枠内が■□■□になる場合と□■□■になる場合を網羅するためだったか。じゃあ 3K×3K でも？ そもそもさっきの仮想累積和の提出(#26544665)が、3K×3K の累積和上を K×K の枠が移動する 2K×2K 通りの探索になってたっぽい。わかってやってるんじゃあないんだよなあ。

ツッコミを入れる

2021年10月12日 (火) [AtCoder] 精進。ARC088-D「Wide Flip」(ギリギリ青 diff)。まずは問題を理解する。「操作には２つの端点がある」「端点は 0 と 1 の境界に揃えたい(←この表現)。そうすれば操作のたびに端点にあった境界が消える。さもなければ新たな境界が生まれるが、それは嬉しくない(←この表現)」「一方の端点を文字列の先頭または末尾に固定して手近な境界から貪欲に消していけばゴールに至る」「文字列の真ん中より手前側にある境界は相方に任せて良い」。提出 #26527889。■一番最初に思いついたゴールに至る確実な答えは、最も短い 111...列(000...列)の長さを操作の最小幅にすることだった。これをどこまで伸ばすことができるか。文字列の端っこまで伸ばしたとき答えが見える。

ツッコミを入れる

2021年10月11日 (月) 「ベテランの「適当でいいよ」は真に受けちゃいけない→ベテランと新人の『適当』にはこれくらいの違いがある - Togetter」■適当に正反対の意味があるのって、判断の基準が主観にあることで結果がピンキリになり、ピンの結果とキリの結果がどちらも適当にやった結果扱いされるせいで起こる現象だと思ってる。なかなかに味わい深い言葉。適当でいいという指示こそがテキトーであり適当ではなかったのであり、言葉からしっぺ返しを食らっている、的な。本当にテキトーでいいなら指示が必要な場面ではなかったはずだし、期待する結果も期待外れの結果も存在し得ないのが道理。「適当でいいよ」ではなくて「もうそれくらいでいいよ」なら許されたのかな。

ツッコミを入れる
最近

ロード後に重いスクリプトが走って文字が動く？

Generated by tDiary version 2.3.3.20091124
Powered by Ruby version 2.5.5-p157