ABC335 （2024/01/06）
〇A問題
Kaplam.icon4に書き換える所を3に書き換えました！
yuichang.icon最後だけ別出力
kakip.icon最後を変える
tako.icon適当
まーす.iconスライスして後ろに+"4"
おたふく.icon スライス
TK.iconスライス。いつもはしない1行コード。
Yuto.icon 今回は初めて，全部の問題をRustで解いてみた．
CarpDay.icon TK.iconさんと同じ
〇B問題
Kaplam.icon3重回す
yuichang.icon 3重ループ
kakip.icon同じく3重
tako.icon以下同文
まーす.icon おたふく.iconTK.iconCarpDay.icon 同上．
Yuto.icon Rustらしく，美しい実装が出来た
〇C問題
Kaplam.icon解き方はすぐわかったけど2次元のデータappendするのに混乱して時間かかった、普通にlist2個作ればいいだけだった
yuichang.icon頭の位置だけ保持しておけば良
kakip.iconリストに頭がどう移動するか記録
tako.icon おたふく.iconCarpDay.icon リストに次の頭の場所を積んでいく
まーす.icon1 Cのとき，頭がどこに移動するかを追加．LとすべきところをRとしていたり，キャストの初歩的なミスに気づかず大幅ロス(WA２回)．
TK.icondequeのappendleftでインデックスを考えやすくしたが、一件だけTLE出ちゃった。めんどくさがらずに後ろにappendしていけば良かった；；
Yuto.icon 最初制約を見ていなくて，愚直シミュレーションを書いた．サンプルを実行中に無理やんと気付く．
〇D問題
Kaplam.icon巻くだけ
yuichang.icon巻く
kakip.icon出力例と同じように巻く
tako.icon巻き巻き
おたふく.icon とぐろを巻く龍.
TK.iconみんなと同じく巻き巻き作戦
CarpDay.icon 外から内側に巻く
Yuto.icon 噂には聞いていたけど，Rustでgridの走査がものすごく面倒だということを痛感しました．
〇E問題
Kaplam.icon同じ数字への遷移を考えてから大きい数字を見てく感じでTLE77
yuichang.icon 狭義単調増加だと誤読してたので普通のダイクストラで何故通らないか理解できず、困惑してた。広義らしい。dfs帰りがけ使って全パスを列挙したときにTLEと同時にWAが出てた意味をよく考えればよかった
おたふく.icon dfsをするもTLE。dfsってO(V + E)のはずなのに...。
kakip.iconコンテスト中は整数の合計が得点になると勘違いしてて無理だと思ってとばした。UnionFindを使って、Aiが同じで直接つながっているところをひとつにまとめればあとはDPで解ける。実装が難しい
Yuto.icon ダイクストラみたいに，番号が小さい頂点から順番に確定させていけば良さそうだけど，Rustのデータ構造がよく分からなくて沼った．
通った頂点集合をどうやって管理するか悩んでたけど、通る頂点がユニークになるようにすれば良かったのか…悔しい
CarpDay.icon 終点のAが始点以上となる有向枝によるグラフを作り，(A[i], -点数)の小さい点から順にダイクストラ風に点数を更新．サンプルはすべて通るも 32/95WA．このコメント書き終わったら，神が降りてきた．始点から到着できない点は処理しないことに対応して無事AC．コンテスト中に気付きたかった．残念．解説見たら，別解と同じ方法でした．
〇F問題
Kaplam.iconDPっぽいことだけはわかってE行った
kakip.icon後ろからパターンを数えていけばいいけど普通にやるとO(N^2)で間に合わなかった。合計をa_iとi % a_iの組ごとに記録してAC。計算量はおそらくO(N^1.5)
CarpDay.icon コンテスト中は Kaplam.iconさんと全く同じ行動でした．翌日考える．単純な配るDPだとO(N^2)になる，と悩む．各点に到着したときのホップ数とその回数を保存すれば効率よくなるか？と思って実装するも，16/63でTLE．勉強会まで，解説と上の隠し文字読まずに臨みます．