最終更新: 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) に何のイメージを割り当てればいいのかわからない。それこそ向きと大きさだけで位置を定めない、ベクトルそのもの？ そうかもね。そうなんですか？
s.visited という行を s2.visited に書き換えて８行か９行下に持って行くと、30秒もかからずに終了しましたよ(そして9305手の履歴を表示した)。そもそも Ruby 2.7 では元のままでも５分かからずに(書いてある通りに) SystemStackError が出たのであるが。■■■@2023-10-02 バグみっけ。箱入り娘.rb の 30 行目。Array#uniq にブロックを渡して処理を行っているが、このブロックは uniq メソッドの一部として働くのであって、uniq した結果が渡されてくるわけではないんだよね。Array#split にブロックを渡す用法があるのを知って以来、隙あらば each を省こうと狙っているのだけど、Array#zip と Array#product は良くても uniq メソッドは間違い。処理が重複して無駄になっていた。最終更新: 2021-03-02T17:55+0900
最終更新: 2021-01-16T18:37+0900
Coprime はまた解けなかった。WA ではなくなったけど TLE が解消しない。
最終更新: 2021-05-04T21:04+0900
AtCoder Problems がお勧めする Moderate な問題(緑difficulty)を上から順に解いた。半年前に解けなかった問題も１年前に解けなかった問題も解けた。だから０完だったこの前の ARC 111 は忘れよう。
過去問はテストケースが利用できる。DropBox からダウンロードするとコンテストの各問題ごとに in フォルダと out フォルダが解凍される。
ARC111_A フォルダの中がこうなっているとする。
そこで次のように実行する。(ARC111_A> はプロンプト)
ARC111_A> attc my_answer.rb
attc.bat の中身がこう。
@echo off
for %%F in ("in\*") do (
call :run "%~1" "%%~F"
)
exit /b 0
:run
echo %~1 ^< in\%~nx2
call ruby27 "%~1" < "in\%~nx2" > "out\%~n1.out.txt"
fc /A "out\%~n1.out.txt" "out\%~nx2"
del "out\%~n1.out.txt"
echo.
exit /b 0
カレントディレクトリの in フォルダの中身を入力として引数のスクリプトを ruby27 コマンドで実行する。出力を out フォルダの同名のファイルと fc コマンドで比較する。
call ruby27 という風に call が付いてるのは ruby27 が exe の名前ではなくて、C:\Program Files\Ruby27\bin に PATH を通してから ruby.exe を呼び出すバッチファイルの名前だという固有の事情から。
別に call でなくて当たり障りのないコマンドならたぶん何でもいいんだけど、call|ruby27 という風にパイプを通すと新しいコマンドインタープリタが起動するので、呼び出したバッチが setlocal してなかったとしても現在の環境(PATH 変数とかカレントディレクトリとか)が汚染されなくなるというハックがある。cmd /C "ruby27 ..." と同じことなんだろうけど、そっちは引数が引数になって二重の引用符が面倒の種だよね。
tc は Test Case の略だけど、 AtCoder の略が at か ac かで定まらないから、attc と actc の両方の名前でバッチを用意してる。ハードリンクにしたら中身の同期に手間もかからないし。
アナクロだけどそれなりに便利。
ご飯を作ってあげたときに「美味しいよ」とか「ありがとう」の前に「鶏肉をもも肉からむね肉にしたんだね、さっぱりとした味になっているね」とか言われたらそりゃモヤモヤするよ」 相手に感謝を伝える、それは喜ばせようという働きかけであり、愛情があればその意思を持つのが当たり前である、ということを学習すればいいように思う。意図をもって働きかける意思が持てればいいと思う(操作か支配かと忌避感があるけどね)。変化を恐れず、相互作用を起こし、相手の反応を楽しむべく努力しよう。相手の喜びこそ自分の喜びとしよう。■私はそれができない。■「
ふたりで、ひとつに、なれちゃうことを、きもちいいとおもううちに、すこしの、ずれも、ゆるせない、せこいにんげんになってたよ」 善し悪しだけど良さをまだ知らぬ。