/ 最近 .rdf 追記 設定 本棚

脳log[2021-11-14~]



2021年11月14日 (日) [AtCoder] 精進。ARC068-E「Snuke Line」(黄 diff)。たぶん調和級数がどうの計算量の見積もりがどうのという問題なのかな。調和級数が何か知りませんけども。とりあえず実装して実行してみる派ですけども。あるいはきっちり考察が詰められれば最終的な計算量は高がしれているのかな。■提出 #27263215 (AC / 1998 ms)。考察がへぼでも BIT で殴ると制限時間ギリギリセーフだった。Ruby で最初の AC であった>Ruby によるすべての提出。2.7 より古いバージョンでは不可能だったのかもしれないね。■ブログを読むとわりとみなさんと同じことを考えていたことがわかる。区間の幅を見たり、重複して数えてしまったり、BIT を使ったりというのが共通してる。案外あれは脳筋解答ではなかったのか。■昨日の ABC? D 問題ダメでした。結果は見ていない。緑落ちあるで。□Twitter でちらっと二分探索のワードが見えた。1部署に人数が固まりすぎてると無駄、少なすぎると統合して人数をかさ増ししなければいけないなど、K 個のプロジェクトに平均的に分散させる必要があって、余ってる足りないの基準となるボーダーを二分探索する考えは頭の隅にあった。でも結局解法によらずどうやって均すのかがわからんかった。


2021年11月12日 (金) [AtCoder] 精進。ARC076-E「Connected?」(黄 diff)。こういう(特定のアルゴリズム、データ構造を知っていますかという知識問題ではなくて、ゼロからむにゃむにゃ考える)問題好き。もちろん解けたから言えることだけど。もちろん(LIS と UnionFind がそうだったように)アルゴリズムを再発明するのでもいいんだけど。解説を読んじゃうと台無しになる類の問題なので、ネタバレには注意。■提出 #27191350 (AC / 390 Byte)。制約が線形時間もしくは入力された個々の点に対して対数時間の処理しか許していないので、試行錯誤はできない。最初は、N 個の点を並べることを考えた。たとえば並び順はなんでもいいけど 1→2→……→N という交差のないひと筆書きが同じ向きで2つ平行に書けたなら、答えは YES。だけど N の順列も交差判定も処理が重い。結局のところ、ひと筆書きを制約するものは壁に張り付いた点なのだということに気がついたら、あとはなんとかなる。


2021年11月10日 (水) [AtCoder] 精進。ARC067-E「Grouping」(黄 diff)。初見では手が出なかったが2度目の今日はわかった。残り人数をキーにして場合の数を記録する DP で、グループの人数を変えて遷移した。提出 #27170288 (AC / 914 ms)。■あほな人間は根を詰めて考え続けても答えは出ないんだ。一旦離れて忘れるのが肝心。それだけで労なく考え続けているのと同じ効果が上がるのが、「下手」の取り柄なのだ。(もしかして:効果ゼロ)


2021年11月09日 (火) [AtCoder] 精進。ARC077-E「guruguru」(黄 diff)。それほど難しくはないかな。ABC-D+α という感じ。プラスアルファで悉くつまずいて AC に辿り着けないのが自分ではあるが。ともあれ道具立てはコンテスト後にいつもいもす法だイベントソートだと話題になるあれ(よく知らないので自分では固有の名称に言及しないけど)。時間軸に沿って加速度と加速度の累積としての速度と速度の累積としての移動距離を記録して答えにする。■提出 #27154438。まずは入力された A 数列の隣接2要素(a,b)から情報を抽出する。a から b へ b-a 回のインクリメントを繰り返して移動するわけだけど、その途中にお気に入りがあると回数を節約できる。区間は [a+1,b] で節約幅は [0,b-a-1]。a+2 時点から節約効果が現れて、b がお気に入りのときに最高の b-a-1 回の節約になる。区間の左右端と節約回数の上下端が off-by-one エラーを誘発しやすい感じ(ドツボにはまった経験から書いています)。あとは区間を外れた b+1 の時点で節約効果をリセットするなど。時間軸は 1 から 2×M の2倍幅を扱うとループの境界を気にしなくて済む。■精進2。ARC035-C「アットコーダー王国の交通事情」(青 diff)。現在 Ruby での AC はなし>Ruby によるすべての提出。N^3 が想定解になる問題は定数倍のハンデも3乗で Ruby にはつらすぎる。提出 #27155496 (C++ / 88 ms)。C++ では一番速いぜ。■昨日の精進。ARC083-D「Restoring Road Network」(水 diff)。これも3乗だけど上限が 400 でなく 300 で、ループ内の処理もごく軽量なので、Ruby でも通る>Ruby によるすべての提出


2021年11月07日 (日)

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

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

解けなかった。

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

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

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

 提出 #27118298 (AC)

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

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

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

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

 なもりグラフ

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

chokudai(高橋 直大)🍆@chokudai

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

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

これもあった。ARC079-F「Namori Grundy」。橙 diff は、どうかなあ。解説 AC が1つあるだけだけど、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 に届くようなケースが1つでもあるなら、その要素は不必要ではない。それを左右からの DP で。■入力をソートしてみたりもしていたんだけど、大小関係を要不要の判断に活用する方法が思い浮かばなくて消してしまっていた。Ruby での AC 提出はどれもソートしている。大きい要素から順番に K 未満の和の集合を作っていくことを考える。和のどれかに現在の要素を加えて K 以上になったなら、その要素は不必要ではない。同時に、処理済みの要素(現在の要素と同じかより大きい)も現在の要素と交換することで不必要ではないと判断できる。最初の判断に利用した和の構成要素であったかどうかには影響されない。和の集合だけど、K 未満で K に一番近いものを1つだけ覚えておくのでいい。K に1足りないだけなら値が1の要素も必要にできる。7割8割くらいまではわかってたんだけどなー(負け惜しみ)。■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 を確定するまでに3回くらい実行を繰り返すというような話を聞いたけど、2026 ms みたいに TLE だけど実行打ち切り(22xx ms など)ではなさそうなタイムの時は、再提出することで試行回数が増やせます。だけど提出直後の2回目の提出は、うっかりミスを訂正するよくある提出パターンとして許されているけど、それ以上の連続提出は規制されているそう。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株式会社」■2番目のリンク先の冒頭。「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)。解けてみればド典型という感じだけど、初見ではグラフが見えなかった。問題を読むのは今日で2度目。提出 #26961806 (AC / 956 Byte / 1915 ms)。つい先日「辺に重みがあるんだから BFS ではなくダイクストラ法を使うべきだというのはあるかも。実装も定数倍も重くて気が進まないわけなんだけど」と書いたばかりで、重くて気が進まないプライオリティキューでダイクストラ法をした。ところで Ruby の他の提出を見ると 500 ms を切る提出がちらほらあって、プライオリティキューは使っていない。まねしてみたのがこれ>提出 #26962407 (AC / 413 Byte / 221 ms)。短くて速い。えっ? どういうことなの? N の総数が高々 1000 だからなのか完全グラフだからなのか。(完全グラフという数日前に初めて見た単語を使ってみた。Wikipedia によるとクリークと関連があるらしい。クリークの初見は3か月前>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 台に先頭集団がある他は1秒オーバーがほとんどなんだけど(「Ruby によるすべての提出」)、長さに関してはどの提出も自分の 798 Byte より短い。何か見落としがある! これが短くて速い代表的な提出だけどほとんどワンライナー>#18041479。どういうことなの? ×2するところを÷2にすることで要素の更新が省略できて速いらしいんだけど、そもそも持っているデータが違うから×2も÷2もないんだよね。■繰り返される配列の確保と初期化が重かったのでできるだけ短い配列で済ませるようにした>提出 #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 の間で1つおきの数字のどれか。これを頑張って子ノード間でマージしながら矛盾なく根っこまでたどり着けたら答えは Yes。根っこの値を1つ選んで今度は下りながら子の数を確定していく。今のところ Ruby での AC は3つなんだけど(「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)

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

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

 E 問題 Integers on Grid

時間は1時間ほど残っていたのに、結果的に1時間と 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 120C 問題 Swaps 2

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

 問題の操作

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

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

 ポテンシャル

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

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

 B 数列

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

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

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

難しい。これが水 diff ってどうかしてる。ちなみに Swaps の1はこれ>「Swaps」。黄 diff です。解けるまで9か月寝かせました(20191111p0120200826p01)。2は1日寝かせただけで解けたんだから、妥当なのか?