最終更新: 2021-11-12T21:42+0900
解けなかった。
これはコンテスト中の提出。WA と AC の比率からして惜しいのかなという感じ。おそらく 0 を返すべきケースで 0 が返せていない。それはどういうケースか。連結成分が８の字になっていたりして輪っかが１つではないケース。
しかしそれをどうやって検出するのか解らなかった。
これはコンテスト終了後の提出。さっきの WA 提出では UnionFind で閉路の検出(だけ)をしていたのだけど、もうちょっと細かく、ノード数と辺の数の両方がわかるように記録をつけた。
辺の数がノード数より１だけ小さい連結成分は木であり、辺の数はこれが最小。辺の数とノード数が同じ連結成分はループが１つとオプションで突起をいくつか持っている。辺の数がノード数より多い連結成分は複数のループを持っている。
題意を満たせるような連結成分は３種のうちの１つだけ。他の２つが存在すれば答えはゼロだし、適合する連結成分のみが A 個あったなら答えは 2.pow(A,998244353)。
ここまで考えがまとまるのに２時間かかってるんだよなあ。
なんか「なもりグラフ」という名前があるらしかった。調べようとしたらゆるゆりの人と名前がかぶってて検索性が悪かったのだけど、別に間違ってはいなかった。なもりを検索してなもりが見つかるのは当然。
chokudai(高橋 直大)🍆@chokudai
F問題の由来です。（N頂点N辺の連結なグラフを「なもりグラフ」と呼ぶ人がいるのもこれが理由です。） https://t.co/saSTvA1lep
F 問題って、AGC の F 問題「Namori」じゃないですかー(やだー)。赤 diff の精進は 10 年後も手つかずの見込みですから。
これもあった。ARC079-F「Namori Grundy」。橙 diff は、どうかなあ。解説 AC が１つあるだけだけど、10 年後は。
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-10-26T00:58+0900
D 問題で TLE に苦しんだ。E 問題も TLE に苦しんだ。そのまま E 問題が解けなかったので F 問題は読めなかった。
全探索が許されそうな制約。重複チェックのためのハッシュ表のキーを文字列にするか配列にするかで悩んだ。結果的に文字列ベースの探索で AC になった。
欠けてる数字を９番目の要素にするのがちょっとした Tips. TLE 解消の決め手にはならなかったんだけど。
現在の状態からありうる次の状態(のうち初出のもの)をすべて候補にするという意味で感覚的に全探索と書いたけど、そういうのは幅優先探索と呼ぶらしかった。
時間は１時間ほど残っていたのに、結果的に１時間と 10 分が AC までに必要だった。
D 問題の TLE×1 と違って全然惜しくない。どこの処理量が膨れ上がるかとソースを眺めてみると、遷移のための辺を逐一処理しているところがダメ。
遷移の方向は A の小さい方から大きい方に決まっているので、A の降順に遷移可能回数を数え、行と列にその回数をメモしておけばいい。今後この行(この列)から遷移先を探すものがあるならメモした回数だけ遷移できますよ、というメモ。A の降順に処理しているから参照したメモはいつでも有効。
ああいや、A の値が等しい別の点が書き込んだメモを参照しないようにだけ注意が必要。この辺の呼吸は珍しくないので心得たものである。
あと 10 分あればなあ。
不要になった処理を消し忘れてた。
レートはちょっとだけ上がってる☞。しかしもっと上がりたかった。
最終更新: 2021-11-23T22:07+0900
精進ですよ。水 diff だけど難しい(まるで水 diff が簡単かのような……)。考えがまとまるまで１日かかった。
隣接２要素をスワップして +1/-1 するというけど、考えやすいように複数の操作をまとめるとこう。
Ai の値は移動に伴って変化しているように見えるけど、実のところ位置に応じて決まった値をとっているに過ぎない。どういう値をとるかは、最初に位置 i で値 Ai をとっていた、ということで決まる。
A 数列の各要素が位置１でとる値をその要素のポテンシャルと呼ぶことにする。ポテンシャルから要素の位置を逆引きできるようにインデックスを作成しておく。
B 数列をスキャンしながら、要求するポテンシャルを計算し、該当する要素を A 数列の先頭に近いところから貪欲に引っぱってくる。
引っぱってくるに際していくつの要素と位置を交換することになるかは BIT で転倒数を管理することで数える。というか、知る必要があって管理している数字が転倒数と呼ばれている、が順序として正しい。
難しい。これが水 diff ってどうかしてる。ちなみに Swaps の１はこれ>「Swaps」。黄 diff です。解けるまで９か月寝かせました(20191111p01→20200826p01)。２は１日寝かせただけで解けたんだから、妥当なのか？