ARC104の感想

AtCoder Regular Contest 104を解きました。問題はこちらから

Tasks - AtCoder Regular Contest 104

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

初めてのarcでしたが、abcに比べるとやっぱり難しかったです。後半はどんどん暫定順位が落ちていくなーとか思いながら順位表を見てました。実力相応な結果という感じです。

試験中の思考過程を書いていきます。

A問題はx+y = a, x-y =bから、x=(a+b)/2, y=(a-b)/2を求めて終わり。
一応、a+bが奇数だと切り捨て誤差が出ちゃうのどうしようかなーと考えましたが、x,yが偶数、奇数のどんな場合でも大丈夫でしたね。

B問題は問題の意味をとらえるのに5分ほどかかりました。難しい言葉が出てくると頭が混乱します。結局は、並び替えてaはtとcはgと置き換えられる、部分文字列は何個でしょうかという問題。

すぐに、部分文字列に含まれるaの数＝tの数、かつcの数 = gの数が条件だとわかりました。そのため、for文を3つ使って、文字長、開始点をずらしながら判定を行いました。

そしたらTLEでしたので、for文を減らしました。先頭からその時点までで出現した各文字の回数をカウントした配列を作り、

区間に含まれる数　＝　終点までの数　－　始点ー１までの数

で求めました。

これ以降は、解けなかったのですが、一応書いていきます。

C問題はエレベータの問題。データが抜けているため仮定をする、みたいな問題は初めて解くため、少し考えたけど断念。D問題に移りました。

D問題は重複を許す整数集合の平均が整数となる個数を求める問題。

いろいろ考えた結果方針として、

ひとまず、使うかわかんないけど、(k+1)^n-1が取りうる集合の個数

集合の要素数を l をしたときに、1~nをlで割った余りの種類は l-1種類。この余りの和をlの倍数になるように選んだ個数が整数となる集合の個数となる。この条件のもと、lを1→n*kまでやればよいのではないか。

という感じです。ここまで考えて時間切れでした。

難しい分、あーでもない、こーでもないと楽しくできました。
解説を見ると、あーあー、そうなのねーっていう感じになりそうなので、復習がとっても楽しみです。

楽しいことばっかりですね。

直近の目標としまして、パフォーマンス1000を目指しているので、今後とも精進していきます。