yukicoder contest 390

　Eまで。

コンテストへのリンク

コンテスト後のツイート

yukicoder contest 390 Eまで。
B x,yが独立
C Union-find
D DP
E Nの約数とか素因数分解は前計算しておく。約数でDP。x→yの遷移では、xとyがともに素数pで割れる数が一致するとき、その個数をかける。

— titia (@titia_til) May 26, 2023

No.2319 Friends+

　解説AC。

　解説で、bitsetで解けると書いてあったので、その方法でAC。

　平方分割を使うのだろうと考えていて、実際それでも解けるのだが、bitsetを使えることも思いつけなくてはいけませんね。

　ただ、高速な言語ではbitsetで通せても、PyPyなら平方分割するしかない、という場面もあるのだから、平方分割でもちゃんと解けなくてはいけなかった。

　友人が多いか少ないかで場合分けするとは思ったけれど、その生かし方が分からなかった。そこは冷静に考えるしかないのだが。

Codeforces Round 889 (Div. 1)

　A1とCの二完。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 889 (Div. 1) A1とCの二完。
A1 大きい数を作ってそれで他を変えていく方針
B 二乗DPしか分からない！　二乗でも通るのかと投げてみたけどやっぱりTLE。
C A[i]がA[i+1]+xで消える確率を計算。折り返して場合の数を求めるのは覚えてたけど、細部が分からずカタラン数を復習した。

— titia (@titia_til) July 29, 2023

B. Earn or Unlock

　bitsetを使うと解けるらしいという情報を得てAC。

・問題が部分和問題に似ているので、DPするしかなさそう。

・（コンテスト中は）PyPyによるACがなく、C++でも実行時間が長いものが多い

　ということから、コンテスト中もbitsetの利用は疑ったはずなのだが、良い方法が思いつかなかった。

　実際は、部分和問題のときと同じ要領でDPテーブルを持てば解ける。

　DP[i]=1で、ちょうどindex iまで使える状態、ということを表すとすると、

・初期状態はDP[0]=1、他は0

・DP[i]=1のとき、iまでの累積和-iが答えの候補。

・DP[i]=1のとき、index i以降で1となっているものについて、DP[i+A[i]]=1と遷移させれば良い。これは、DP>>=i, DP|=(DP<<A[i]), DP<<=iのように表せる。

　となり、解ける。

　なお、現在はPyPyでのACもあるが、bitsetを書くのが簡単そうだったので久しぶりにC++を使ってみたら、昔ほど書くのに抵抗ない気がした。VSCODEを使ったら、いつのまにかボタン一つで実行できるようになっていたのも嬉しい（前はできなかったのに、なぜ？）。

Codeforces Round 870 (Div. 2)

　Dまで四完、と思ったらシステムテストでDが落ちた。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 870 (Div. 2) Dまで。
A 全探索できるけど何を全探索すれば良いか難しい。Aとしては難問
B 差のgcd
C nの最も小さい1でない約数<=m
D 右端全探索。左側からB[i]+iをつめていき、その大きい二つか三つが候補。
E 計算量n*n*mかかる気がした。高速化できず終了。

— titia (@titia_til) May 5, 2023

D. Running Miles

　システムテストで落ちたのは、B[i]+iが同じならindexが大きい方から優先して調べるべき、ってところを考慮してなかったためでした。そこを修正してAC。

E. Walk the Runway

　bitsetを使うと聞いてもピンと来なかったが、こたつがめさんの実況放送の振り返りを聞いたら理解できた。

　ただ、Python通常のbitset（普通の整数をbitsetとして使う）では通らず、64個ずつに分けて、0～(1<<63)の数字の配列をbitsetとして使ったらACできた。

　この方法、書いたことなかったので勉強になった。面倒かと思ったけれど、意外と実装するのは簡単だった。

yukicoder contest 384

　Cまで三完。

コンテストへのリンク

コンテスト後のツイート

yukicoder contest 384 Cまで。yukicoderで質問したの初めてだったかも。
A 丁寧に実装
B 乱択
C 全く分からず検索したら、e=Σ1/x!と表せるといわれ、それを利用したがWA。N=0が例外になる可能性には気付いたが、WAのケースが多かったので長いこと誤差を疑っていた。ACした後で質問した。

— titia (@titia_til) April 14, 2023

No.2270 T0空間

　愚直にやったらTLEした。解説にbit setを使うと書いてあったので、それでAC。

　bit set高速化は一回思いついたのだけど、なぜか違うと思って検証しなかった。もうちょっと掘り下げていれば解けたはずなので反省。

AtCoder Beginner Contest 258

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 258　Eまで五完
C 2 xというクエリが来る度、先頭のindexを-xさせると考える
D それまでで一番短いステージを使う
E ループするところを探す
Gがたくさん解かれていたのでFを飛ばしてGに行き、有名問題っぽいと検索していた。bitsetを使うのは考えたはずなのに……。

— titia (@titia_til) July 2, 2022

F - Main Street

　自力ACだが時間かかってしまった。

　（K=1の場合を除くと）スタート・ゴールそれぞれから、直線で大通りに出る4通りを考えれば良い。その16通りを考えて最短のものを出力する。

　(スタートから大通に出たときのx座標)/B=(ゴールから大通に出たときのx座標)/Bのときを気を付けるのが重要。このときはマンハッタン距離が答えにならないのに注意して実装する。

　基本的にはこれだけなのだが、自分が詰まったところを書いておく。

・if (スタートから大通に出たときのx座標)/B=(ゴールから大通に出たときのx座標)/Bのとき

・else if (スタートから大通に出たときのy座標)/B=(ゴールから大通に出たときのy座標)/Bのとき

　のように実装し、それぞれ迂回して行く最短距離を考えると、「(スタートから大通に出たときのx座標)/B=(ゴールから大通に出たときのx座標)/Bかつ(スタートから大通に出たときのy座標)/B=(ゴールから大通に出たときのy座標)/Bのとき」のときおかしくなる。

　このときはマンハッタン距離で良いことに長い時間気付けなかった。

G - Triangle

　解説AC。

　bitsetを使っても、bit_count(popcount)を高速化できないと意味がない。bit_countの高速化はこのスライドが詳しい（とtoamさんの解説に書いてあった）。

　予め63個ずつに区切っておき、それぞれについてこのスライドの方法でbit_countを求めるとTLEせず求められる。

Ex - Odd Steps

　解説放送を見てAC。

・Aを無視してDPを立式

・累積和を取ると式が簡単になる。行列累乗が使えそう

・A以外の部分は行列累乗で処理、Aのところだけ普通にDPする

　という流れ。

　上記のステップを経れば難しくないのだけど、Aが重要そうな問題で、Aを無視して処理することが解法に結び付くというのは意外だった。

　何も思いつかなければとりあえずDPを考えてみるのは重要か。