ABC286 (2023/01/21)
〇A問題
Yuto.iconスライス使って一気に入れ替えた．添え字をバグらせて少し手間取ったけど一発AC
CarpDay.icon元のリストaから変更後のリストbを作成．WA！ええ！？リストのまま表示してました．．
おたふく.iconスライスを使ってまとめて入れ替えた。リストのまま表示してWA!!
TK.iconスライスを使って一度ｂを作成した。
〇B問題
Yuto.icon S.replace("na", "nya")
CarpDay.icon上に同じく．B問題の方が簡単（Pythonだから？）．
おたふく.iconreplaceを思いつかなくて1文字ずつ追加していき、条件を満たすとき先にyを追加する。という実装をしました。
TK.iconn->aで続いていた場合aでなくyaを表示。
〇C問題
Yuto.icon 分からなくて一旦飛ばした．D, Eが解けたのでコンテスト終了5分前くらいに戻ってきた．回文の中心位置を全通り試して，それぞれの場合で回文にするために必要なコストを求めればいいのかな？とか思ってたらコンテスト終わった.
CarpDay.iconC問題だから難しい訳ない！と15分考えるも，分からない．サンプル2を手で解くことさえできず，スキップ．D，Eの後に戻り，方法1を行う回数を全て試すやり方を試したら解けました．久しぶりの5問AC(^^)
おたふく.icon10分前くらいに回文にするための全パターンを試しても計算時間が足りることに気付いたが、上手く実装出来なかった。後日、少しだけ間違っているところを発見。
TK.icon方針が立たなかったため一度D問題へ。そのまま戻ることはなかった
〇D問題
Yuto.icon 見た瞬間DPだ！解けそう！と思ったけど思ったよりも苦労した．
CarpDay.iconつい昨日最後に扱った個数制限なしナップサック問題の個数限定版．昨日限定版も復習しておけばよかった．計算量心配だったけど，なんとか無事AC．おたふく.iconの方法がシンプルでいいね．
おたふく.icondpには気付けたが、実装の仕方が最初思いつかず時間がかかってしまったのが悔しい。CarpDay.iconから頂いたdpの冊子のA18を参考にさせてもらいました。
TK.iconｄｐだ！やってやろうと思い、すべての時間を費やして何とかクリア。はじめは数値を持たせて考えていたが、boolを値として持っておき、枚数はループで処理。基本はi種類の硬貨で数字jが実現できるかという方針でやった。できた！クリアだ！と思ったが5件TLE。枚数に関するループの位置が悪かったので修正したが直らず。ぎりぎりでPyPyでやったらいけるかもと思い提出してみたら、残り数十秒でAC。危なかった
〇E問題
Yuto.icon 全頂点対最短経路→ワ―シャルフロイド (計算量的にも$ O(n^3)間に合いそう)と思ってワ―シャルフロイド書いたけど，そういえばお土産を考慮できないな..となった．そこで，隣接リストを作って全頂点からダイクストラをして，ついでにお土産も考える方針に変更．実装すると，答えは合ったけどTLE．必要な分だけダイクストラをするように変更したら無事にAC(約100分)．解説見たらワ―シャルフロイドでも解けるっぽい．落ち着いて考えれば確かにそうか..
CarpDay.icon全頂点からダイクストラしました．ヒープに距離とお土産の両方を入れました．
〇F問題
Yuto.iconこれ以降見てない
CarpDay.icon少し覗いただけ．終了後に考察して，長さ素数のサイクルを使うことまで思いついたが，Nを導出する方法が分からず解説を見る．中国剰余定理ですか．．聞いたことあるので，この機に勉強します．
〇G問題
Yuto.icon コンテスト後にチラッと見た。UnionFindで解けそう？