ABC245参加記
お気持ち重視で解法への進み方等書いていきます
解説ではないので議論がゆるめ＋解いてない問題もあります
総括
もったいないミスはありましたが、まあいい感じですね。パフォーマンスは2050くらいです。
A問題
if文で判定するだけ。時間の前後は頭がこんがらがるので、hour*60 + minuteで分に変換してから判定するようにしています。
B問題
mexというトピック自体はD以降でたまに出会いますね。
解法はいろいろありますが、setに出現したものを入れて最後に0から増やして判定しました。
C問題
一瞬ぎょっとしますが、最後の一つだけわかってしまえばそのあとにつなげられるかはわかります。なので、「最後がある値のとき達成可能か？」という情報を使ってDPします。DPでは遷移するときにどんな情報が必要かに着目するといいかなと思ってます。
D問題
今度は問題文の見た目がかなりいかついですが、単純に多項式を展開する操作を示しています。高校数学の基礎って感じですが、展開した後の次数がxになるものの係数がどうやって決まるかを考えると、やることはそんなに難しくないです。
端っこから決めると毎回の決定の時に未知数が1つだけになるのでうまくできます。ただし、除算が発生するのでここで0除算をしないように気を付けないといけません(1敗)。あんまりアルゴリズム！！って感じではないですね。
E問題
直接出題されたり、より難しい問題の部分問題として何回も出題されている典型問題だと思います。
・順番が関係ないときはソートする(1つ考えることが減る)
・貪欲では「こうすると損しない」を考える
・選択肢の少ないところから考える
この3つはほかの問題でも応用できる典型要素だと思います。
具体的なアプローチはいろいろあると思いますが、こんな感じで解きました。
・チョコレートと箱それぞれを、縦の長い順にソート
・大きい方からその時使える箱をリストアップする
・箱に入れることができるなら入れる、このとき最も横幅がぎりぎりのものを使う
縦の長い順にソートしたのは、長いチョコほど箱の選択肢が少なくて決定がしやすく、小さいチョコは大きな箱にも入るので、先に大きなチョコを入れても後で困らないなというイメージからです。
実装としては横幅をmapやmultisetなどでもってlower_boundを用いるとそれぞれのチョコに対してO(logM)で処理ができます。setやmapのlower_boundは適切に使わないと計算量が増加することがあるので注意が必要ですね。
F問題
有向グラフで「移動を繰り返す」とあるので、強連結成分分解(SCC)がパッとでてきます。強連結成分分解を知らないと解くのは難しくなりそうです...。
まず、ある頂点が「頂点数2以上の強連結成分」にあるならそこで動き回ればよいのでOKです。そうでない時を考えてみましょう。結局「頂点数2以上の強連結成分」にどこかでたどりつければそこで動き回ればよく、そうでなければどこかで詰まって止まってしまいます。なので、「ある頂点から適切にグラフをたどって、頂点数2以上の強連結成分にたどりつけるか判定せよ」という問題になります。
C++erならAtCoder Libraryのsccを用いると実装が簡潔になるでしょう。これをすると強連結成分ごとの頂点のリストを返してくれるので、これを使って強連結成分を1頂点に圧縮したグラフをつくります。
このグラフからどうやって探索するかですが、葉に当たる部分は「頂点数2以上の強連結成分」にたどりつけるかどうかすぐにわかります。なぜなら、そこから進める場所がないからです。逆に根に近い部分はどの道をたどっていけばいいかわかりません。
これもEと同じで「選択肢の少ないところから考える」ことがうまくハマります。グラフの葉にあたるところから戻っていく向きで更新していけばよいことになります。更新の仕方はDPやDFSなどが考えられます。
G問題
解けませんでした...。まずいろいろ条件が多いのですが、「自分と異なる国の人気者」というのが厄介でこれがないバージョンを考えてみます。それがなければ、それぞれの人気者を始点とした多始点ダイクストラをすると、人気者への最短距離がわかるので解けることになります。
ということでこれをうまく活用できないか考えてみます。本番では(人、人気者の国)を頂点としてもったダイクストラを考えましたが、国が多い場合にTLE / MLEになります。適当に枝狩りをして通せないかと思いましたが、AtCoderのテストケースは優秀でしたね。
解説を読むと、「使えないのは高々1種類の国」ということから2種類の国だけもったダイクストラで解くという方法が紹介されていました。いわれてみれば確かにという感じでした。実際に実装もしてしっかり理解しておきたいと思います。
