/ 最近 .rdf 追記 編集 設定 本棚

脳log[20210123] AtCoder Beginner Contest 189/C,E



2021年01月23日 (土) [AtCoder] NoSub に関して @evima0 さんのこのツイートがえらいと思う。「現在の AtCoder ではコンテストで一度も提出しなかったら (できなかったら) 不参加扱いですが、問題を読み始めた瞬間に参加扱いにすることを検討しているようです。」■ NoSub 即不正みたいな論調ばかりで想像力の足りない連中に言いたい。NoSub したくてする奴なんざいねーんだよ。いつだって誰だって全完できるなら全完したいしそうするに決まってんだよ。A 問題のサンプルを通す解答すら用意できなかったから NoSub になるんだよ。もちろん戦術的 NoSub の選択肢は知っている。でもそれが?■パフォーマンスの良かった回だけピックアップすることでレイティングが上振れするとしても、その範囲は精々色半分程度ではないか。自分の場合、緑が水色にはなるかもしれない。でも青パフォ黄パフォなんて見たこともないから、粉飾しても青黄の目はない。■にもかかわらず NoSub を含む戦術を駆使してレイティングを良く見せようとする人間は、自分がその程度伸びる未来も描けない終わった人間だと俺は思う。何を気にかける必要がある? そんな他人の足なんざどうでも良かろう。

最終更新: 2021-05-07T14:34+0900

[AtCoder] AtCoder Beginner Contest 189/C,E

今日の ABC。

 C 問題 Mandarin Orange

制約がよく見かける 10^5 ではなくて 10^4 だから雑なやり方でも通る気がしたんだけど、そんな仏心が期待できるはずがなくて、時間が厳しいからこそ制約が緩めてあるのだなあ。Ruby では D 問題よりも解かれてないみたい。

 提出 #19612283 (AC / 190 Byte / 88 ms / 15720 KB)

AtCoder のことを初めて日記に書いた記念すべき日「脳log[20190907p01] AtCoder Beginner Contest 140 E問題」を思い出して書いた。

不安だからそのままにしたけど、今回は更新と更新のあいだに参照が1回だけだから、番兵も1つで足りたと思う(これに対する答え>「実のところ + [N, N]+ [-1, -1] は完全なるコピペ。+ [N]+ [-1] ではダメだったものがどうしてこれで正しい答えにつながるのか、さっぱり理解していない。RU[N]LU[-1] に番兵を1個置くのと2個置くのの違いとは。」)。

 提出 #19649425 (AC / 167 Byte / 68 ms / 15644 KB)

ソートで配列を比較するのが贅沢で余分な時間を使ってるみたいだったのを修正した。88 ms → 68 ms

多重代入部分を読み解く参考に>20201124p01, 20200428p01.08.01

主流の解き方ではデータを蓄えたり捨てたりしながら数列を前から一度だけスキャンするみたい。何を蓄えて何を捨てるんだろう。わからない。ピークの情報は残しておいてもしかたないな。現在の要素をピークとして左側への広がりが知りたいかな。上昇トレンドでは広がりに意味がないな。

 提出 #19675442 (AC / 201 Byte / 69 ms / 15096 KB)

2 WA のち AC。数列を1回通り抜けるだけ。上昇トレンドでインデックスを記録しておいて、下降局面で幅を確定する。

あ、これ8行目の if が常に true でバグってる。

 提出 #19679788 (AC / 199 Byte / 66 ms / 14984 KB)

これが(バグ修正済みの)本当の O(N) 解答。バグといっても等しい要素が多いときに無駄がある、という程度だったみたいだけど。

C 問題でこれをイチから考えるのはあまりに酷だけど、実は O(N^2) が通る制約だったらしい。Ruby で 10 メガや 100 メガが秒未満は無理だと思うけど。

 ヒストグラム中の最大長方形の面積を求める

ここで紹介されている方法が O(N)。自分の(前2つ)はソートしてるから O(NlogN)。

 提出 #19680172 (AC / 297 Byte / 69 ms / 15104 KB)

さっきリンクしたのと同じ日記だけど、「Rubyで一番速いのはこれ。345ms」として参照したのと同じ解法。愚直に検索する O(N^2) 解法の改善案として素直に理解しやすいと思う。

数列がソート済みであればあるほど改善効果がなくなるのではないかな。クイックソートみたい。

 提出 #19700600 (corazon さん / AC)
#ここがよくわからない
#●●●しない限り、次に来る高さと取り出した長方形の最後のインデックスをスタックの中に入れる

わからないのがよくわかる。自分が O(N) 解法を書くにあたって 2 WA した原因がここだから。

要するに、「取り出した長方形」は「次に来る高さ」よりも高い要素なわけだから、次に来る高さの上位互換であるわけ。その「最後の」(=最も左の)インデックスを、次に来る高さの左方への広がりとして記録している。

 E 問題 Rotate and Flip

 提出 #19644038 (TLE×6 / AC×24)

アフィン変換を検索して見よう見まねで書いた。1時間かかった。TLE だった。これ以上はもう余力も時間もなかった。無念。


対称移動のための行列は3つの積ではなく2つの積で表現できるし、それも自分で計算して1つにできる。でもそれだけでは TLE のままだろうな。行列の掛け算をただの配列同士の掛け合わせとして自分で書いてみたりもしたけど、7秒が6秒になるだけだった。


競技プログラミングをするフレンズ @kyopro_friends Jan 23

アライグマ「E問題は、(0,0),(1,0),(0,1)の3点だけシミュレーションすれば全部計算できるのだ!」

な、なんだってー。

汎用的に点を動かそうとするのでなく、具体的に基底を動かすってことなんかな。だけどそのシミュレーションをするのに行列を使ったら元も子もないので、どうするの? 頭が働かないから行列におまかせしていたんだけど、どうしたらいいの?

軸に平行な直線で折り返すのはまあできる。90度回転は x と y を入れ替えたり符号を入れ替えたりで、たぶんできる? 個々の点の座標を求めるのは……?

まあ、TLE 提出を見れば行列って形で式が見えてるんだから、計算できないはずがないんだよなあ。

 提出 #19690206 (AC / 619 Byte / 1497 ms / 103080 KB)

いやー、厳しい。ヒントがあってもいくつも穴にはまって時間がかかる。「まあできる」とか言っていた折り返しも実はできなかった。


ここでやったことと蟻本に書かれていた(けど解らない)「実は、m 項間漸化式の n 項目は行列を用いるのではなく、各項を初項の線形結合で表して繰り返し二乗法を行うことにより、O(m^2log(n)) で計算することも可能です。興味のある人は考えてみるとよいでしょう」に関連はありますか?

 @2021-02-06

移動後の点の 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 として、操作1~4でどのようにマッピングしていくか。

遅い方速い方備考
操作1b,-a, d,-c, f,-eb,-a, d,-c, f,-e同じ
操作2-b,a, -d,c, -f,e-b,a, -d,c, -f,e同じ
操作3p2-a,b, p2-c,d, p2-e,fp2-a,b, -c,d, -e,f 一部 p2 の省略
操作4a,p2-b, c,p2-d, e,p2-fa,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)引き算が不要

遅い方は各操作で余計なことをしていて、移動後の座標を求めるときにも余分なことをさせられている。そりゃあ遅くなるはずだけど、何を念頭に置けば速い方の式が書けるのかわからない。

遅い方を書くときは、基底となる2つのベクトルを定める3点を移動していくつもりで書いていた。

速い方でも (a,b) の意味はただの点なのでわかる。でも (c,d) と (e,f) に何のイメージを割り当てればいいのかわからない。それこそ向きと大きさだけで位置を定めない、ベクトルそのもの? そうかもね。そうなんですか?