Codeforces Round #828 (Div. 3)

　E2が解けずに終了。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #828 (Div. 3) E2が分からなかった。
B 偶数と奇数の代表を1個ずつ処理。
C 何個先にgがあるか。
D 2で割れる回数が大きい方から使う
E1 a～cを全探索。lcmを使って処理。
F 範囲がxのとき、(x-1)/2以下の全ての数を含んでいればOK。indexの最小と最大を管理

— titia (@titia_til) October 16, 2022

E2. Divisible Numbers (hard version)

　解法ツイートを参考にAC。

　制約を考えると、約数・倍数の関係で絞るしかない。a*bの約数を使うはず、というところから進まなかった。

　正しい方針は、a*bの約数xをa～cで利用したいなら、a+1以上でxの倍数のうち最小のものを使うべき。これは求められる。同様に、yは、b+1以上でa*b/xの倍数のうち最小のものを試す。

　a～cの範囲でxを決めたとき最適なyを求めるためにはどうするか？　という考え方はE1でも使っていたのだから、約数の関係を利用して同じようにすれば良かった。多少焦っていたにせよ、これくらいは気付きたかった。

Codeforces Global Round 23

　Cまで三完と悲惨な出来。

コンテストへのリンク

D. Paths on the Tree

　解法ツイートを見てAC。本番中1500人近くも通していたから簡単なのかと思ったら、解法も実装も難しくてびっくりした。

・各頂点の重複度の最大値と最小値が高々1しか離れない

　と気付くのがポイント。

　これは直観的にそうだよね、と思いたい。

　頂点xの重複度がyで、子の数がcのとき、xの子たちの重複度は、y/cの切り捨てか切り上げになる。これを繰り返しても、（頂点1の重複度である）kを、pathをたどったとき現れる子の数c_1, c_2, ...の積で割ったものの切り捨てまたは切り上げになる。割り算の式から不等号を導けば、証明できたが、そんなことをしなくてもまあ直感的に（あるいは知識として）正しいと分かっておきたいもの。

　これを利用して木DPすれば解けるのだが、実装もなかなか大変だった。

　

E1. Joking (Easy Version)

　解法ツイートを見てAC。

　0, 1, 2の3要素が残ったとして、

・｛1,2｝を聞く

　→”NO"なら{1}を聞く

　　　→"YES"なら{1,3}に、"NO"なら{2,3}に絞れる

　→"YES"なら再度{1,2}を聞く

　　　→"YES"なら{1,2}に絞れる。"NO"なら最初に"NO"が来たときと同じ手順を踏む

　とすれば三回で2/3くらいになってACできる。

　試行錯誤するしかないけれど、Aと￢Aを質問するのは意味が変わらない、ということには早く気付くべきだった。そうすれば、三等分するという方針には早くたどり着けたと思う。（が、三等分してからも難しい。コンテスト中も三等分することは一応考えたけど、その後が思いつけていないので……）

yukicoder contest 364 (Do you know Cherry Contest?)

　Eが解けずにマラソンへ行き、マラソンが10位。 通常（アルゴ）のコンテストにマラソン問題が混じっているのは好き。

コンテストへのリンク

コンテスト後のツイート

yukicoder contest 364 (Do you know Cherry Contest?) Eが分からなかったのでマラソンに行った。
C 過去への移動回数を探索。
D 減ったとき、増えたときでの最大scoreを持つDP
F ロリハ

— titia (@titia_til) October 14, 2022

マラソンの最後の提出が135……まで伸びてびっくり。
(x, x, x)という形なら点数調べるの簡単なので、この場合に限定して乱択しました。xは1～6の範囲にしたらsampleの点数が一番が高くなったのでそれで。

— titia (@titia_til) October 14, 2022

No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに

　解説AC。

　イベントソート（平面走査）だとは思ったが、何を管理すれば良いかが分からなくなってしまった。

・元の数列の値（減り終わったら0に更新する）

・減り始める時間

・減る途中のものの個数

　を持って、減り始めるときと、減り終わるときにupdateするようにすれば、答えを求めることができる。

　イベントソートという方針自体はすぐ思いついたので、時間があれば解けたとは思うが、何を管理すれば良いか考えるのはいまだに苦手。とはいえ、解けなくてはいけない問題でした。

　なお、PyPyだと（意外と）制限時間が厳しく、セグ木の関数で内包表記を使っているとTLEが取れなかった。PyPyだと内包表記が遅いのには注意。

ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)

 　ABCEFの五完。

コンテストへのリンク

コンテスト後のツイート

ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268) ABCEFの五完。
A len(set(A))
C Q[P[i]]=iなる配列を考えると分かりやすい。
E 差分計算。難しいがやることは分かるので頑張る。実装で双対セグ木を使った。
F (a,b)=(xの個数,数字の和)とすると、a/bでソート。

— titia (@titia_til) September 10, 2022

最後、DでWAが取れなかったけど、DのWAの原因はN=1の場合分けをしていなかったためでした。
テストケースの名前見てはじめて気付いたので、最初D飛ばしたのは正解。

— titia (@titia_til) September 10, 2022

 G - Random Student ID

　解説放送を見てAC。

　あんまり自分で考察しなかったけど、考察ができてもTrie木を使うことを思い付けたかどうか。Trie木を使わなくても上手くソートすれば解けそうだけど、実装で苦戦してしまいそう。

Ex - Taboo

　解説放送を見てAC。

　Aho-Corasick法を勉強しました。

　もっと難しいかと思っていたけれど、結構理解しやすいアルゴリズムでした。

　

Codeforces Round #827 (Div. 4)

　Rustで出て全完。時間はかかったが、Rustで全完できたのは良かった。

　→システムテストも全部通ってた。結構Hackが出てたので心配していたけど、通って安心。

コンテストへのリンク

コンテスト後のツイート

F tにa以外が現れたらYES。otherwise sにa以外が現れたらNO。sもtもaのみのときは長さを比較。
G 使っていない中で最大のものを使う。使ったやつのbitはもう見ないので、((1<<32)-1)^xで&する。

— titia (@titia_til) October 13, 2022

AtCoder Regular Contest 149

　Cまで三完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 149 Cまで三完
A 全探索できることにずっと気付かなかった。
B 片方をソート
C 3で割った余りが1,2のものを並べた後、適切に3の倍数を並べる。1+2が素数に気付かずWA。素数の最大値が10^6（正しくは2*10^6）としており3WA。
D マージテクだよね？　と思うもバグらせて終了。

— titia (@titia_til) October 2, 2022

D - Simultaneous Sugoroku

　解説AC。

　いわゆるマージテクではなかった。

・Xの範囲が小さいので、区間[1,10^6]の全ての答えを求めても良い

・区間を最小値・最大値で管理する

　の二つがポイント。

　ただ、一つ目を思い付けば二つ目は自然か。

　Xの最大値が大きくないことに注目して、データを扱いやすい形で持ちたい、と考えれば一つ目の考え方も自然。

　そもそも数学では、「一般化した方が扱いやすくなる」問題は多いのだから、一般化できないか？　と考えてみるべきでした。

　なお、テストケースが弱い模様。

　木の根から答えを反映させるって処理をサボって、各座標ごとに子孫がどこへたどりつくか調べるのを投げてみたら通ってしまいました。

yukicoder contest 341

　ABの二完。

コンテストへのリンク

No.1917 LCMST

　解説AC。

　一見手がかりのない問題だけど、最小全域木を作る方法は普通はクラスカル法かプリム法なわけなので、

・最小全域木を作る方法としてクラスカル法を用いよう、そのために、辺の候補を絞り込もう

　と考えるのが重要。

　そして、最小公倍数が問題になっているのだから、約数・倍数の関係を用いて絞り込むのだろうな、と考えれば（証明はともかく）解説の方法を思い付くことは可能そう。

　難しいけど、多分こうだろうな、という考察を推し進めていけば思いつけない問題ではなかった。