おはようございます。しほみんです。
この前の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問題も大事ですね。競プロもっとレベル上がってもちゃんと書けるべきなので、引き続き挑戦したいですね。
ではでは。
