ARC110の感想
鹿島建設プログラミングコンテスト2020（AtCoder Regular Contest 110）に参加しましたので、その感想を書いていきます。
問題はこちらから。
結果はこんな感じでした。
正解：AB(4wa)
順位：1966 / 3971
パフォーマンス：910（緑）
でした。今回はABを60分で解いて、C問題に60分かけることができました。ただ、今回も解けませんでした。前回も同じようなこと言ってましたね。今回はいいところまで考察できたと思うんだけどな。
また、今回は賞金の出るコンテストでしたので、なんかよくわからない奇跡が3回ぐらい起こって、お小遣いもらえるかもと思ってましたが、そんなことはありませんでした。当然ですね。
あと、少しづつ緑の頻度が増えてきました。このままいけばレーティングが緑になるのももう少しかもしれません。水色パフォーマンス（1200）を出す勢いで、精進をしたいと思います。
ARCに関しては、難易度によって変わりますが、Bの速解きかCの正解あたりが1200ボーダーになっています。ですので、緑、水色問題をじっくり考察する練習をしつつ、灰、茶を高速で解く訓練を積んでいきます。
少々話が逸れましたが、今回の感想を書いていきます。
A問題
2~nで割った余りが１となる数を求める問題。ここで2<=n<=30です。
一番初めはとにかく2~nまで全部かけてそれに+1でいいじゃん。と30秒ぐらいで実装しましたが、n=30のとき、掛け算の積は10^31ぐらいだったかな？になるなと思い断念。
次に素数だけをかければいいんじゃないかということで、実装しましたがダメでした。これだと、25とか27などなど、素数の2乗、３乗を網羅できません。
結局、2~nまでの最小公倍数+1が答えだということに気づいて、紙に2~30までを素因数分解して、すべての数の倍数となるように必要最低限だけを掛けて+1して答えとしました。もっと言うと、答えはnによらないので、2~30の最小公倍数+1が全パターンの答えになります。
B問題
文字列の問題です。sは"110"という文字列を10^10回繰り返したものです。sの中に長さ n の文字列 t は何回登場しますか？
という問題。
前々回かな？B問題で"fox"を消していく問題が解けなくて少し文字列に不安がある状態で、10^10という数字が目に飛び込んできたので、だいぶ動揺しました。
文字列の検索でもするのかなとかをはじめに考えましたが、10^10がその考えを阻みました。
とりあえず、文字列「110」ですので、もし t が s の中に登場するならその開始点は0,1,2の3パターンに分けられるなと思いました。そして、次の開始点は始点+3、その次は+3、となります。結局これが、tの末尾がsに収まるまで何回繰り返せるかを割り算で求めてしまえばおしまいです。開始点と t の長さを s から引いてそれを3で割って、植木算的な感じで+1をすれば答えです。
あとは、コーナーケースを見ていきましょう。私はここで3waをたたき出しました。まず、n = 1 のときつまり、t= 0,1のときですね。次にn = 2でt = 00,01,10,11ですね。00の場合を忘れて、まずwa。あとはここの出力だけ
cout << pow(10,10) << endl;
としていたのですが、これだと型が合わないのかな？それでwa。
あとは、コーナーケースといえるかわかりませんが、tの開始位置の判定をt[0],t[1],t[2]で見ていたので、それ以降で辻褄が合わない場合を考慮していなくてwa。
ボロボロになりながらもなんとかacできました。
C問題
数字を昇順にソートする問題です。
数字が小さいものから順番に適する場所にswapする。このとき、スワップした場所を記録していき、適する場所にスワップする際に、既に記録されていたものを必要とする場合、-1とする。とすればいいんじゃないかなと思いました。
実装をしたのですが、waとtleでした。tleだけでもどうにかしたいと思って、swapをやめて、該当数字を配列から消去して先頭に投げ込むとしましたが、これもtle。
そういえばどこかの問題で「vectorの先頭にinsertするのは結構重いから避けた方がいいよ」という記述を見た気がします。確かに、メモリ上の動きを考えると、一発で先頭に入れたところで他の要素を内部的にずらす必要があるから、ほとんど処理量変わらないのかーとなんか納得していました。
ただ、コンテスト後に解説を見ると方針はあってるみたいでした。つまり、これはもう純粋に実装力不足です。数学の力ではありません。悔しいですね。
多少の苦さを残しつつ、今回の感想を終わりたいと思います。
この記事が気に入ったらサポートをしてみませんか？