いろいろな記録

大学院生やってます

AtCoder Beginner Contest 161

ABC161お疲れ様でした。過去最高パフォ出せてよかったです。

atcoder.jp

 

A - ABC Swap

c -> a -> bの順に出力するだけです。最初出力時に " " を入れ忘れて10秒ほどロスしました。

 

B - Popular Vote

こちらもそのままですが, 4mで割る時に小数が出てくるのが怪しいと思ったので,移行して掛け算の形にして整数で解きました。

パナコンのC問題のように,小数を扱わないような工夫はデフォルトで出てくるよう,注意を怠らないようにしておきたいです。

 

C - Replacing Integer

nに対して,何回kで足し算または引き算をしても n\ ({\rm mod}\ k)は不変であることから, {\rm min} (n \% k,\ k - n \% k)という答えが出ます。

 

D - Lunlun Number

面白い問題でした。これを落ち着いて処理できたことで,ある程度成長を感じました。

例4で,制約条件中で最大のn=100000に対するルンルン数が3e+9くらいと出ているので,この時点で自然数一つずつ列挙+判定が難しいとわかります。

最初,最大の桁数を決めてDFSでいけると思ったんですが,再帰の引数が多くなりそうでめんどくさかったのでBFSに切り替えました。

BFSと同じ要領でキューに対してルンルン数を入れていき,その都度カウントを取っていくと適切な値が出てきます。

 

そういえばルンルンってダックスフンドでしたっけ。なんかそんな問題があった気がします。

 

E - Yutori

ギリギリゆとり世代の僕としては解きたかったのですが,順位表を見てFが解けそうだったので飛ばしました。

解説読んでなるほどなあとなっているので解説ACしておきます。

 

F - Division or Substraction

考え方はCと同じで,n-kの引き算を繰り返してもn\ ({\rm mod}\ k)は変わらないので,この二種類の操作については「割れるだけ割る」→(割れなくなる)→「引けるだけ引く」という順番で起こること以外ありえません。したがって答えの候補としては,割れるもの(nの約数)もしくは割れないもの(割って余りが1になるもの)しかありません。前者については,割れるだけ割った後のmodが1になるものの個数,後者に関しては, n-1の約数の個数が答えとなります。

divisorをスニペットに入れておいたことを忘れていたり,コード上でn=2が違った処理をされることを見落としていて,30分ほどかかってしまいましたが,残り7分でACできました。

 

 

あと青パフォと水パフォを一回ずつとれば入水できそうな感じです。

次回も頑張ります。