競プロをしながら、節約と株式投資でセミリタイアを目指す東大卒のブログ

東大卒でメーカー勤務の私がセミリタイアするために投資や競プロを頑張っていこうという趣旨で始めたブログです。独身男性です。火木土日に更新予定です。お金について考えています。

競技プログラミング~ABC174~

おはようございます。しほみんです。

 

この前のM-Solutionsはちょっと別件があったので参加してないです。今回は3週間ぶりでした。いろいろ忙しかったのですが、E問題まで解ければよかったなあってかんじです。

 

https://atcoder.jp/contests/abc174

 

自分の競技プログラミングへのスタンスです。

<自分のプログラミング力>

・レートは1000程度になりました。緑中堅へ。

・C#でクラスとかつかってアプリケーションは作れます。

<Atcoderでのスタンス>

・アルゴリズムについて問題でいろいろ学んでいる。第3回PAST70点で中級取得。

・基本的に本番でやっている。現在55回以上参加、2年目。

・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色(1200以上)は欲しい。

 

今回はABCD、30分1WAでした。C問題がちょっと躓いて悩みましたが、裏技使って解いた感じです。D問題も前位に一度見たことがあったのであっさりACできました。あとは、E,Fを見て典型っぽいけど思いつかねえって思って終わりました。できている人が多かったのでパフォーマンスが低いです。パフォーマンスは1101で、レートは1035→1042で微増したものの、やはりこのレベル問題が早く解けてもレートが上がらない厳しさを実感しました。

 

今回はE問題まで振り返ります。E問題が水色目指すなら解けないとダメだったので要反省です。

長くなるので前半はC問題まで書きます。

前回に引き続き考察をメインに書きます。

コードは別に上げます。

 

 

A問題

室温が30度以上のとき、冷房を入れます。今、X度です。冷房を入れるかどうか判定してください。

 

冷房を入れる温度が30度を基準なので、X>=30とそれ以外で、if文を分けて書けばよいです。とりわけ難しいことはないです。

 

B問題

2平面上の点がN個あります。それぞれの座標は(xi,yi)です。

原点からの距離D以下の点はいくつありますか?

 

原点と点の距離は、sqrt(xi*xi+yi*yi)です。これがDより小さければよいです。

ただ、平方根を出すと小数点が出るので、精度を考えないといけないので厄介です。

なので、両方を二乗して、整数だけで考えるとよいです。

long型で、xi*xi+yi*yi <=D*Dとして判定して、満たす場合だけ足し合わせていけばよいです。

 

C問題

数列7,77,777,7777,....とi番目は7がi個並んだ数の数列があります。

この数列で、Kの倍数である数が初めて現れるのは何番目か?

現れない場合は-1を出力せよ。

 

 

まず、Kが偶数の場合は、Kの倍数も偶数です。よって、奇数しかない数列では現れることはありません。

よって、-1を出力します。

それ以外の場合を考えます。

普通に頭から検証してみて考えていくとよい気がします。

すなわち、全検索をしてその間に出てきたら出力すればよいです。

 

全検索の方法は単純で、7,77,777,...をそれぞれKで割って余りを0になればよいです。

ただ、普通に出すことができないので、i+1番目と、i番目の数の関係を考えます。

上の数列のi番目をaiとするai+1 = 10*ai + 7となります。

よって、ai+1(mod K) ≡ 10*ai+7(mod K)です。

これをうまく活用して、while文を作ればよいです。詳しい書き方は下の4-7を見てください。

 

 

ただ、もしかしたら終わらないかもしれないです。終わらない場合はないかなあと思って、-1を出力します。計算時間的に10の7乗ぐらいまでは計算できます。なので、10の7乗までで打ち切ろうと考えます。

 

上記のアイデアは計算時間の制限から出しています。数学的にも証明はできますが、そんな時間はないので、この計算時間の制限とo(N)ができる最大を知ることはとても大事です。

 

まとめると、

1. Kが偶数のときは-1を出力。

2. K=7のときは、1を出力。

3. 初項をx = 7として考える。項数を1とする。

4.(ここからwhile文)項数を1増やす。

5. xを10倍して、7足す。

6. x %= Kであまりを求める。

7. もしx = 0なら最初の項、項数を出力して終わり。また、項数が10の7乗に足したら-1を出力して終わり。そうでないなら4に戻る。

 

while文と計算量の見積もりをすべきいい問題だったかなあと思います。(というかD問題より解けてなくてビビる)

 

最後に....

なんか最近C問題までもあっさり解けるようになってきましたが、A-C問題も大事ですね。競プロもっとレベル上がってもちゃんと書けるべきなので、引き続き挑戦したいですね。

 

ではでは。