最終更新: 2021-05-07T14:21+0900
今日の ABC の C と D はちょっと傾向が違ったよね(E と F は時間切れで読んでいない)。C はむしろ復古的かもしれないけど。
どこに着目すれば数えられるのか、わかりますか？ わかりません。
テキトーに注目して数えて、(÷２では)ダメだとわかって(÷３で)やり直して、31 分かけて鬼の羅列である。
(構造の)理解に頭が必要ないという意味で、これも可読性に優れた読みやすいソースコードの例なんですよ。似たような例にすべての繰り返しを for ループで書くなんてありますね。for さえ解れば鬼に金棒、馬鹿の手にハンマー。目に入るすべては釘。打つべし打つべし。
だけどプログラムは構造化と抽象化を(必要である限り)繰り返して、人間はよりハイレベルな意味を読み取らなければいけないんです。あれをどーしたこーしたなんて作業手順を(人間に向けて)仰々しく並べ立てることに意味はありません。それはソースコードの役割であって、人間に向けたコメントには意味のあることを書いてください。
これって、黒のマスが１つの塊(ドーナツではない)であって、黒の内部に白のマスが島になっていることがない(逆に黒のマスはたった１つの島になっている)ってことだと読んだ。そのあとで補足的に「白に塗られた任意の 2 マスは、辺を共有するマスへの移動を繰り返し、白に塗られたマスのみを通って互いに到達可能である(マス目の一番外側のマスは全て白に塗られていることに注意してください)
」ともあるし、問題文は慎重に
書かれていたと思う。
多角形の解釈についても、色が塗られたグリッドであって座標空間上の点列ではないのだから、書かれていないものを見ようとして見るべき角が見えていなかっただけでしょう。
数学の言葉で書かれた制約の読解に普段苦労するので(20201122p01)、今回の問題文に文句はない。
すごくいい。そうか、ドット絵師と 3DCGモデラーがいただけなのか。
図形です。
制約が 10^5 だからどうかなーと思ったけど、普通に数えられる範囲だったみたい。手元ではサンプルに２秒以上かかってたんだけど、ジャッジサーバーは速かった。
１時間かけて、コンテスト終了１分前の提出。よかった……よかった……。
格子点を数える問題で、入力を小数で受け取るのはやっぱり怖い。小数点以下第４位までって書いてあるので、(文字列のまま) 10000 の下駄をはかせて、ついでに諸々の座標が正の範囲に収まるように平行移動した。負の数が混じると整数除算の丸め方向が期待と異なっていて面倒くさい。
# 0 を足すと答えが変わります。難しすぎるでしょ？ -1/2 #=> -1 0-1/2 #=> 0 # 1 (イチ)が変数 l (エル)で、中身が正の数だったり負の数だったりすると、もう予測できないでしょ？
上記は Ruby の挙動。仲間はずれらしい>「整数同士の除算演算子の挙動 (C言語、C++、Scala、Java、Rust、Go言語、PHP、JavaScript、Perl、Python、Ruby、Elixir) - Qiita」 Python の整数除算(//)も同じく負の無限大方向に丸められるとか。
他の人の Ruby での提出を見ると、入力を to_r するものが多かった。r は Rational の r. 使ったことがないと使えないし、思いつきもしないのだ。
二分探索の探索範囲をちまちま限定したところで、倍の違いが試行１回の違いにしかならないのだから、２つのループは１つで十分でしたね。これは円を４分割して数えられないか考えていたのが尾を引いている。
競技プログラミングをするフレンズ @kyopro_friends
アライグマ「D問題は、円の中の格子点のx座標としてありえる値の範囲がX-R～X+Rだから、x座標を決めたときの格子点の個数が求められればいいのだ！ 誤差が大変だから整数で計算して、負の数の切り上げや切り捨ての計算に気をつけて……、罠がいっぱいあって大変なのだ」https://t.co/6z8erFU3Ym
実は二分探索がいらなかった>画像。三平方の定理！ 中学生！
三平方の定理。速い！ 短い！
Integer#sqrt なんてニッチなメソッドを使ってみた。
ところで、やっぱり **2 は遅いみたい。引き算を２回評価することになっても覆らないくらいに。
Ruby での提出を早い順に見てるんだけど、どの人もどの人も平方根をとって計算で格子点の数を求めていた。10行以下のスクリプトで。それが間違いなくすごいんだけど(だって開始後30分ぐらいでの無駄なく短い提出だ)、それらをことごとく撃墜した３つの入力(handmade_marginal_{01|03|05}.txt)が、今回はいい仕事をしていたなと。単に to_f を to_r にしたところで、三羽烏のひとつしか超えられないみたいですよ。
Rational だけでなく BigDecimal の存在も忘れていた。これは「任意の精度で 10 進表現された浮動小数点数を扱えます。
」 to_d の d は (big)decimal の d. to_f を to_d にしてもやっぱり３つのうち２つが WA になるようなのは、BigDecimal#sqrt を使わないで Math.sqrt を使っているのが良くないんでしょうか。Math モジュールは、標準とはいえ require が必要な添付ライブラリである BigDecimal を知らないのが普通だと思う。
提出して確かめようとしてわかった。BigDecimal#sqrt を使うとサンプル３で既に TLE が避けられない。
入力は Rational で受け取っている。Math.sqrt の結果を検算して条件を満たす限り±１の微調整を施し続けている。そして大事なことは、±１した結果の正当性も確かめている。
単純に±１するだけ、しっぱなし、では、handmade_marginal_{00|04}.txt に捕まってしまうようだ。
書き方を洗練させた結果がたぶんこの提出 #20009989 (kyoshida さん)。find メソッドと count に加算する前の nil チェック。
左右の点のうち１点が二分探索で見つかりました。左右の点の中間座標は円の中心に由来して明らかです。ではもう１点は？ a1 = x*2 - a0
違いは１行だけ。Math.sqrt の結果を(floor ではなく)小数点以下第５位あたりで丸めていたらどちらも AC だったんだろうかダメです。
これが Integer.sqrt の実装らしい。
def isqrt(n):
x, y = n, (n + 1) // 2
while y < x:
x, y = y, (y + n // y) // 2
return x
Math.sqrt とは別に用意する価値があるからこそ存在しているのかな。ニッチとか言ってしまったが、こちらが使い所を知らないだけなのか。
自分は今回も Sqrt Inequqlity のとき(20200316p01)も、浮動小数点数を単純に嫌ったり怖がったりして難を逃れたけど、こういう風に限界を見極めて対応できるの、かっこいいよなあ。
B 問題の出力例はスペース区切りだけど、問題文は「A′ の要素を空白区切りで順に出力せよ。
」という表現になっている。
ここを参照すれば間違いないという定義があるわけではないけど、空白が white spaces の意味なら、ここに改行もタブも含まれると考えるのが普通(※要注意ワード)。自分は「スペース」(ASCII 0x20)と「空白文字」を使い分けているし、AtCoder にもそのように期待している。
というわけで、わざわざ .join(' ') はしない>提出 #19962733。
ダメです handmade_marginal_{00|04}.txt に捕まってしまう。Math.sqrt のアルゴリズムに起因して誤差が蓄積するらしい？