AtCoder Beginner Contest 174 参加記

ABC174に参加して、47分で全完して221位だった。うれしい

ABCで全完したのはこれが初めてです。

f:id:knzk398:20200804204318p:plain

A,B,Cまで普通のでD問題がちょっと難しくてE問題がかなり難しくてF問題がtwitterで見たことあるやつだった。

A~Eまでのそれぞれの問題に対して考察を書く。

A. Air Conditionar

Xを受け取って30と比較する　三項演算子で、はい

C++:

https://atcoder.jp/contests/abc174/submissions/15587969

Python:

https://atcoder.jp/contests/abc174/submissions/15631507

B. Distance

これも問題文の通りにやる。 $\sqrt{p^{2}+q^{2}}$ を関数にわけると、うれしい

C++:

https://atcoder.jp/contests/abc174/submissions/15594907

Python:

https://atcoder.jp/contests/abc174/submissions/15634182

C. Repsept

これはちょっと難しい。

数列A=7,77,777,7777,.....として、これをKで割った余りで置き換えた数列AmodKを考える。K=101の場合AmodK=7,77,70,0,7,77,70,0,....となる。ここでAmodK[i]==0となるiを求めればよい。

7,77,777,7777,.......という数を愚直に持ってmodK(Kで割った余り)を計算していくと77777777777777777777777とか、桁数が大きくなるとオーバーフローしてしまうのでうれしくない。

少し考えると、A[i] = A[i-1]*10+7になっているのがわかる。これでAを陽に持つ必要がなくなった。次に、modKでは足し算とか掛け算は適当にやってもいいので毎回Kで割りながら計算していけばよさそうな気になる。

この方法だとAにKの倍数が存在しないときに無限に計算を続けてしまい厳しい気持ちになるが、適当に1e7回ループして無理なら無理。ということにしたらACを得たので、ヨシ！w

C++:

https://atcoder.jp/contests/abc174/submissions/15745382

Python:

https://atcoder.jp/contests/abc174/submissions/15635522

D. Alter Alter

うーん　木びしい　

これは最終的にRRR....RRRWWW...WWWという形になってほしいので、そういうことを考えると、右側にあるRはWに色を塗り替えるか左側にあるWとswapする。

えー、なんとなくRとWの前から、後ろから累積和をとってごちゃごちゃする気分になる。

sample3で考えると

		W	R	W	W	R	W	R	R
front R	0	0	1	1	1	2	2	3	4
front W	0	1	1	2	3	3	4	4	4
back R	4	4	3	3	3	2	2	1	0
back W	4	3	3	2	1	1	0	0	0

こんな感じになる。これを見ると、みると、みてもよくわからない。

まあ考えると、i番目までみて、それより左にあるWを消す。それより右にあるRを消す。としたい。min(frontW[i],backR[i])個はswapして残ったのは色を変える作戦でi=0~nまで計算してそれのminをとるとサンプルが合うので、提出するとAC

C++:

https://atcoder.jp/contests/abc174/submissions/15611373

Python:

https://atcoder.jp/contests/abc174/submissions/15641506

E. Logs

かなり難しくて、難しい。

一瞬、全部priority_queueに入れて、大きい順に取り出して半分にして戻す。という操作をK回やればよさそうな気になるがKが1e9なので時間的に不可能だし、Kが小さくてもsample1でそれをするとダメなことがわかる。コンテスト中はここまで考えてわかんねーとなってF問題を見に行った。Fが見たことあるやつなのでACができて、帰ってくると、二分探索という言葉が降ってくるので、それで考える。つまり、長さの最大値の最小をLen以下にできるかという判定問題を解ければそのLenの取りうる値を二分探索できるので、おーけー笑

ここまで考えれば8割ACしたようなもんだが、ぼくは算数が苦手なので、ここから詰めるのにかなり苦戦して、長さA[i]の丸太を何回か切って最大の長さをもつものがLen以下になるようにしたいという問題をO(1)で解くのにかなり苦労した。競プロ経験からこんなんA[i]/Lenのceilかfloorだろwwwと思ってやったらどっちもsampleがあわず、あーーーーーあーあーあーあーあー＾＾＾＾＾＾＾＾＾＾ーあーあーあーあー＾ーあ＾ーあ＾あー＾ーああ＾ー＾という気分になった。ceil(A[i]/Len)-1にしたら通ったので、おーん.....

なんでceil(A[i]/Len)-1かというと、ceil(A[i]/Len)で、切った後できる丸太の数を表していて、それ-1が切った回数になる。自明ですね。今なら3秒で思いつくけどコンテスト中は3分か5分かしらんけどめちゃくちゃ時間がかかったので、反省。

C++:

https://atcoder.jp/contests/abc174/submissions/15622885

Ptyhon:

https://atcoder.jp/contests/abc174/submissions/15643056