ABC280 (2022/12/03)
〇A問題
Yuto.icon 入力を配列として持たずに処理した．メモリ節約して偉い
TK.icon 読み込んで数える。前回も登場していた文字列に対してcountを使って結果に加算していった。
sakana.icon読み込んで、for文で数えた。
CarpDay.icon前回のAと同じく，countメソッド使用．
TTT.icon 前回知ったcountメソッドを使ってできました。
〇B問題
TK.icon階差数列
sakana.iconAi = Si -∑Aという感じで求めた。
Yuto.icon sakanaと同じく，A[i] = S[i] - sum(A[:i])で求めた．nが高々10なので計算量は考えなくて良い．
CarpDay.icon問題読み違えて，サンプルで間違い．修正してAC．終了後に改めてコード見たら，正に階差数列でした．
TTT.icon ぱっと見Cのほうが簡単そうだったので先にCに取り組んで、Cが上手くいかなかったのでBに戻ってきて実際に手を動かして考えたらすぐに解けました。先にBに取り組むべきでした。
〇C問題
Yuto.icon 前から見て行ってS[i] != T[i]のiを出力すればok．例外処理として，S==T[:-1]の時はlen(T)を出力する．簡単すぎて合ってるのか不安になった．
TK.icon前回もあった転置して縦列で比較を練習がれら実装してみようと思ったが、文字の比較ではS=aaa,T=aaaaが反例であることが判明。さらに、次の実装ではS = aabb T = aabbbが反例であることがわかり、いろいろ甘かった。
sakana.iconS[i] != T[i]で比較したものの、abcとabccのように最後に挿入した時に上手く処理してくれなかったため、SとTが前から部分一致していたらTの文字列の長さを表示するように条件を加えたらAC。（Sが１文字たりなくて空の要素と比較することになるから？）
CarpDay.icon一番上の方と同じ．これでC問題？？と不安に．．
TTT.icon TLEでコンテスト中にACにできませんでした。みなさんのプログラムを拝見して、方針は合っていたみたいです。S : i != T : i のようにスライスで全部比較させていたのが時間オーバーの原因だったのかなと。すなおにS i != T i のように一文字ずつ比較するよう書き換えたらACになりました。 〇D問題
Yuto.icon 最初，素因数分解して最大のbaseが答えだと思ったけどWA．冷静に考えるとk=30=2*3*5の時は5だけどk=90=2*3*3*5の時は6が答えなのでこの解法は誤り．なんか規則性とか無いかなーと考えてたけど無理だった．
コンテスト後解説を見て通した．素因数分解と二分探索は良いとして，ルジャンドルの定理を知らないと二分探索の判定関数の実装に苦労しそうだなーと思った．
CarpDay.icon先に別解読むと，解説分かるよ
Yuto.icon別解も読みました．コンテスト中にKが10^6より大きい素因数を持つかで判定できるか(そんなことに気付けるか)はさておき，この方針は分かりやすいですね
TK.icon最大の素因数が答えになりそうだなと思ったが、そもそも素因数を返すプログラムの実装に時間がかかった。エラトステネスの篩で候補の素数をしぼり、その中から素因数になるものをリストにするという形式で頑張ってみたが、やっているうちに例外に気づき、実装途中に時間切れ
CarpDay.icon最大の素因数が答でない反例を見つけ，それに対応できるロジックが思い浮かばず，E問題へ．その後戻るも，思いつかずに終了．コンテスト後も熟考したが，観念して解説読む．TLEになりそうで諦めた方法で合っていて，実装したらあっさりAC．素数や約数は直観より少ないため，意外に計算量が少ない．計算量多くなりそうでも，この分野はベタに実装して何とかなることも多そう．
sakana.icon素因数分解してその最大値を求めれば良いと思ったけれど半分くらいWA。違うパターンを考えたけれど時間内には解法が思いつかなかった。
TTT.icon コンテスト中に問題を見てなかったのでコンテスト後に取り組んでみました。N,N!,Kを実際に書き出しても規則性がつかめなかったので紙の上から進んでおらず、実装すらできませんでした。
〇E問題
Yuto.icon 見た瞬間期待値dp，逆元だ！と思ったものの，実装出来なかった．添え字と値に持たせる情報が上手く設計出来なかったのが敗因．
コンテスト後，解説を見た．二分木っぽく(漸化式的に？)考えていたのは良かったが，そもそも期待値の計算が間違っていたっぽい．期待値の計算をちゃんとしたら通った
CarpDay.icon以前作ったModIntライブラリの出番！と思ったが，それ以前にO(N)で求める方法が思いつかず．．．解説見て，DP更新がO(N^2)でなくO(N)で済むことに気付く．無念．．．実装したらすんなりAC．むっちゃシンプル．コンテスト中に気付きたかった．．．
〇F問題
Yuto.icon コンテスト後，問題を見た．クエリが来る前に前処理で全頂点対最短経路を求めておくのは$ O(V^3)だから無理だし，クエリ毎に最短経路求めても$ O(QE)くらいかかりそうだし，普通に最短経路問題として解くのは難しそう...となった．nan, infは閉路検出(Union Find)で出来そう．→ 解説見たら重み付きUnionFindを使ってた．そんなのがあるんですね．
CarpDay.iconD問題・E問題に詰まって覗く．ベルマンフォードでいけるか？と思ったが，O(VE)なので無理そう．諦めてD問題に戻る．コンテスト終了後も思いつかず，解説を確認．考察できれば実装は難しくなさそう．考察「できれば」だが．．