ARC106の感想

AtCoder Regular Contest 106に参加しました。

問題はこちらから。

Tasks - AtCoder Regular Contest 106

結果はこんな感じです。

1756 / 4352、パフォーマンスは1058で、パフォーマンス1000を達成できました。直近のコンテストは揮わない結果でしたので、今は素直に嬉しいです。

問題の感想を書いていきます。

A問題は

3^a + 5^b = n

を満たす、a, bを求める問題。制約が

n<= 10^18

でしたので、計算量をどうするかなどを考えるのに5分ぐらいかかりました。でも、100乗もしないうちに10^18ぐらいは超えるでしょ、という感覚を信じて、aとbを全探索しました。試験後計算してみたところ、38乗で超えるみたいです。

あとは、long longにしてオーバフローに気を付ければ答えが出ます。

B問題はグラフの問題。n 頂点 m 辺の単純無向グラフがあります。各頂点には ai が書かれています。すべての i について、ai を以下の操作の後に bi に書き換えたいです。

操作：辺が結ぶ2つの頂点の値を、片方は+1、もう片方は-1 

何回でも操作をしてよいので、全部 bi にすることができますか？という問題。

図を書きながらどうすれば条件を達成できるかを色々と考えていきました。

追記
まず、頂点に関して、ai - biとしました。

隣接する頂点の値の偶数、奇数の数が等しい、辺と隣接する2頂点の和が0である、などなど、あーでもないこーでもないとやってました。

結局、もうちょっと広く見て、同じ集合に属している頂点の総和が0なら条件を満たすということに気づきました。

同じ集合に属すということで、以前に解いたabc177-d-Friendsにて用いた「UnionFind」が使えそうと思ったので、以前に作成したライブラリから引っ張ってきました。

これを使えば集合を楽に管理できるので、あとは総和が0かどうかを確認すれば答えです。

C問題は条件を満たす区間を作成できるか？という問題。区間が複数与えられます。2人が異なる方法で、重複部分が存在しないように、区間を選択していきます。

a : 始点を昇順に並べて、先頭から重複してないなものを選択する。
b : 終点を昇順に並べて、先頭から重複していないものを選択する。

2人の選択した区間の個数の差(b-a)が m となるような区間を作成してください。

という感じです。

とりあえず、mが正（aの方がたくさん区間を選べる）, 0 , 負の3つの場合に場合分けすれば解けるなーって考えました。まずは、ぱっと浮かんだ負の場合を実装しました。大きい区間を一つ作って、その中に小さいものを m の条件を満たす分だけ詰め込みました。0のときは、適当に作りました。正の時はどうしようかといろいろ考えていたら時間切れ。

もうちょっとだったのになーという感じでした。しかし、どうやらbの選び方は最適な選び方のようで、負となる場合は存在しないみたいです。存在しないものにずっと悩んでしました。

あと一歩だと思ったのに、実際はまだまだ足りてませんでした。

今回はコツコツと解答を書いたりライブラリを整理していたのが非常に役に立ったコンテストでした。先週に作成した、アルゴリズムから問題も逆引きするメモがここまで役に立つとは。

アルゴリズムやメモはgithubにあげているので、興味がありましたら使ってみてください。お役に立てると嬉しいです。

UnionFindの記事のリンク
https://note.com/momomo0214/n/ne25049a25cf0