2023年10月9日月曜日

AtCoder Regular Contest 166

　Cまで三完。

コンテスト後のツイート

D - Interval Counts

　解説AC。

　コンテスト中は、最小値を取りたいということから、(-∞, ?]や[?, ∞)という区間をいっぱい作りたい……というところから考えてしまったが、この方針はあまり良くない。

　もっと根本的に、[L, R]という区間をいくつか張る問題だということを意識するべきだった。
　そうすると、Yの隣接差分を見ることで、区間が何個始まるか、何個終わるか、の差分が分かる。しかし、ある場所で区間が終わり、同時に始まったとすると、その二つはくっつけた方がいいのは当たり前。
　ということは、Yの隣接差分は、「各場所について区間が何個始まるか、もしくは何個終わるか」を表していることになる。そうすると、貪欲に（できるだけ昔始まった区間から）消費していった方が良いというのは自然。
時刻: 0 件のコメント:
ラベル:

2023年10月8日日曜日

Educational Codeforces Round 151 (Rated for Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Boxes and Balls

　こたつがめさんの実況放送の振り返りを見てAC。

　コンテスト中、左端の1はどこからどこまで詰められるのだろう？　などと考えていた。大まかな方針はそれで良いのだが、「どこからどこまで」ではなく、全てのnについて試さなくてはいけなかった。

　各i in [0, n)について、何番目のボールをそこに置くか？　そうした場合の移動距離はいくつか？　というDPを考えると三乗のDPになり、それを枝狩りすると通る。

　三乗DP自体は自然なものなので、それは思いつかなくてはいけなかった。
時刻: 0 件のコメント:
ラベル:

yukicoder contest 340

　A一完で終了。


No.1909 Detect from Substrings

　解説AC。

　最初の二つの文字列から答えを絞るのがポイントだが、そのためには、「答えが少なそう」と気付かなくてはいけない。
　絞れると分かった後の考察も結構難しいが、「異なる最初の文字」に注目して考えれば良い。

　分かってしまえば難問という程ではないのだが、問題の見た目がシンプルなのに、腰を落として考える必要があるのが難しい。

No.1910 High Element on Grid

　$R_i$、$C_i$が、「A[j]がA[:j+1]の最大値になっているようなjの個数」を表していることは分かったが、その構築をどうやるか？

　……結構考えても分からず解説を見たが、あまりにも単純でびっくり。一行目一列目が特別だと気付いていなかった。
時刻: 0 件のコメント:
ラベル:

2023年10月7日土曜日

Pinely Round 2 (Div. 1 + Div. 2)

　pretestはEまで。

コンテスト後のツイート

F. Divide, XOR, and Conquer

　こたつがめさんの放送の振り返りを見てAC。
　いや以前に、この放送や公式解説を見たときは分からなくてしばらく放置していたのだけど、今もう一回きちんと見たら理解できた。

　区間DPでいけそう、と言われればそういう気はしてくる。（n=10000でも想定計算量が二乗の可能性があることに注意しよう）
　ただ、区間DPが二乗で済むと思いにくいし、また、空間計算量が線形で済むと気付きにくい。

　区間DPでいけると言われれば自然な解法に思えるが、それでいけるとは思いにくい問題な気がする。

・Sを累積xorとする。
・最上位bitに注目するのは自然。
・長さが長い区間から区間DPしていく。

・[l, r]でS[l]とS[r]の最上位bitが同じなら、[l, n], [n, r] for any n（ただし、それぞれの区間は元のものより短い）に遷移できる。

・[l, r]でS[l]とS[r]の最上位bitが異なるなら、そのbitをxとすると、[l, n]に遷移できるのは、S[l]^S[n]のx bit目が異なるとき（[n, r]も同様）。これを覚えておきたいが、そのとき、「S[l]が左端になるときは、右端とx bit目が異なれば良い」とさえ覚えておけば良い。

・この後、xと異なるyについて、「S[l]が左端になるときは、右端とy bit目が異なれば良い」を覚えておきたい状況が存在するかもしれない。そのため、(1<<x)|(1<<y)と記録しておけばOK。



時刻: 0 件のコメント:
ラベル: ,

yukicoder contest 407

　Cまで三完。


No.2495 Three Sets

　コンテスト後自力AC。

　A, B, Cを大きい順にソートしておき、それぞれ何個取るべきかを三分探索で求めたらACできた。
　コンテスト中にこの方針は思いついたもののあまり自信がなくて実装せず、コンテスト後に実装したらAC。

No.2496 LCM between Permutations

　WAが出て、WAが出たtestcaseを見てデバッグしてAC。

　(1, i)を全て聞いてみる。
　それで、Bの中に1があるところを特定できれば簡単。そうでなければ特定できたもののうち最も大きい素数を考え、そのindex indを使って(i, ind)を聞く。

　そういう感じで、AかBかで特定されていない場所が二個以下になるまで聞く。
　そうしたら、片方が1と分かるので、それを利用する。

　……みたいにしてACできたが、多分、Hackできますね。（多分できなそう。追記しました）

　解説を読むと、N/2より大きい素数の位置がN+1回あれば見つけられることを利用していた。そういう素数の位置が分かると良いことには気付いていたが、N回で見つけられなかったとき、もう一回で見つけられるとは気付いていなかった。なるほどです。

　（追記）
　自分の解法は正当な気がしてきた。N/2より大きい素数をpとして、(1, i)を全部聞いたとき、A[i]=pならばBは二要素以外全て明らかになる。それ以外だったら、Bの中のpが最大の素数になる。
　だから、正しそう。

No.2497 GCD of LCMs

　解説AC。

　一般グラフの単純パスたちの持つ性質を考えるという問題が、ダイクストラで解けるとは考えもつかず、結構びっくりした。

　とはいえ冷静に考え直すと、一般グラフのサイクルとかを扱うのは難しい（サイクル基底を使う、とかはあるけれどそういう問題ではなさそう）し、何か上手いことをして最短距離問題に持ち込むくらいしかないのかもしれない。
時刻: 0 件のコメント:
ラベル: ,

2023年10月5日木曜日

yukicoder contest 390

　Eまで。

コンテスト後のツイート

No.2319 Friends+

　解説AC。

　解説で、bitsetで解けると書いてあったので、その方法でAC。
　平方分割を使うのだろうと考えていて、実際それでも解けるのだが、bitsetを使えることも思いつけなくてはいけませんね。
　ただ、高速な言語ではbitsetで通せても、PyPyなら平方分割するしかない、という場面もあるのだから、平方分割でもちゃんと解けなくてはいけなかった。

　友人が多いか少ないかで場合分けするとは思ったけれど、その生かし方が分からなかった。そこは冷静に考えるしかないのだが。
時刻: 0 件のコメント:
ラベル: ,

2023年10月3日火曜日

yukicoder contest 391

　ABの二完。


No.2336 Do you like typical problems?

　自力ACしたが、非常に時間がかかってしまった。難しい問題ではないと思うが、大まかな方針が立った後、立式しても自分が何を求めているか分からなくなってしまう……。

　想定解とほぼ同じ方法だが、想定解でいもす法を使っている部分で、平面走査を使っている。
　TLEできつくなってしまったのはそのせいなのだろうか？　定数倍高速化を頑張ったらACできた。

No.2337 Equidistant

　解説AC。
　大体の方針は分かったが、LCAがちょうど間にあるケースを考え損ねていた。典型だけど、そのケースを見逃しやすい。

　ダブリングによるLCAを久しぶりに実装した。ライブラリに入れておこう。
時刻: 0 件のコメント:
ラベル: ,
登録: 投稿 (Atom)