こんばんは、しほみんです。
コメントありがとうございます。すべて拝見しています。今後もよろしくお願いします。見てもらえるといろいろ励みになります。
今日は10/27(日）に開催されたABC144（Atcoder）の考え方について大雑把に書こうと思います。あまり見受けられないC#での解答も記載するのでもし興味があればそちらもご確認ください。
自分の結果はABCDまで解いて、解答時間は約82分でした。
昨日は30分ほど遅刻して参加したので結構遅い時間になってしまいました。直接パフォーマンスに響くのでやっぱ遅刻とかよくないと思います。
ABC144の問題はこちらです。
競技プログラミングについての説明は前に記載しています。
ここから下はABC144の解説になります。
今回は2つの積がテーマになっているような問題編成でした。単純なようで意外と厄介なので問題としては悪くなかったのかなと思います。
A問題
九九を覚えた人が九九を計算できるかどうか、九九以外はできないことに注意する。
二つの数字はaとbです。九九ができるということはaもbも1以上9以下であれば基本的に計算できます。
よってif文でa≦9かつb≦9のときはa*bを出力し、それ以外は計算できないことを示す-1を出力すればいいです。
B問題
また九九を覚えた人の話です。今度は逆で数字が与えられたとき、それが九九で表せるかどうかを判定します。例えば49だったら7×7にできるので九九になりYes、50なら5×10なので九九にはできません。よってNoとなります。
これはどうするか悩みましたが、九九で計算できる数は限られます。九九で計算できるかどうかなら九九を全部やらせてその中で一致した数があればYes、ないならNoにすればいいです。
やり方はいくつかありますが、数を読み込ませた後、i,jの二重ループとして、i*jと読み込んだ数を比較して該当する数があればYes, それ以外はNoにすればよいです。
C問題
今度は入力するNの数が以上に大きく、2つの積としてあらわした場合、スタート位置からその位置まで行く距離を求めます。そのうち最小の距離を計算する問題です。
とりあえず仮に2つの積a*bにできれば距離はa+b-2で表すことができます。
Nが非常に大きいのでただ単純にfor文をやっていちいち2つの数に分解できるか考えても間に合わないです。しかし、2つの数の最大はm*mで分解できることに注目するとm*m =Nでmまで考えればいいことが分かります。
よって2つの積a*bであらわせることを仮定して、for文でaを1からsqrt(n)までを考えそれぞれbが存在するか、存在するならbを求め、距離を計算します。それが最小なら更新すればいいだけです。
D問題
3辺がa,a, bの水筒にxだけ水があるときどれぐらい傾けてもこぼれないかを求める問題です。
傾けた分だけ水は落ちやすくなるので角度をどんどん大きくして落ちるかどうかを判定する二分法を用いることが可能です（自分は答えを見て知ったが）
ただ二分法を使っても場合分けがあるので今回は直接傾ける限界の角度直接求めた方が楽です。
場合分けは水が半分より多いか半分以下で場合分けをします。
幸い奥行きはaなので単純にa,bの直方体の平面を考えて出すことができます。
水が半分以下の場合、側面は三角形なので角度を求めるのは比較的容易です。
一方、水が半分より多い場合は、側面が台形になるので角度を求めるのはちょっと厄介です。
ただ、どちらも三角形の相似を使ってcosを求めて角度に直します。
cosから角度に直すときは180/Math.PIで是正が必要です。
また、C#では小数点をつけないとdouble型の計算をしないので注意が必要です。
（2ではint型、2.0はdouble型）
E問題
時間オーバーで解けませんでしたが解説を見て何とか解けました。
（問題）N人の人がいて食べるコストはAi(i = 1-N)です。一方、食べ物も同じ数があって食べにくさがFi(i = 1-N)です。食べるコストa, 食べにくさbの場合食べるのにa*b秒かかります。ただ、K回まで修行ができて、修行をすると食べるコストが減らせます。N,K,Ai,Fiが与えられたとき最小の秒数を求めます。
まず問題を理解するのが厄介です。ただ、要するに修行してどれだけ秒数を削減できるかを求める問題だとわかります。
また、食べるコストを昇順、食べにくさを降順に並べてそれぞれ同じiでかけ合わせれば修行しない時点での最小の秒数というイメージが大事です。（実際そうなのだが感覚的にそうかなと思うことが大事）。修行しないときの最小秒数をうまく求めることも大切です。
あとはここから修行回数以内で最小にできるかどうかを調べますが、この時に二分探索法を使います。
問題としてはとりあえず修行しない場合のかかる時間をmax、最小の0をminとしてかかる時間がx秒のとき修行すればそのxは可能かを見ていきます。xは(min+max)/2
修行で可能ならx秒に短縮できる→maxに代入。
修行で無理ならx秒では短縮できない→minに代入
あとはまたxに(max+min)/2を代入して、答えの出します。
修行をすればするほど必ず時間が減ることを考えると修行でどうにかできない場合は時間を増やすしか手段がないため、minにして解答候補を狭められます。
これだとNlogX(Xは解答の候補数）で時間も間に合います。
F問題は相変わらずわかりません。まずはE問題を時間内で解けるようになりたいです。
またコードも記載しておきます。今度は注釈をつけたのでわかりやすくなったと思います。
参考になればうれしいです。ではでは。
