ABC284 (2023/01/07)
〇A問題
Yuto.icon reverseしてprint
TK.iconいったんリストに追加して、スライスで逆順に表示
おたふく.icon TK.iconと同様
CarpDay.icon上2名と同様
wataumi.iconいったんリストに追加して、後ろから順に表示
TTT.icon for文で逆順に表示しました。
sakana.iconyuto.iconさんと同様
〇B問題
Yuto.icon a%2==1の個数を数える
wataumi.iconYuto.iconと同様
TK.iconリスト全体を％２でmapして１の個数を調べた
おたふく.icon a%2 != 0の個数を数える
CarpDay.icon a % 2の合計を求めた
TTT.icon for文でM回まわしながら順次a%2==1の合計を表示しました。
sakana.icon読み込みながら％２してカウント
〇C問題
Yuto.icon UnionFindしてi==find(i)をチェック
TK.iconありがとうUnionFind
おたふく.iconUnionFind最高。find(i)の数値の種類で連結が何個か判断
CarpDay.iconこのサイトにUpしていたUnionFind使って，uf.group_count()したら結果がおかしい．．．0-indexなのか1-indexなのか，曖昧なクラスになっていましたね．0-indexで使うよう修正しておきました！
おたふく.iconindexを変更し忘れてました
wataumi.icon以降、分かりませんでした。DFS？UnionFind！ 悔しいです。
TTT.icon sample01しか通せませんでした。以降手をつけていません。
sakana.iconUnionFind使った
〇D問題
Yuto.icon 事前にエラトステネスの篩で素数列挙(Nが高々9*10**18なので，素数リストは10**7くらいまであればok)して，各クエリでNを素因数分解．指数部が2のやつを見つけたらそれをpとしてq=N//p//pでqを作ってqが素因数に含まれてたらp,qを出力．出来た！！！と思ったらWAとRE祭り．おそらくp,qが見つからないケースがあったっぽい(printせずに次のinputしようとしてRE)．なぜ．．．結局コンテスト中に通せなかった
コンテスト後，無事にAC．コーナーケースは(2)*(2)*(10**18)などで，この場合は素因数分解できない．この例だと，2を素数リストから探して，10**18の部分はn//2//2より求めればよい．素因数分解の計算量が$ O(\sqrt{n})なので10**18の素因数分解はそもそも出来ないことに気付くべきだった．
TK.iconエラトステネスでテストケースの最大の数字の3乗根までの数字の素数を用意。それをもとにとりあえず最小の素因数をひとつ見つける。その後、まだその数で割れるなら、割ってもう一つを取り出す。割れないなら残っている数の平方根をもう一つとして取り出す。最初にできたプログラムで行けていると思ったが10件ほどWAに。powを使っていたので今回は計算誤差出るパターンか？と思いintのキャストをしっかり四捨五入してやったらACになった。（またやらかしていませんように...）
おたふく.icon事前に素数を用意するためにscrapbox内のエラトステネスの篩を拾ってきて実装を試みると、sprapbox内のメモに誤字が含まれていたので修正しておきました。またYuto.iconと同様に素数リストを10^7まで用意すれば良いと思ったが、その素数リストで素因数分解は出来ないことに気付かずWA。制限時間終了後の数分後にAC...。
CarpDay.icon修正感謝
CarpDay.icon2つ上の方とほぼ同じ方法．ICPCよろしく，まず3×10^6までの全素数を列挙しておきました．後者のケースでp = int((n // q) ** (1/2))としたが，誤差で1小さくなるケースが気になって，p * p == n // qの場合と(p + 1) * (p + 1) == n // qの場合を想定しましたが，四捨五入の方がスマートですね．
〇E問題
Yuto.icon 与えられるGraphが木だったらいいのになー(木DP？)と思いながら，効率よく個数を列挙する方法を考えていたけど無理だった．
TK.iconグラフだ、UnionFIndしとくか？と思ったが、結局その先の方針がわからず、Fに行ってみた。結局Fがわからず最後の10分ほど戻ってきたが、考えているうちに終了。
CarpDay.iconbitDPかとも思ったが，その割には点数が多すぎ．問題サイズ的には，BFS/DFSのサイズだなぁと思いつつ，最後まで方法を思いつかず．終了後に解説見たら，やっぱりDFSでしたか．．．ポイントはDFSの1つの探索点が1つの単純パスになることに気付くことでした．問題設定が不自然なのは気になっていましたが．．残念．
〇F問題
Yuto.icon ちらっと覗いてみたけど(文字列アルゴリズムちゃんとやったことなくて)無理そうだったのでDに戻った
TK.iconテストケースの文字列をもとに、実際に手で調べてみたが、区切る場所を前から順に探索していては効率が悪い。何かうまくできるやり方はないかと探していたが結局わからなかった。
CarpDay.iconE問題お手上げのため覗きに来る．問題は理解できるが，O(|S|)の方法が思いつかず，E問題に戻る．終了後解説見ました．Zアルゴリズム初めて知りました．勉強します．