ABC145参加
ABC145参加しました~
結果はこちら
2完しかできず詰みました…
コンテスト中はすべてFortranで出しました.
A問題
円の面積はなので
を出力して終わりでした.
B問題
Nが偶数かつ文字列の前半分と後ろ半分が同じときのみYesと出力するようにしました.
C問題
とりあえず3と4のときの順列を列挙して手で数えてみたところ、特定の隣り合う2つの組み合わせが回出てくると勘違いして、各点間の距離の総和に
をかければよいという結論に至り、実装して試してみたらサンプルケースで見事にコケてしまいました(それはそう). そのため、全探索するかぁってモチベーションになったものの、やりかたがよくわからず、時間がかかりそうだったのでしばらく迷ってから諦めました.
D問題
与えられた条件から、到達できる点は下の図のように格子状に存在することがわかりました.
が到達できるかどうか判定して、あとは
で求めれば良いことがわかったので到達できる点かどうかの判定方法および
と
の求め方を考えていくことにしました.
まず、到達できる点かどうかの判定法です.
図1から、
$$y= \frac{x}{2}+b \tag{1}$$
は必ず
$$(a, 2a) ただしa \in \boldsymbol{N} \tag{2}$$
を通ることがわかります. よって、ここから式(1)のを求めると、
$$2a= \frac{a}{2}+b$$
$$b=\frac{3a}{2}$$
これと
を式(1)に代入し、
について解くと、
$$Y= \frac{X+3a}{2}$$
$$a=\frac{2Y-X}{3} \tag{3}$$
よって、式(2)から
が3の倍数でないと到達できないことがわかります.
次に、と
を求めます. 図1において、目的地まで原点から上方向にいくつ進まなくてはならないかは、入力された点
を通り傾きが
である直線と
の交点の
座標に等しいことがわかります. これは、式(3)と等しいので、これを使います. 横方向には、今度は点
を通り傾きが
である直線と
の交点の
座標と等しいことがわかります. よって、これを求めていきます. 点
を通り傾きが
である直線を
$$y=2x+c \tag{4}$$
と置き、
を代入して
を求めると、
$$c=Y-2X$$
よって、式(4)と
の交点の座標
は
$$2l+Y-2X=\frac{m}{2}$$
$$l=\frac{2(Y-2X)}{3}$$
よって、
座標は
$$m=\frac{l}{2}=\frac{Y-2X}{3}\tag{5}$$
であることがわかります.
よって、式(3)および式(5)から、
$$n=a+m=\frac{X+Y}{3}$$
$$r=min(a,m)$$
であると求められました.
ここまできたら後は実装するだけだったのですが、効率のよいコンビネーションの求め方がわからず、ひたすらググっていました…
結局、こちらのサイトに載っていたコードを使用させていただきました.
【Python】組み合わせ(nCr) 計算の高速化 - Qiita
ただ、これで実装できたはいいものの、終わったのがコンテスト終了直後という悲しい結末… しかも、提出してみたら普通に通ってしまったという悲しさ…
供養しておきます pic.twitter.com/sU3dB41DhV
— JJ1GUJ@オセロソフト公開準備中 (@jj1guj) 2019年11月16日
終了20秒後に出したのが通るとかなんなん…
終わってからずっとほえてました…
反省とか
よかったところ: Fortranの実装速度が上がった
悪かったところ: B問題に見切りをつけるのがおそすぎた
結局レートはちょっと下がってしまいました...(100くらい下がるかと思ってたけどそうでもなかった)
とりあえず来週もABCあるのでレートを戻せるようにがんばります.
あと4~5回くらいで緑色になりたいなぁ…
