AtCoder Begginer Contest 144のDまで解いてきました。(ネタバレ注意)
タイトル通り、ABC144を解いたので、勉強したこととか感想とかをつらつらと。
リンク
https://atcoder.jp/contests/abc144/tasks
いつもながら、ネタバレ注意です!!
さて、まずはA問題とB問題ですが、こいつらはただif文で判定するだけので、特に言うことはなし。次にC問題ですが、こっちは慣れてないとすぐにはできないかもしれないので、度忘れした時用にメモがてら解法をば。
以下、問題文。
高橋君は無限に広い掛け算表の上にいます。
掛け算表のマス には整数 が書かれており、高橋君は最初 にいます。
高橋君は 回の移動で から か のどちらかにのみ移ることができます。
整数 が与えられるので、 が書かれているマスに到達するまでに必要な移動回数の最小値を求めてください。
これを見て、まず思いつくことは、「とりあえず、a*b=Nとしたときに、|a-b|が最小になる時のa,bに対して、a+b-2すれば良き」ということなのですが、このとき、aとbは対称性があるので、a<bの時だけを考えればよく、加えて、この条件下では、a<=N^(1/2)が成立しているので、1重ループで全探索してやれば良さそう。この方法でやる場合、Nをi(i=1,2,3,4,.....)で割っていくのですが、iがNの約数であるかどうかの判定をどうしようかと考えたのですが、そんなに難しくないですね。Nをiで割ったあまり(javaだとN%i)が0であれば良いので。というわけで、C問題は典型的な全探索でしたとさ。
最後にD問題これは普通に面白かった、というか懐かしかったです。
以下、問題文
高橋君は、底面が 辺 の正方形であり、高さが であるような直方体型の水筒を持っています。(水筒の厚みは無視できます。)
この水筒の中に体積 の水を入れ、底面の正方形の 辺を軸として、この水筒を徐々に傾けます。
水を溢れさせずに水筒を傾けることができる最大の角度を求めてください。
いや、中学受験か!!と叫びたくなるようなこの問題。少年の心を忘れたこの大学生は大人げなくも普通に三角関数を使ったとさ。(とはいっても、tanを使っただけなので、小学生でも習えば解けるかも?)
一応考え方載せときます。
メモが雑なのは申し訳ない。
んで、問題はここからで、このtanをどうやって角度に戻そうかなと考えようとしたんですが、ダメもとで調べてみたらjavaには普通にMath.atanなるtanの逆関数の値をかえしてくれる(値xをいれたら、tan(y) = xとなるようなyを返してくれる)ものがありまして、これを使って解けましたとさ。めでたしめでたし。
今回の問題はアルゴリズムとかはなくてラッキーな感じでしたwでもそろそろガチで練習せんとあかんな~。