AtCoder Beginner Contest 174はC問題が大荒れでした。私は残り30分ぐらいに順位表見て、C問題の提出数よりD問題の提出数の方が多いのを見てD問題に取り掛かった口です。D問題はACできたのでレート大暴落とはならずに済みました。
また、今回のA~C問題のwriterは、かのMultiplicationシリーズでお馴染みの競プロフレンズさんでした。
目次
1,A問題
キーワード:if文、やるだけ
if文書けますか？という問題です。とても簡単。
三項演算子を使って実装するとプロっぽく見えますが、私は使いこなせていないので普通に書いています。
2.B問題
問題:B – Distance
キーワード:距離、オーバーフロー
for文書けますか？ルート計算と二乗計算できますか？という問題ですが、私はちょっと躓きました。
理由は、int型で計算するとオーバーフローするからです。お陰で入力例3を入れたら13という謎の出力が出ました。しばらく悩んだあとに制約条件を見て事なきを得ました。まあ、特に理由がない場合は全部long long型にしててもいいと思いました。
二乗計算はpow()関数を使ってもいいですが、二乗程度だとこっちのほうが楽だと思います。あとpow()はちょっと遅いとどっかで見た気がします。
3.C問題
問題:C – Repsept
キーワード:mod、倍数
まず、1,11,111,…のようにすべての桁の数字が1である自然数のことをレピュニット数(レプユニット数)と言います。各レプユニット数の約数に登場する素因数に関しては法則があるらしいのですが、そのとおりに実装してもできなかった(解が複数個出てしまうが、その中に正しい解は含まれていた)のですが。
さて、今回は7,77,777,…なのでレプユニット数*7という数列になっています。なので、7の倍数でなければレプユニット数の約数として初めて登場する項の番号を言えば良さそうに見えます。ただ、その"初めて約数として登場する"というのが曲者でして、3以外の素数ならばmod n(nは項の番目)をやって1余る場合のnがそれに当たるらしいです。
これが上に書いた"法則"なのですが、ぶっちゃけソース元がyahoo知恵袋なので・・・。確かに正しい解が含まれる集合が出力できましたが、一個に絞ることはできませんでした。
さて、C問題で数論なんて出るわけ無いだろ！という話なので、ちゃんとした解法を。これに関してはwriterである競プロフレンズさんが解説してくれています。
アライグマ「C問題は、a[n+1]=a[n]*10+7だと思うと、mod Kでの値が順番に計算できるから、同じ値が出てくるまでを調べればOKなのだ！ K項目までにはループになるから、手抜きをして「K項目までに0になるか」とかで判定しても大丈夫なのだ！」 pic.twitter.com/mh8vfd2doA
— 競技プログラミングをするフレンズ (@kyopro_friends) August 2, 2020
まず、7,77,777,…の各項はa[n+1]=a[n]*10+7という漸化式で表せます。
そして、mod計算の性質で、先程の漸化式はa[n+1]=(a[n]*10+7)%kと合同になります。あとはその値が0になるかどうかをK項目まで探索すれば良さそうです。
上の解説ではループするとあるので、ちゃんとループするかどうかを判定するにはsetなどを用いて管理する必要があります。最近でループすることを利用する問題だと、ABC167のD – Teleporterがあります。たまにループ判定が必要な問題が出てくるので、頭に入れておきたいです。
また、twitterでこの問題の感想を見ていたら、「1.9s計算してプログラムが終了してなかったら-1を出力するコードを通した」ってツイートを見かけて、制約時間を逆手に取ったコードも面白いなと思いました。
4.D問題
キーワード:最小操作回数
C問題より遥かに簡単です。計算用紙に入力例1を書いてみて、自分で操作してみると解法がわかると思います。
赤い石の左に白い石があってはいけないので、結局はR…RW…Wという風にのみの区間とWのみの区間をつなぎ合わせた形になります。そのため、最終的にR…Rとなる部分にあるWの数を数え上げれば正しい出力が得られます。
最終的にR…Rになる部分は、文字列をsortして元の並びと比較してもいいですし、Rの数を数えて、それまでループを回して数えてもいいと思います。
提出したコードではWの数も数えていますが、解法上は必要ありません。
5.おわりに
A,B,D問題通せて3完でした。Cはmod Kの世界ということに気が付きませんでした。数学的な問題だとばっかり・・・。
しかし、途中でD問題に移行してACできたのは良かったと思います。たまにC問題の難易度詐欺があるので、順位表を見てAC数/提出数を確認することは競プロにおいては必要なことなんだなと思いました。
しかし、未だにhighest更新できていないので、頑張っていきます。緑とかまだまだ遠い。