ARC115の感想

AtCoder Regular Contest 115に参加しましたので、その感想を書いていきます。問題はこちらから。

Tasks - AtCoder Regular Contest 115

結果はこんな感じでした。

ABC (70:08  0WA)
順位　849 / 2592
パフォーマンス 1393

今回初めてARCで3完をすることができました。問題のセットが簡単？というよりかは、A~Cのどれも似たような難易度になっており、いつもとは勝手が違いました。でも、3完は3完です。素直に嬉しい。最近、コンストの調子がよくなかったので、良い結果がでてひとまず安心しました。それと同時に、D問題には歯が立ちませんでした。このパフォーマンスからもう一段階伸ばすのは、とっても大変そうだ、と身に染みてわかりました。

感想です。

A問題

同一の得点を取る生徒の組み合わせは何通りあるかを求める問題です。

まず、問題文を理解するのに10分ぐらいかかりました。これを愚直にやりますと、おそらくO(M*N^2)ですので間に合いません。工夫しました。

まず、XOR演算を試しました、0と1の数がうまいこと噛み合わないかなと、いろいろやりましたがダメ。

次に、0の出現回数をカウントしました。同じ出現回数を持つ人同士はペアになれないことを利用して、

全ての生徒から2人選ぶ：n*(n-1)/2

から、同じ出現回数の人数を m として、

同じ出現回数から2人選ぶ：m*(m-1)/2

を全ての出現回数考えて、全通りから引きました。でもこれ違います。同じ出現回数から2人選ぶとペアにならないのは正しいのですが、それ以外にもペアになれない組み合わせがあります。十分性がないです。

結局、その十分性はある適当な答え（00000）からのハミング距離の偶数奇数のグループからペアを作ることでした。そのグループで上と同じようなことをすれば答えが求まります。

と言いますか、2グループなのでその掛け算が答えです。ACしてから気づきました。

A〜Cのなかで一番苦戦しました。

B問題

行列に関する情報が正しいかどうかを判定し、それの一例を挙げます。この問題は以前類題を解いたことがありましたのですぐにわかりました。

A_1 = 0と置けば、A_1~A_N、B_1~B_Nの全てが決定します。あとはこの値がCの条件を満たすか判定するだけです。

ただし、本問題では非負の制約があります。ですので、AかBのどちらかに負数が出現したら（両方には出現しない）、その絶対値を出現した方に足して、他方には引きましょう。そうすれば、非負が実現されます。

C問題

インデックス番号が約数の場合に異なる数を持つ配列を作る問題です。

まず、出現する数の最大値を最小化する必要があるのでその値を考えました。

1からその値の各倍数に+1をしていって、その値の最大値がその値となります。といいますか、約数の個数の最大値ですね。今気づきました。

次に、ABC194 F - Coprime Present にて

ある数を約数に持つ数字はその数字だけ離れた場所に出現する。

ということをやりましたので、それを使いました。例えば、2を約数に持つものは2個先に出現し、逆に1個隣には出現しません。4ならばとなり3個は大丈夫です。こうやって構築していくと、その数の最大値は先の約数の数と一致したので、この方法で提出。無事ACでした。

D問題

解けませんでしたが、40分ぐらい考えました。

まず、どこが奇数とかは考えず、全体の奇数の頂点数を考えました。また、辺を切った際に辺が繋がってる頂点の次数の偶数奇数で全体の奇数の個数が変化するな、と思いました。

奇数ー奇数→-2
偶数ー奇数→０
偶数ー偶数→-2

辺の情報を持ちながらこの遷移をおこなう、dpかDFSで解けないかなーと考えてました。でも無理でした。

あとがき

A~Cまで似たようなdiffでしたが、それらをしっかりと得点できたのはよかったです。また、なんといってもWAを出さなかった点を一番褒めたいです。提出の前には、intとlong longやコーナーケースがないか、などいろいろと考えてから提出をしました（辺な数字が入って、コンパイルエラーを出しましたが、、）。

難しい問題に歯が立たないのは承知の上です。のんびりのんびりと難しい問題に手が出るようになればいいなあ、と思っています。ですので、これからも実力相応の問題の精進を続けていきます。頑張ります。