ABC288 (2023/02/04)
〇A問題
Yuto.icon a+b
TTT.icon for文をN回まわして随時入力と出力を行いました。
TK.iconおたふく.iconCarpDay.icon↑に同じく
〇B問題
Yuto.icon 最初， 辞書順で上位K人 のハンドルネームを答えるのだと勘違いしていて，めちゃくちゃ沼った．落ち着いて問題文を読み直すと 上位K人 のハンドルネームを辞書順に出力するって書いてるやん．．．B問題に10分以上かかってしまった...
TTT.icon S_ = S( :K )としてからS_.sort( )して、改行はさみながら出力しました。
おたふく.icon問題文をよく読むことを胸に刻みたいです。
CarpDay.iconスライス＋ソート
TK.iconpythonだと文字列もソートができて便利ですね。スライスとソートで終わり
〇C問題
Yuto.icon みんな大好きUnionFind．B問題の鬱憤を晴らすかのように2分弱でAC．素晴らしい
TTT.icon 今日は日中用事があってunionFindの勉強ができておらず、コンテスト中に勉強するも間に合わず無事トラウマと化しました。unionFind理解したところで一本ずつ辺削除して閉路あるか探索するの難しそうだとコンテスト中に考えていましたが、コンテスト終了直後に上記の先輩の解答を拝見して、閉路、すなわち根の個数がそのまま答えとして扱えて、別に探索する必要はないということを学びました。
おたふく.iconみんな大好きUnionFind。自分は根の個数ではなく、unionする際に閉路となってしまうときの辺の本数で求めた。
CarpDay.iconグラフ理論の良い問題．閉路なし＝森．各連結成分において，枝数＝点数 - 1．連結成分数をCとすると，各連結成分における上式の両辺を合計して，森の枝数＝全点数(N) - C．したがって，Union-FindでCを求め，M - (N - C) が答え．
TK.iconUnionFindですでに同じグループの頂点同士をつなごうとしたときに、つなげずに消去する辺のカウントを増やす
〇D問題
Yuto.icon range query→セグメント木？と思ったけど区間加算なら遅延評価セグメント木じゃないとダメ．遅延評価はまだライブラリ化してないなぁと思いつつ問題文眺めていたけど，そもそもセグ木で何を値として持つのか上手く設計出来なかった．
解説読んで理解して実装した．言われてみれば納得は出来るけど，コンテスト中だとそもそもmod Kでまとめるという発想すら出てこない．難しい...
TTT.icon DはNの条件から計算量削減の問題だと勝手に踏んで、Cに没頭しました。以降見ておりません。
おたふく.icon手計算で頑張ったが、規則性を見出せず...。解説を読んで理解して実装したが、時間内にこれに気付いてかつ実装を完了出来る気が全くしない!!!
CarpDay.iconアルゴリズムを考えたが，正しく動作するものが思いつかず終了．解説読んで納得．(1)不変量を意識すること．(2)等価の問題に変換すること の重要性を学びました．
TK.icon惜しいとことまでできた気がする。座標みたいな感じで書いて点のばらつきを考えたら法則性を発見！これはいけただろと思い実装。サンプル1は通るがサンプル2のクエリ１と２の結果のみ合わず、修正を考えているうちにタイムオーバー。時間中に考えたところまでの状態を提出しておきます。「追記」提出してみたらほとんどTLEが出ていたので方針自体違うみたいです
〇E問題
Yuto.icon ぱっと見てdpかな？と思った．最初はdp[i][j] := i番目までの商品を考えた時，j個購入した時の費用のminみたいな感じで考えていたけど遷移が上手くいかない．dp[S] := Sを購入した時の費用のminとbitDPで考えてみたりもしたけど上手くいかない．そのままコンテストが終わってしまった．．
解説読んだ。dpを2回やると上手くいくんですね。メインのdpの係数を前処理でdp的に求めるという発想が無かった。
別の解説でcostをセグ木使って求めているのがあった．区間のminなので確かにセグ木でも良さそう．計算量は$ O(N^2 log(N))なので$ log(N)だけ重いけどぎりぎり行けるかな？→PythonでもPyPyでもTLE．．．やっぱりインタプリタは遅い
CarpDay.iconD問題に詰まって少し検討．DPと確信したけど，「売れ残った商品の中でi番目」という追加費用の扱い方が思いつかず諦める．解説見て，追加費用の扱いの考察に感銘．全商品を購入する例を考えたら，解き方思いついたかも．比較的容易に解ける問題例から考えること の重要性を学びました．
TK.iconぱっと見dpっぽいと思ったが、D問題を解くと決めて考えていたためちゃんと見れていない
おたふく.iconビットdpかつ配るdpを駆使して一応答えが求められるコードは完成したがTLE...予想通りではあったが。
〇F問題
Yuto.iconDもEも難しかったのでここまで見に来た．暫くにらめっこしてたけど方針すら立たなかったのでEに帰った．
CarpDay.icon同じくD・E解けずにFを見る．素直に桁数を順に増やすDPだと気付くも，1回の遷移での処理をO(N)で行う方法が分からず諦める．解説見て，もうひと頑張り考察しておけばよかったと反省．数値例でじっくり考察して法則性を見つけ出すこと の重要性を学びました．
TK.iconDの方針が立ったため、これ以降見に来てすらいない
〇G問題
Yuto.iconこれ以降見てない
CarpDay.icon↑に同じく．今回は悲しみの3問AC．でも5問ACの先週とパフォーマンスは大差なく，レートも微上昇で一安心．AtCoderトップページ内のABC288の案内に，「今回のD問題以降は難しめ」と書いてありました！