最終更新: 2021-05-07T14:00+0900
先週末の ARC。ABの２完でレートは横ばい。ちょっと背伸びして C 問題が今やっと解けたので日記にする(べつに考え続けていたわけではなくて、オラクルが降ってくるのを待っていたのです)。
一応制約は掛け算していたんだけど、まずは素直に数えて確実に答えを……TLE。見れば一次 の k のΣなので機械的に変形して……AC。
間違った式の変形に５分以上の時間をかけてもしゃーないので、TLE は避けられない。今は(ARC の１問目に対しても)ステップを刻まなければ、答えにたどりつくことさえ覚束ない。
どれだけ１円を払っても数の種類は１しか増えないので、基本となる操作は何回２円を払って絶対値を変化させられるか。±B が境界として存在していて、|B| から 0 へ向かう変化と -|B| から負の無限大へ向かう変化が考えられる。反対側の値は１円余らせておくだけでいい。0 を挟んで -B から B の範囲を数えるのが面倒か。親切にも B=0 となるコーナーケースがサンプルのひとつになっている。もうひとつのコーナーケースが C=1
2 WA のあとの AC。±B と 0 と、それらで区切られた４つの区間を愚直に数えた。
翌日になって機械的に式を整理したもの。できれば if による分岐を消したかったのだが。
問題の見通しは難しくない。表のスコアと裏のスコアと、手番を渡すか否かのフラグ(子孫ノード数(=スコア計)の偶奇)があって、それらを葉からボトムアップで積み上げていけば先手、後手のスコアが即座に解る。
制約の 1≤ の解釈に一瞬詰まったけど、p_v<vp_v の上限が v であることで、逆向きにスキャンするだけで子から親へ順序よく処理できる親切設計だとわかった。
最後まで解らなかったのは青木君高橋君が採用する最適な行動がいかなるものであるか。二人が何を指標にしてどの子を選ぶのか、それが解らないでどうしてコーディングができる？ 何をコードにする？ 自分はこの、先攻後攻が決まった瞬間に勝ち負けが見えるゲームを、きっと楽しくプレイできるんだろうなあ。
odd.sort_by!{ _2-_1 } と even.each(...) がキモ。これが二人の戦術。
最後まで見えなかった even.each についてもう少し。
even は潜って戻ってきたときに手番が入れ替わらない子ノードを集めた配列。表のスコアが裏のスコアより高いものは手番(※広辞苑にはテツガイの見出ししかない。テバンは業界用語か？)を持っている方がさっさと潜って表のスコアを得てしまえばいい(裏のスコアは相手に渡る)。では裏のスコアの方が高いものは？
裏のスコアの方が高いものは、できることなら相手の手番で相手に選ばせたい。そうすれば表のスコア(低い)が相手のものに、裏のスコア(高い)が自分のものになる。それが可能になるのは、潜って戻ってきたときに相手に手番が渡る子ノード(odd 配列)が奇数個ある場合。手番というババの押し付け合いに勝てる。
Ruby の他の AC 提出(今のところ２つ)と比べて遅かったので出し直し。100 ms 縮んで遜色がなくなった。省メモリを目論んだが結果的に増えている。配列の配列の配列がよくない。
ところで、再帰呼び出しを行っている解答を手元で実行してみたらいくつかのケースで stack level too deep (SystemStackError) が出て速度比較ができなかった。PC が貧弱なんだな(環境変数か？ その解決法はドーピングぽい)。
人類の手には多少余るとしても、プログラマを信頼し、力を与えてくれる言語が好きだ。安全のためと称して枷をはめようとする言語は選ばない。安全な」■git は素直でパワフルな道具>20181118p01。リンカは素直で馬鹿な道具>20181102。Nintendo Switch の UI>「「あまりに親切すぎるUIは冗長になる」という考えのもと、プレーヤーを信頼して意図をはっきりさせたかった」。ユーザーの意図を反映するかわりに押しつける道具>20150410。鈍 は退屈だ。
while queue.empty?.! というループを見つけて、二度見では理解できなくて三度見直した。見たことのない字面だから nil許容演算子(&.)なのかと最初は思った。ドットノットが出てくるのってすごい。最初に while ! queue.empty? が浮かぶでしょう？ そうしたらそこから until queue.empty? へも至るでしょう？ 演算子にドットを付けて呼び出そうっていうステップが割り込む余地はないように思う。そういう書き方のパターンを考えたことがなかった。いやまあ自分は最初に until が浮かぶので(「キューが空になるまで繰り返す(until queue.empty?)」)、引き出しのひとつとして蓄えたうえでしまいっぱなしにするんだけど。最終更新: 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 のアルゴリズムに起因して誤差が蓄積するらしい？
最終更新: 2021-05-04T20:49+0900
先週末の ABC。例によってお風呂で考えるも頭が爆発して無理だと思われた F 問題が、なぜか今日取りかかってみれば解けたので日記にする。
すごく難しくて、じっくり 10 分の時間をかけた。
Aoki と Takahashi の文字列を２回書いているところに余裕のなさが見える。間違えるくらいなら全パターンを網羅して並べればいいんですよ(言っていることが違う>20201101p01.03)。
A 問題より簡単だった。条件を満たすものが１つでもあればいい。Array#any? メソッドの出番です。
ところで空配列に関して、[].all? は true を返し、[].any? は false を返す。この違いによってメソッドの選択が制限されることがあるかなと一応警戒するんだけど、特にそういう違いは生まれないみたい。むしろそうならないようにデフォルト値が選ばれている。罠があるとしたらそこではなく、穴に落ちるときは all? を選んでも any? を選んでも落ちる。
制約が K に関して全探索しろと言っている。
Ruby で最も速い提出(492 ms)より倍以上遅いんだけど、どういうことなんでしょうね。
本当は今日は F 問題をやるつもりはなくて、この C 問題を速くするつもりで取りかかったのだけど、優先順位をつけた深さ優先探索でやろうとしてうまくいく見通しが立たなかったのだった。
45 分考えた。等差数列の和の公式に２種類あることはこのときに確認済みなので(20201101p01.02.01)、今回は使いやすい方を選ぶことができた。
珍しく解答の中にコメントがあるのは、書いておかないと脳みそからあふれて何度でも最初から考え直しになるからです。紙と鉛筆を用意すべきなんだよなあ。
本番中は残り時間が 30 分しかなかったので問題文が短い F 問題に先に取りかかっていた。同じように考えたかどうかはわからないが、E 問題より F 問題の方が多くの人に解かれていたようだ。自分はどちらも解けなかった。
制約が３重ループを許すと言っている。
解答の後半はもう３回目になるあの形。実行速度にハンデを背負った Ruby でのタイムの詰め方は、このときに研究し尽くした>E 問題 Traveling Salesman among Aerial Cities。
惜しい。とても惜しい。時間制限が２秒なのだけど、実行を打ち切られたときは 22xx ms というタイムになる。32 ms 詰めれば AC になるぞ。
ハッシュ表を使っていたところで配列を使ったら余裕の AC。
必然性があってハッシュテーブルを選んでいたわけではなくて、Hash のデフォルトプロックありきでスクリプトを構成していたから、使っていた。TLE は邪道の報い。
実は唯一の TLE は最も重いケースではなかった。この提出では TLE だった 21_large.txt のタイムが 135 ms だ。
前半部分で選ばれた魔法石がどうがんばっても連結できないとわかれば、後半の３重ループはスキップできる。そういうこと。
前半部分で距離の確定を双方向からやらずに片方向で済ませてみたら、平均的には速くなったけど、一番遅いケースでは 25 ms しか違わなかった。
Integer#times を while ループにするだけで 200 ms 縮んでやんの。そんなに違うの？ times はイテレータの中では速い方だと思ったけど。
転倒数って固有名詞なのかな。公開された PAST の過去問をやったときに見た>20201111p01。K 問題。それが解いてあった(提出 #18029328)からといって、何かが役に立ったということはない。残念。
最初に、k を増やして数列の初項を最後尾に送り込んだときに、転倒数がどのように増減するかがわかった。わかったからわかったとしかいいようがない。こねくっていたら、転倒数の増減が簡単な計算で求まることがわかった。
それから、転倒数の初期値の求め方を考えた。BIT で殴るのではない、頭のいい方法があるのではないかと考えたが、思いつかなかった。
BIT です。Ruby や Python で速い提出も同じだったので、転倒数はこう求めるのだ！ という頭のいい方法はないのかも。
実は A 数列をスキャンして作成していた配列 I は不要だった。
BIT を使って転倒数を求める手順も、考え方次第でひと通りではないということ。ソート列を必要とする方法よりは必要ない方法を、BIT へのお伺い(対数時間)が２回になる方法よりは１回で済む方法を選びたい。脳みそはタダだけど計算資源は有限。
最終更新: 2021-05-07T14:34+0900
今日の ABC。
制約がよく見かける 10^5 ではなくて 10^4 だから雑なやり方でも通る気がしたんだけど、そんな仏心が期待できるはずがなくて、時間が厳しいからこそ制約が緩めてあるのだなあ。Ruby では D 問題よりも解かれてないみたい。
AtCoder のことを初めて日記に書いた記念すべき日「脳log[20190907p01] AtCoder Beginner Contest 140 E問題」を思い出して書いた。
不安だからそのままにしたけど、今回は更新と更新のあいだに参照が１回だけだから、番兵も１つで足りたと思う(これに対する答え>「実のところ
」)。+ [N, N] と + [-1, -1] は完全なるコピペ。+ [N] と + [-1] ではダメだったものがどうしてこれで正しい答えにつながるのか、さっぱり理解していない。RU[N] と LU[-1] に番兵を１個置くのと２個置くのの違いとは。
ソートで配列を比較するのが贅沢で余分な時間を使ってるみたいだったのを修正した。88 ms → 68 ms
多重代入部分を読み解く参考に>20201124p01, 20200428p01.08.01
主流の解き方ではデータを蓄えたり捨てたりしながら数列を前から一度だけスキャンするみたい。何を蓄えて何を捨てるんだろう。わからない。ピークの情報は残しておいてもしかたないな。現在の要素をピークとして左側への広がりが知りたいかな。上昇トレンドでは広がりに意味がないな。
2 WA のち AC。数列を１回通り抜けるだけ。上昇トレンドでインデックスを記録しておいて、下降局面で幅を確定する。
あ、これ８行目の if が常に true でバグってる。
これが(バグ修正済みの)本当の O(N) 解答。バグといっても等しい要素が多いときに無駄がある、という程度だったみたいだけど。
C 問題でこれをイチから考えるのはあまりに酷だけど、実は O(N^2) が通る制約だったらしい。Ruby で 10 メガや 100 メガが秒未満は無理だと思うけど。
ここで紹介されている方法が O(N)。自分の(前２つ)はソートしてるから O(NlogN)。
さっきリンクしたのと同じ日記だけど、「Rubyで一番速いのはこれ。345ms」として参照したのと同じ解法。愚直に検索する O(N^2) 解法の改善案として素直に理解しやすいと思う。
数列がソート済みであればあるほど改善効果がなくなるのではないかな。クイックソートみたい。
#ここがよくわからない #●●●しない限り、次に来る高さと取り出した長方形の最後のインデックスをスタックの中に入れる
わからないのがよくわかる。自分が O(N) 解法を書くにあたって 2 WA した原因がここだから。
要するに、「取り出した長方形」は「次に来る高さ」よりも高い要素なわけだから、次に来る高さの上位互換であるわけ。その「最後の」(=最も左の)インデックスを、次に来る高さの左方への広がりとして記録している。
アフィン変換を検索して見よう見まねで書いた。１時間かかった。TLE だった。これ以上はもう余力も時間もなかった。無念。
対称移動のための行列は３つの積ではなく２つの積で表現できるし、それも自分で計算して１つにできる。でもそれだけでは TLE のままだろうな。行列の掛け算をただの配列同士の掛け合わせとして自分で書いてみたりもしたけど、７秒が６秒になるだけだった。
競技プログラミングをするフレンズ @kyopro_friends Jan 23
アライグマ「E問題は、(0,0),(1,0),(0,1)の3点だけシミュレーションすれば全部計算できるのだ！」
な、なんだってー。
汎用的に点を動かそうとするのでなく、具体的に基底を動かすってことなんかな。だけどそのシミュレーションをするのに行列を使ったら元も子もないので、どうするの？ 頭が働かないから行列におまかせしていたんだけど、どうしたらいいの？
軸に平行な直線で折り返すのはまあできる。90度回転は x と y を入れ替えたり符号を入れ替えたりで、たぶんできる？ 個々の点の座標を求めるのは……？
まあ、TLE 提出を見れば行列って形で式が見えてるんだから、計算できないはずがないんだよなあ。
いやー、厳しい。ヒントがあってもいくつも穴にはまって時間がかかる。「まあできる」とか言っていた折り返しも実はできなかった。
ここでやったことと蟻本に書かれていた(けど解らない)「実は、m 項間漸化式の n 項目は行列を用いるのではなく、各項を初項の線形結合で表して繰り返し二乗法を行うことにより、O(m^2log(n)) で計算することも可能です。興味のある人は考えてみるとよいでしょう」に関連はありますか？
移動後の点の X 座標ないし Y 座標を求めるのに、a+x*(b-a)+y*(c-a) の式を使うと遅い。どうせ同じ数の係数を蓄えておくなら、a+b*x+c*y で答えが求まるような係数を用意したい。
でも何を考えて係数を変換していけばいいのかわからない。
a,b, c,d, e,f の初期値を 0,0, 1,0, 0,1 として、操作１～４でどのようにマッピングしていくか。
| 遅い方 | 速い方 | 備考 | |
|---|---|---|---|
| 操作１ | b,-a, d,-c, f,-e | b,-a, d,-c, f,-e | 同じ |
| 操作２ | -b,a, -d,c, -f,e | -b,a, -d,c, -f,e | 同じ |
| 操作３ | p2-a,b, p2-c,d, p2-e,f | p2-a,b, -c,d, -e,f | 一部 p2 の省略 |
| 操作４ | a,p2-b, c,p2-d, e,p2-f | a,p2-b, c,-d, e,-f | 一部 p2 の省略 |
| 移動後の座標 | (a+(c-a)*x+(e-a)*y, b+(d-b)*x+(f-b)*y) | (a+c*x+e*y, b+d*x+f*y) | 引き算が不要 |
遅い方は各操作で余計なことをしていて、移動後の座標を求めるときにも余分なことをさせられている。そりゃあ遅くなるはずだけど、何を念頭に置けば速い方の式が書けるのかわからない。
遅い方を書くときは、基底となる２つのベクトルを定める３点を移動していくつもりで書いていた。
速い方でも (a,b) の意味はただの点なのでわかる。でも (c,d) と (e,f) に何のイメージを割り当てればいいのかわからない。それこそ向きと大きさだけで位置を定めない、ベクトルそのもの？ そうかもね。そうなんですか？