/ 最近 .rdf 追記設定本棚

脳log[2022-12-13～]

最近ひとつ現在へひとつ過去へ

2022年12月13日 (火) [AtCoder] ツイッターの検索結果に Swap 解いたーというツイートが流れていて、見ると自分は過去に解いている。でも問題を見ても自分の提出を見ても解き方がわからない。ほぼ１年前の当時の日記(20220116)を読んでようやく理解した。１年前はものを考えていたし頭も回っていたらしい。高くもないピークを越えて現在は劣化中……。

ツッコミを入れる

2022年12月08日 (木) [AtCoder] 精進。CODE FESTIVAL 2016 qual C-D「Friction」(黄 diff)。AC じゃないよ、部分点だけ。ローカルで最大ケースが安定して 50 秒だから、ジャッジサーバーが倍速だとして 13 倍の定数倍改善で通ると思う。■まずは問題を理解する。摩擦が発生するのは列と列のあいだ。最小単位２列について考える。戦略としては右をどんどん下げていくか、左をどんどん下げていくか、どこかのレベルからは左右を交互に下げていくことで摩擦を最小にできそう。端っこを除いては摩擦面が左右にあるけど、それによって一面の都合によって下げたいけど他面の都合で下げたくないというジレンマは生じなさそう。全体を通して下げる順番を調整すればどの摩擦面にとってもベストな選択が可能。そういう調整が可能なので列を下げるか上げるかには違いがない。一貫してさえいれば、配列を反転したりしなくていいし、頭の中を決まった方向に整理したりしなくていい。■提出 #37100541 (300 点 / TLE×13)。メモ化 DP。提出総数が少ないというのはあるけど、Ruby によるすべての提出を見ても AC がない。できるはずだ。■累積和の要素数をケチったのとメモを Hash から Array に代えたら 24 秒になったけどこれは２倍の改善でありあと６倍足りない。しかも答えが一部合わないし。■答えが合った。コードテストで 10.X 秒だからやっぱりあと６倍(切り上げ)の改善が必要。■メモ配列を無理に１次元化せず２次元配列にしたら 8.2 秒になった。■演算子をケチって 7.6 秒になった。■lambda を普通のメソッドにして 6.9 秒。AC は 2 秒……。再帰じゃなくてメモ配列を埋める普通の DP にしたらどうかなあと思うけど、右を下げる遷移と左を下げる遷移をどんな感じで一列に並べてループにできるか迷う。■どうも考察が足りてないみたい。こちらの提出 #949122 (PyPy / AC / 989 ms) を Ruby に移植してみたら 4.6 秒だった>提出 #37243589 (TLE×12)。よくわからない遷移。そしてすでにミニマムなこの解答を倍以上速くすることは無理だ。Ruby の将来に期待！

ツッコミを入れる

2022年12月05日 (月) 隻狼(SEKIRO)クリアした！だいたい３年前(20200113)に日記に書いたあと、源の宮を探索して桜竜の直前で根気が尽きてやめてしまっていた。以前見ていたこれらの動画「【隻狼-SEKIRO-】やがて玄人になる。」「SEKIRO-隻狼-「トロフィー100＆やり込み解説」」「SEKIRO（隻狼）実況 END」を見返しているうちにまた自分でもやりたくなってきたのだった。一度終盤まで行ってるし余裕余裕とイチから始めたんだけど、やっぱりいっぱい死ぬのんな。弾きはおろかジャンプステップダッシュすら覚束なくて最初の雑魚敵に殺されたし。だけど鬼庭形部雅孝とか大忍び梟とか義父とか破戒僧とか、以前いっぱい死んだボスはさすがに体が覚えていてそんなには死ななかった(でも何度かはミスであっさり死ぬ)。今回は侍大将と七本槍と重蔵と孤影衆と蛇の目タイプの敵との戦闘が楽しめるくらいになった(それまでにいっぱい死んだ)。戦闘が楽しめるというのは、すでに何が来ても(ほぼ)対応できるのであって、テキトーに近づいてテキトーに斬りつけてみて何が返ってくるかなーと成り行きを楽しむことができる状態。それでも弾きミスだったり攻撃が被って相打ちになったり対応が難しい攻撃が一部残っていたりで退屈はしない。ミスから死までが近いんだ。ラスボスの弦一郎と一心様にも鍛えられた。前回も今回も天守での弦一郎戦は身体力と回復瓢箪に物を言わせて押し切ってきたので、一心戦の前座として出てくる最終戦で初めて動きを見極める必要に迫られた。うまくいくときはノーダメージもあったけど、２時間以上やっていて勝率は５割を超えなかった。お前前座じゃなかったのかよ。一心様１段階目はわりとハメパターンに持ち込める。攻撃を中断して律儀に弾いてくれるからだと思う。居合いに付き合う必要はない。一文字は狙い目。２段階目は刀と銃と槍の連撃をテキトーに弾きながら見切りで体幹ダメージを稼ぐ感じ(チャキチャキ)。ただし突きは連撃の最後なのでそれまでに倒れてたら見切れないよ。そういうケースがいっぱいあったんだよ。ため攻撃に付き合わないのと一文字が狙い目なのは同じ。３段階目は２段階目とほとんど同じ。追加された雷攻撃がこちらにとってはボーナスなんだけど、あまり使ってこないのと、横薙ぎの方は当ててくれないから返せないしで、そんなにうまみはなかった。３段階目までたどりついたのは全部で３回くらい。数少ないチャンスなのでおくるみ地蔵とおはぎまで使って倒した。３年前に「脳筋なので弾き一辺倒で押し切りたい」と書いた。弦一郎も一心も体幹がたまりやすいボスで体力を削ることを意識する必要がなかった。自分は弾きや防御から攻撃に転じるときに暴発しやすい流派技は常に外していたし、最後は義手忍具も外していた(鐘鬼は外さなかった)。弾き(L1)と攻撃(R1)だけで戦える、非常に満足度の高いラスボス戦だった。一心様の剣技って葦名の侍に受け継がれてるんだよね。予備動作が小さくて予測しづらいすくい上げる技は武者侍りの侍も使う(でも一心様の方が力みがなくて振りがコンパクトな気がする。完成度)。一文字や十文字は隻狼自身が修得している。だから初めて戦うけど全く知らない動きではない。胸熱だしフェアだと思う。ラスボス戦 (432 MiB！)■２周目の梟 (259 MiB！)。２周目は３回目で倒せた。■２周目の弦一郎・一心は１日１時間として４、５日かかった。まだ死に足りないらしい。■２周目はね、なぜかお米ちゃんがお米を補充してくれなくてお米もお米から作るおはぎも手に入れられなかった。最初のお米を菩薩谷のババアにあげてしまってそれっきり。なんでなん。細雪(３個まで一度に持てるお米の上位版)を持ってるせいではないと思う。２周目だから傀儡の術を最初から持っていて仙峯寺のフラグ立てが狂った？小太郎に死体漁りをさせたのが気に入らなかった？■おはぎから連想したんだけど、エリザベスの名前ってエリンギからきてるよね。全然気付かなかった。あの姿を見てエリンギだと思わなかったし、エリンギだと指摘するコメントを見てもエリザベスと関連付けられなかった。■心中の弦一郎にはまだ勝ててないんだけど心中の一心には２回目の連戦で勝てた。しずくも地蔵もお米もおはぎもなしで瓢箪だけで。２周目のラスボス戦で十分に死んでいたってことかな。一心様弱くなった説もあるな。自分が認知している変化は３つで、１つは突き一辺倒だった危険攻撃に下段を混ぜてきたこと。２つ目は不死斬りを使った攻撃の追加。３つ目は共通の下段攻撃から始まる連続攻撃で派生が２種類あるものの追加。追加された不死斬りも連続攻撃も大技過ぎて必ず対処を要求してくる。対処できるし、対処するし、そのとき攻撃チャンスが生じている。■＠2023-01-23 ３周目の梟は２回目で、３周目の義父は１回目で倒せた。３周目の梟 (249 MiB！)。なんだかんだ対処できるという気易さがあるせいでこれまでで一番テキトーなムーブになっている。弦一郎戦についてひとつわかったことがあって、防御されようが弾かれようが斬り続けていくことで多くの攻撃を潰せる、ということ。スーパーアーマーの時だけ手を休めて対処する。順番のせいもあるけどやっぱり一心様より弦一郎の方に多く殺されている。巷で言われているより強いよ、弦一郎は。一心様の呼吸がだいぶわかってきたのか、３周目は２周目より死ななかった。こちらの行動次第で対処しにくい下段に派生させないようにできるし、逆にこちらが対処しやすい突き攻撃を待つこともできるので、うまく走り回ればまあまあ勝てる、何日目かには。３周目の弦一郎・一心 (313 MiB！)。

ツッコミを入れる

2022年12月04日 (日) [AtCoder] 精進１。CODE FESTIVAL 2016 qual B-C「Gr-idian MST」(青 diff)。１辺が 10 万のグリッドだから辺に沿った処理は通るけど (辺×辺) の処理は通らない。UnionFind のような具体的個別的な処理ではなく、何か規則に沿って処理をまとめなければいけない。まず、造る道路の数は頂点数マイナス１に決まっている。最も低コストな道路はそれが縦であれ横であれ造れるだけ造らないという選択肢がない。では２番目３番目のコストの道路は……。提出 #37039797 (AC / 167 Byte / 173 ms)。あるコストで造れる行方向(列方向)の道路を１通り造ったら、行に対しては列、列に対しては行方向の道路を造る際の必要数が１つ減る。その繰り返し。■精進２。同-D「Greedy customers」(青 diff)。まず単純なケースとして列が昇順の場合と降順の場合を考えた。降順の場合、後ろの人を狙って物を買わせることはできない。昇順の場合はできるけど、いずれ前の人が邪魔になる。先頭の人の所持金を１刻みで残金１まで毟り取れることは決まっているしそうしない理由もない。先頭の人から順番に狙い撃ちにするので良さそう。１人目の所持金を１まで減らしたとして２人目の所持金が１のときは？２のときは？３のときは？４のときは？５のときは？提出 #37040436 (AC / 120 Byte / 89 ms)。よーく考えた。WA になる例外ケースがありそうな気がしたので先頭の要素だけ特別扱いしたりもした。■精進３。CODE FESTIVAL 2016 Final (Parallel)-C「Interpretation」(水 diff)。以前に見た問題だけどまだ解けていなかった。さすがに前回と前々回の ABC-F がともに UnionFind がらみだったので(でもどちらも時間内には解けなかった)、その適応を見逃したりはしない。提出 #37040679 (AC / 327 Byte / 175 ms)。人と言語を２列に並べた２部グラフを考える。今回は解法から発想したので気付かないまま、いわば偶然 AC に至ってしまったけど、問題文を読解するにあたってコミュニケーションが取れることの条件「2 人ともが話すことの出来る言語が存在する」ことと「2 人ともが X とコミュニケーションを取ることが出来る」ことの違いをよく意識しなければいけない。２つの条件でそれぞれ使われている「共通言語が存在する」ことと「コミュニケーションが取れる」ことはイコールではない。共通言語の存在は再帰関数の停止条件であり、コミュニケーションが取れることは共通言語の存在により再帰的に定義されている。後になって問題を反芻していたとき、X 以外の別の人間を介在させてコミュニケーションが取れると判断してはいけない気がして、なんで AC だったのか疑問に思って問題を読み直して、表現の違いに気がついたのだった。■なんだかんだで青 diff が半分くらい埋まってきてるので、そろそろ青入りさせてくれてもいいんですよ。

ツッコミを入れる

2022年12月03日 (土) [AtCoder] 精進。今日あったデンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)-F「Pay or Receive」(青 diff)。ヒント、というかほぼ答えを見ました。「へえFってベルマンフォードじゃなくてweighted unionfindってやつ使うのかルジャンドルも知らなかった」「F: 初見ベルマンフォードかなと思ったけど、制約で間に合わないので却下。辺のコストからポテンシャル定義できることに気づいて、ポテンシャル付きUnionFindを着想。無限にできるかは、閉路ができた時の相対高さで判断できる」一応自分でも UnionFind の可能性が頭をかすめていたけど、構成する辺のコストの和が非ゼロになるサイクルがあるときでも、サイクルから伸びた腕の中では inf 以外の答えが定義されるような気がして、強連結成分分解が必要だと考えてしまった。解ける可能性はなかった。■提出 #37002677 (AC / 758 Byte / 433 ms)。バグなしで完成してびっくり。UnionFind と言いながら公開関数は U(nite) 関数と DD 関数の２つ。F(ind) 関数は内部でしか使わないので非公開。DD 関数を difference between distances from a root から命名したんだけど、ルートからの距離(D)とは別に２点間距離をあらためて D(istance) と命名しても良かったなとどうでもいい後悔をしている。うまくすれば場合分けが省けるかなと期待して負の無限大を値として使用したけど、無限大と無限大の差から NaN を作ってしまうしょうもないバグを踏みそうで結局 if/finite?/infinite? による場合分けが避けられなかったのが残念。

ツッコミを入れる

2022年11月30日 (水) [AtCoder] 精進。ABC129-E「Sum Equals Xor」(水 diff)。数週間前には解けなかった問題。今日の思いつきはこう。ある１のビットを選んで倒す。そのとき、左にある１のビットを a,b のどちらかに割り振る。右にあるビット(0/1 を問わない)は a,b のどちらかを選んで立ててもいいし、a,b ともに０でもいい。これで重複なく数えられる。あとは１のビットを１つも倒さない場合の割り振りを忘れずに。提出 #36886000 (AC / 142 Byte / 133 ms)。

ツッコミを入れる

2022年11月29日 (火) リツイートされていたことで観測した１つのツイートに対する反応集。■１「何がひどいのか全く指摘していない点でひどい感想文だなという印象。論文で扱っていない因子の話がしたければレター書いたら建設的だが、しないんだろうなあ。」■２「シニア研究者の配慮を欠いた発言により、こうやってまたシニア研究者や大学教員に対する評価が下がっていくのである。」■３「論文に対して意義を述べるのは自由です。ただ、科学雑誌に掲載された論文を「ひどい論文」と表現するのは研究者として如何なものかと思いますね。同じ地球惑星科学に関わる人間として残念です。」■４「本当に悲しいです。陸水学を代表する先生に「ひどい論文」と評価されました。共同研究者全員で3年間必死になって積み上げてきたことを、すべて崩れた形に。アメリカで私は何を勉強してきたのか。本当に悲しいです。」■ひとつを除いて共感できないんだよなあ。言いたいことは「悲しい」だけ？感想ひとつで研究成果が崩れちゃうの？論文にも論文誌にもピンからキリまであるらしいので、科学雑誌に掲載されたことをもって「ひどくないもん」と主張されてもなんだかなあ。精々確からしいのは最低限の水準と体裁をそなえた「論文である」というあたりでは？欠けているのも求めているのも配慮なの？思慮ではなくて？そこからあなた自身の論文への評価を読み取っても構わない？シニア研究者や大学教員に対する評価への心配は大きなお世話じゃない？対象を個人からカテゴリに拡大しているのはあなたであって、空気の代弁者気取りはいらないよ。アカデミアを構成しているのも人間なんだなあ、というのが自分の感想。お気持ちだけで戦うの？たぶん２のツイートはゼミ生募集に際してあからさまな女性優遇を隠しもしなかった帝京大学教授に関する報道を踏まえたものだな。流れはわかったけど同列に扱うべきかどうかはわからない。自分は渦中の論文が本当にひどいものかどうか判断できないから。研究者の顔と教育者指導者の顔は別物で両方あっていいと思うから。

ツッコミを入れる

2022年11月26日 (土) [AtCoder] 今日はトヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)があった。コンテスト成績証。A-E ５完(1500 点)の中では最速級だったらしい。これ以上は望むべくもない結果だけど、でも、１時間以上あるなら F も通そうよ。難しい問題ではなかったと思うよ。解けなかったけどさ。終了後の提出(#36829850)も TLE だったけどさ。■精進。F 問題「BOX」(青 diff)。提出 #36832919 (AC / 443 ms)。できてると思ってた経路圧縮ができていなかったのが TLE の原因だった。普通の UnionFind にくらべてレイヤーが１枚多い感じで、いつもの Find 関数が表層の１つ下層に隠れていた。表層のショートカットだけ更新していて隠れていた Find 関数の経路圧縮ができていなかった。■宿題だった F が片付いたので気持ち良くふり返りたい。D 問題「Freefall」(茶 diff)。サンプル３について、自分の AC 提出の出力が `8772053214553.691` な一方、出力例が `8772053214538.5976562500` となっている。差は 15 とちょっと。これが「出力は、真の値との絶対誤差または相対誤差が 1e-6 以下のとき正解」という条件を満たすかどうかの判断がひとつの分かれ目だったらしい。自分は何か月か前あたりに、絶対誤差と相対誤差を正確に計るとこういう式になるのだけど……(でも必ずしも停止条件を厳密に計る必要はないよね)、的な文章を読んでいて、大きい値の相対誤差は(絶対値的には)そこそこ大きい値でも許されるんだなあ、というような、今では式もよく覚えてないけど意外性の発見があったことだけは覚えていたので、通るような予感があった。祈りながら提出して 1 WA でも返ってきたらどうしようもないなと戦々恐々としていたのも本当のところだけど。解法は g を探索する整数の二分探索(Range#bsearch)。だけど g におけるタイムと g+1 におけるタイムを比較して判定条件にしたので実質的には三分探索だった。こんなに簡単素直な解法でいいのかと疑ったけど、20210401p01.03 に書いたように ABC174-E「Logs」が自分が初めて解いた解を二分探索する問題で、二分探索に対する発想の転換があるまでは解けなかったことを思い出すと、D 問題でこの素直さはありなのかなあとも思った。早々に解析解を提出している人はすごいね。分数とかルートとか、もはや紙と鉛筆があってもなんとかなる気がしない。■E 問題「Cheating Amidakuji」(水 diff)。題意を理解するのがちょっと難しい。ざっくり言うと、A 数列の値に従って B 数列の隣接２要素のスワップを繰り返したとき、B 数列の要素１がどこへ移動するかを追跡する。A 数列の要素の１つを無視した場合(スワップを１つ飛ばした場合)の答えを A 数列の長さと同じ数だけ答えてね、という問題。スワップ対象の $B_{A_{k} + 1}$ が $B_{A_{k + 1}}$ と紛らわしくなかった？ HTML ソースを読んで判断したよ。結局は同じことをしているのかもしれないけど、人によって全然解法の背景にある考え方が違いそうな気がする。自分はといえば、まず最初に A 数列を順番に使用して B 数列のスワップを最後まで完了させた。そして B 数列の初期位置と最終位置の対応を記録した。そして B 数列を初期化してからもう一度スワップを繰り返した。その際に、A 数列のこの要素が関わるスワップを飛ばしたとしたら答えにどう影響するかを考えた。スワップする２つの要素がどちらも１ではなかったら、１の最終位置は変化しない。どちらかが１なら……。■■■@2022-12-07 F 問題を振り返ってなかった。F 問題はボールから箱を引くデータと、箱から箱ラベルを引くデータと、箱ラベルから箱を引く３つのデータを用意した。最初からこの方針だったのだけど、Find 関数の停止条件が明らかではなかったり、箱と箱ラベルを混同したりでなかなかサンプルが合わせられなかった。合ったら合ったで TLE だったしね。箱というのが普段の UnionFind で取り扱う頂点なのだけど、この問題では箱が表に出て来ない。ボールや箱ラベルから間接的に参照されている。こういうのは初めてだったし、要件に対して用意するのがこの３つのデータで間違いないという確信も持てないまま実装していた。自分としては ABC273-E「Notebook」(青 diff) を解いたときと同じ頭の部分を使っていたのであり、そのときみたいにさささっと８分で解きたかった>20221015。でもこっちの問題は骨格を決めた後の実装がちょっとややこしかったね。

ツッコミを入れる

2022年11月25日 (金) 「■DFSを非再帰で書くとTLEになる件再帰になっているものを非再帰に変えると普通は関数呼び出しのオーバーヘッドがなくなるので処理は速くなるはずだ。ところが、DFSを非再帰に書き換えるとTLEするようになったという心霊現象みたいな話はわりとある。添付画像のような記述だ。つづく https://t.co/KU7V0jQfni」■非再帰で迂闊な DFS を書くと TLE になることがあるという一連のツイート。書いてある通りだと思うのだけど、結論が投げっぱなしなので補足的なことを書きたい。再帰関数で書いた DFS を非再帰版に書き換えるというのは、関数呼び出しによってスタック上に暗黙的に確保されていたローカル変数および仮引数のスタック(積み重ね)を、配列などを使い自分で明示的に保存、復元する処理を書いてループを回すということ。ループの１回がだいたい再帰関数の呼び出し１回にあたる。TLE になるのは非再帰バージョンに書き換えたときにパラメータが不足していて状態の復元が不十分だから。不十分でも WA にはならないかもしれないけど、状態と状態のあいだが疎らなために手戻りが発生して TLE になることがある(というのが一連のツイートの内容)。このツイートで再帰関数を呼び出す瞬間と戻ってくる瞬間をよく意識してほしい。隣接頂点リストを走査するループの途中で再帰に突入し、ループの途中に戻って来ている。これを非再帰で書き直すのだから、隣接頂点リストのどこまでが処理済みかという情報まで(明示的な)スタックに保存し、状態を復元しなければ等価な書き換えとは言えない。提出 #36771698 (Ruby / 419 ms / 非再帰 / 頂点番号と隣接頂点リストの添字を記録してループ)。提出 #36771423 (Ruby / 409 ms / 非再帰 / 頂点番号だけを記録しているが隣接頂点リストを破壊的に使用して手戻りを防いでいる)。ちなみに迂闊な DFS をあえて再帰で書くとこうなる>提出 #36774583 (TLE)。隣接頂点リストを繰り返し走査する 14 行目を見れば O(N^2) が納得できると思う。再帰↔非再帰を行き来するときに知らずこのような違いが生じているので TLE でなかったものが TLE になったりする。それゆえに「結論 : DFSを非再帰で書くのはわりと難しい」。でも心霊現象ではないと思うの。■再帰→非再帰の書き換えを初めて意識したのはこのとき>脳log[20050929p01] やねう企画2005年度入社試験。見覚えのあるお名前。■■■@2022-12-21 八百倍役に立つ記事があるよ。「それ、非再帰で書けます - Qiita」

ツッコミを入れる

2022年11月20日 (日) [AtCoder] 精進１。昨日あった ABC278-D「All Assign Point Add」(茶 diff)。クエリ１を愚直にやってはいけないのはわかる。だから Hash を使った。提出 #36620785 (TLE×2)。ちなみにこちらの提出 #36623538 が素直に配列を埋める解法で、全く同じケースに対して TLE×2。どうして２つが同じ性質を示すのかまるでわからない。昨日はもう、TLE になるはずがないと考えてしまって現実に対処するのをやめてしまった。今日の提出１#36664071 (329 ms)。配列２本を使った解法。１つにはクエリ２の累積和を、もう１つには累積和のベースになっているクエリ１のバージョンを記録した。古いバージョンに基づく累積和は無視する。今日の提出２#36664254 (351 ms)。昨日の Hash を使った解法を踏襲したもの。この提出 #36664376 (TLE×2) と比べて間違い探しをしてみよう。Hash#clear を呼ぶと TLE だが代わりに = {} で Hash を使い捨てにすると AC。ベンチマークをとってみても差が出ないので単純に Hash#clear が遅いという話ではない。謎。こういうツイートを見かけた。「AtCoderのABC278D、TLEするのでこんなところで解けないとは耄碌したなーと思ったが… unordered_mapで書いてたところを普通のmapに書き換えたら通った。普通逆じゃないかと思うんだけどまだまだC++、奥が深い。」 Ruby の Hash 実装に固有の秘孔ではないらしい。■精進２。同じ ABC278-F「Shiritori」(水 diff)。D の次に解けたのが F なので E を飛ばして F。bitDP が見えたらちょっと下手なことをしても通る制約。ただし 16 要素の順列はちょっとではない。やるだけ。でもできなかった。提出 #36668555 (AC / 66 ms)。Hash のデフォルトプロックを使ったメモ化再帰で書いた。DP はボトムアップの解法なんだけどメモ化再帰で書くとトップダウンになる。トップダウンの方が頭の中を素直に反映していて書きやすい。気をつけるべきは、DP の詳細を詰めず状態をまとめないままメモ化再帰を書いてもメモ化の意味がないし、TLE になるということ。■精進３。同じ ABC278-E「Grid Filling」(緑 diff)。これが緑 diff ってマジ？俺は制約を見て、h=H/2; w=W/2 のときの計算量を計算して、諦めたよ。D と E のコンボでいじけちゃったよ。提出 #36685628 (AC / 737 ms)。書いてみれば通った。２次元累積和はたぶんかなり苦手にしている。それを尺取りにしようなんてしたら脳みそがオーバーフローしてもしかたがない。実態は「書いてみれば」の語の印象の通りではない。138 ms と飛び抜けて速い提出がある>#36636856。数の種類ごとにそれを覆う最小の矩形を求めておいて、それが黒マスに含まれるかどうかを効率良く(変化量の累積和の累積和で)調べてるっぽい。累積和を使わないとこちらのように短く書けてそれでも通るっぽい>#36649717 (347 Byte / 1586 ms)。まねまね>提出 #36698536 (AC / 560 Byte / 131 ms)。答えを求める部分(末尾５行)をこういう風に書きたいというところと Array#transpose を失敗させない条件から逆算して配列の要素数と添字を調整している。ABC278_e.rb27←これを最終形にしたいけど大勢に影響しない程度の計算量の削減(※黒塗りがグリッドの上(左)にはみ出しているときの変化量を１行(１列)に圧縮した)と見た目の違いしかないので提出を控えている。■今日の ARC152 はどうだったか。自分のすべての提出。１時間半かけて２完のノルマは達成した。B の提出が完成してから 15 分くらい粗探しに時間をかけていた。粗というのは書き損じではなく考え違い。ARC では慎重になる。自分にとって２時間で３問を解くコンテストなので ABC とは違う時間の使い方ができる。昨日の ABC がひどかっただけに慰められる結果。C 問題は B 問題の後だったので図形的な意味はすぐに掴めたのだけど、そこからがさっぱり。解説放送があるよ>「AtCoder Regular Contest 152 - YouTube」。

ツッコミを入れる

2022年11月14日 (月) [Ruby] 「Ruby 3.2.0 Preview 3 リリース」を読んでいたら「Regexpのマッチングアルゴリズムの改善」という項目があった。メモ化によってマッチ時間が改善するという。「Feature #19104 未完了 Introduce the cache-based optimization for Regexp matching」位置と状態をキャッシュするっていうから 20220218 にテキトー書いていたことがあながちテキトーではなかったってことかな。Limitation の項目に書いてあることが面白い。まあそうでしょうという感じ。緩和策なのでそういう場合は無効にするだけ？ ReDoS 一般が話題になった時期があったけど、タイムアウトの採用もあり、見つけた問題を着実に解消しているのだな。

ツッコミを入れる

2022年11月13日 (日) 「『ロマサガ』の自由度と難度が高い理由。『ミンサガリマスター』河津秋敏氏動画インタビューの内容を全編書き起こし | ゲーム・エンタメ最新情報のファミ通.com」■先日整理していた本の中に『Sa・Ga 2 秘宝伝説完全クリア編』があり、94 ページの開発者インタビューに添えられていたプロフィールによると河津氏は 1920 年生まれなので 8 日前に 102 歳になっている(そんなはずがない)。ヤクーツク出身ってなんだ。

ツッコミを入れる

2022年11月12日 (土) [AtCoder] 今日は大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277) があった。コンテスト成績証。自分のすべての提出。ここひと月ほど ARC の開催が途絶えていて、そうするとレートが安定するんだなあ。今回は E 問題でも緑 diff 止まりだった一方、F、G 問題がともに橙 diff だったらしい。F 問題はてっきり自分が苦手なタイプの水 diff だと思っていたので意外。■G 問題「Random Walk to Millionaire」の方が見込みがあると思って考えている。とりあえずサンプルが合うところまではできたのだけど、これは O(KKM) であり K,M≦3000 の制約下では時間オーバー。報酬がレベルの２乗だというところが嫌らしいと思うんだよね。２乗でなければレベルの和と個数を覚えておくだけで良さそうなところが２乗だからまとめることができないでいる。レベルごとに独立して遷移を行うせいで K(移動回数)×K(レベル数)×M(辺の数) の計算が必要になってる。■F 問題「Sorting a Matrix」も考えてる。行のソートと列のソートをそれぞれでがんばれば解ける気がするんだけど、「がんばる」が曲者。行のソートは比較的問題が少なくて、列の統計情報を一度記録しておけば素直に比較ができる。列のソート。行ごとに非ゼロの列を選んでソートして列の序列を作り、マージして１本のソート列にする。入力がすべて非ゼロだった場合、最初のソートに O(HWlogW) かかるのと、扱う２項関係が行×(行内の２項関係) = HW(W+1)/2 個存在するのがつらい。最大ケースで数十秒かかる。あと制約も曲者で、H と W のそれぞれは上限を持っていない。ものすごく縦長の行列もものすごく横長の行列も考えられる。ソート部分の logW がほぼ logHW だったとしても問題はないけど、２項関係の W(W+1) は非常によろしくない。ソート列をソート列として保持したままうまくマージする方法は。それ以前の問題として、エラーなしでは最初の提出 #36477837 (WA×12 / TLE×5) が一番 WA と TLE の数が少ないこともある。愚直にやったものの TLE が一番少ないところと、愚直なのに WA があるところが問題。ケアレスミスなのか根本の方針が答えにたどり着けないものなのか。ダメケースを１つ２つ見つけては結果が改善してるのを確認してるのに提出すると WA 数が何も変わらないのつらい。列のソート(比較)の肝は一方または両方が 0 の行では順序づけを保留することと、同値の場合はグループ化することだというのが今の理解。■@2022-11-14 G 問題。ヒントを見ました。「G は i 回目の移動で頂点 u にレベル X で来る確率が p だとすると、知りたいのはすべての i と $C_{u} = 1$ なる u について $p X^{2}$ の和。(i,u) を状態として $\sum p X^{2}$ を管理しようとすると、レベルアップの処理が $\sum p X^{2} \to \sum p (X + 1)^{2} = \sum p X^{2} + 2 \sum p X + \sum p$ となる。よって $\sum p$ 、 $\sum p X$ 、 $\sum p X^{2}$ を管理しておけば更新も含めて計算できる。」これがヒントであって答えでないのは、これを読んでさえさっぱり遷移が書けなかったから。何度も何度もガチャガチャやって考えてガチャガチャやって考えてお風呂に入って考えた。提出 #36502350 (TLE×13)。書けなかったのは 29 行目と 30 行目と 32 行目。それで苦労の結果が TLE。計算してみたら N,M,K≦3000 で Ds.size=3 で E.sum(&:size)=2×M で C0.size+C1.size=N だからループの回数が K×(3×2×M+N) = 6300 万。Ruby は 1000 万回を超えたあたりから厳しくなってくるのでこのままでは無理だよ。

ツッコミを入れる

最近ひとつ現在へひとつ過去へ

ここをクリックしてカテゴリ一覧を表示