/ 最近 .rdf 追記設定本棚

脳log[2023-07-05～]

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

2023年07月05日 (水) 頼まれて家の Wi-Fi の事前共有鍵を入力したとき、「Amazon に保存する」という不穏なオプションのチェックマークはぬかりなく外したのだけど、その後にアマゾンから送られてきた別のデバイスが最初からネットワークへの接続方法を知っていた。不正アクセスでは？■「Wi-Fi設定のAmazonへの保存に関するよくある質問 - Amazonカスタマーサービス」便利ではなく選ばれにくく選んでもらいたいとも思われていないであろう選択が機能していない疑い。■「Amazonで買うとWi-Fi設定が不要に。スマートホーム規格「Matter」への取り組み - AV Watch」もちろんロッカーに鍵を預けてはいない。

ツッコミを入れる

2023年07月04日 (火) [AtCoder] 精進。ABC009-D「漸化式」(黄 diff)。ABC を古い方から埋めていく取り組みでつまずいてつまずいたままになっている最初の問題。ベルトコンベア式に入力を出力へ変換していく装置がある。10^9 回の処理を繰り返すわけにはいかないのでどうやってプロセスを加速するか。どこかのツイートで行列累乗だと読んだんだよね。たしかに、それ以外にない見た目をしている(しかし気がつかない)。その人は FPS で解くシリーズをやっていたらしいけど。■提出 #43246893 (AC / 351 Byte / 1730 ms)。２回連続で行列の掛け算が書けなかったのがつい２週間前のこと(20230619)なので、今日は３度目の正直。■Ruby での提出一覧を見ると３桁 ms の提出がいくつもある。K^3logM を K^2logM にする Kitamasa 法というものがあるらしい。高速 Kitamasa 法というのは聞いたことがある気がするなあ。

ツッコミを入れる

2023年07月01日 (土) [AtCoder] 今日は CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)があった。コンテスト成績証。今日は F 問題までこれというところのない、つまりは典型的な問題ばかりだった。G 問題は TLE 解しか書けなかった。コンテストの途中から終了後しばらくの現在まで AtCoder にアクセスすると必ず 403 Forbidden が返ってきて、即座にリロードすると正常に表示されるという状態が続いている。とても面倒。以下 A-F のふりかえり。■A 問題「New Scheme」。PAST のはじめの方にでも出てきそうな問題。書かれていることを愚直に実装する。■B 問題「Default Price」。これも愚直に実装する。まだ効率を考えなければいけないような制約ではない。これに５分の時間をかけてしまった理由は入力の受け取りに失敗していたことに気がつくまでの時間。だって AtCoder で色っていったら数字で与えられるのが常なんだもん。■C 問題「Standings」。たぶん分数を浮動小数点数で扱っても AC になるのかなあ、C 問題だし(追記：ツイッターを眺めてるとダメっぽい)。一応 sort メソッドに比較関数を渡して通分してから分子を比較するようにした。浮動小数点数って特殊で使用場所を選ぶものっていう認識で、整数で間に合うところで使うものではないと思ってる。なお JavaScript……。■D 問題「Snuke Maze」。素直にグリッドを探索する。同じマスを二度処理しないようにするなら BFS でも DFS でもいいだろう。再帰関数を使わないで書くなら違いはキューから shift で出すか pop で出すかの違いしかない。■E 問題「MEX」。いいかげん MEX という概念を認知するくらいには MEX を問題で見る機会が増えてきたけど、やっぱり「いずれとも一致しない最小の非負整数」みたいに否定で定義されるのは脳に負荷がかかる。この解法を DP と呼ぶのかな。M の字が出現した状態はその値が 0,1,2 である場合の３通りがある。ME の２字が出現した状態は(0,1,2)×(0,1,2)の９通りが考えられるけど、MEX への影響という観点では M(0)E(1) と M(1)E(0) を区別する意味がない。３桁のビットフラグで８通り持てば十分(ただし、0b000 と 0b111 は０通りに決まってるので意味があるのは６要素)。ところでこの問題の典型要素に「３つのうち真ん中に注目する」があったらしいが気がつかなかった。そういえば ARC160-B「Triple Pair」もそうだったけど真ん中を固定できなかったな>20230514。次からは典型として注目できるといい。■F 問題「Voucher」。ソートすれば貪欲に無駄なくクーポンが利用できそう。何をソートしようか。必ずこうでなければいけないという必然の選択はなんだろう。高額商品は使えるクーポンの幅が広いので低額商品から優先的にクーポンを割り当てたい。あるいは最低価格の設定が高いクーポンは利用機会が限られるのでできるだけ優先的に使用したい。でもクーポンが余るような時に最低価格設定が高いからといって値引きの渋いクーポンを使いたくはない。どうしましょ。低額商品から順番にクーポンを割り当てる。プライオリティキューで使えるクーポンを管理しておいて値引き額が最高のクーポンから順に使用していく。一度使用可能になったクーポンはその後ずっと使用可能だからできる。kotatsugame さんの動画を見ていて言及されていたので思い出したけど、クーポンの値引き額が商品価格を超えないことを制約で確認している。もし値引き額が商品価格によってキャップされてしまうなら常に最大の値引きクーポンを利用するのが最適ではなくなってくるので。もしそんなことがあれば DP でもしてすべての可能性を考えないと答えが出せないと思う。■G 問題「Minimum Xor Pair Query」。解けてないよ。黒板に書かれている数字をプリフィックスで分類しておきたいなと思った。数字は 30 ビット幅の範囲なんだけど、たとえば 29 ビット分のプリフィックスが共通する数字が２つ以上あったら、30 ビット分のプリフィックスが共通するものがないとしたら、答えは１に決まっている。できるだけ長い共通プリフィックスを見つけることが答えを出す最初の一歩だと思った。たぶん TLE なのは次の一歩が愚直組み合わせだからなのだろう。見つかった共通プリフィックスが短いほど組み合わせがやばい。プリフィックスを取り除いて MSB を無視して再帰的にプリフィックスで分類していくのだろうか。難しい、っていうかややこしいよ。プログラムの概形が見えない。今の TLE 提出の段階でもややこしくて配列に逃げたんだけど、配列の非効率的な操作が TLE の(唯一の)原因だったら嬉しいなあ。３要素以上の組み合わせを考えることってなくない？３要素あるならより長い共通プリフィックスが見つかると思う。じゃあ最長の共通プリフィックスを効率良く見つけるのに失敗してるな。最長の共通プリフィックスを見つける算段は立ったと思うけど、それが b ビットの長さだとすると最大で 2^b 組の XOR から最小値を見つけるのはどうすれば？ SortedMultiSet があれば考えることもないけど(ないんだな)。■■■G 問題。間接的に解説を読みました。「整数集合から2つ選んだXORの最小は整列させた隣り合う数のXORのどれか」うん、そうだね。できるだけ長い共通プリフィックスを持つ２数は隣り合う数字だね。バイナリ表現と数としての評価が繋がらなかったんだよ。あと条件を緩和する発想もなかなか出て来にくいと思う。隣接する２数の中には最長の共通プリフィックスを持つものもあるけど、そうでないものも当然ある。だけど区別する必要がないし、区別しない方が処理しやすい。■■■G 問題結果報告。■１.平衡二分探索木がない言語の頼れる味方 BIT を使ったもの>提出 #43153261 (TLE×23)。XOR した値が 30 ビット整数の範囲でどういう値をとるかわからないから BIT の実装に Hash を使っている。これはお時間やばめ。■２.XOR した値に対しては Hash 実装の BIT のままだけどクエリ先読みができる x については Array 実装の BIT を使った。あと必ず効果があるものではないけどクエリ１と２の処理をクエリ３が来るまで遅延させて同一の x に対する処理がまとまるようにした。提出 #43229129 (TLE×14)。■３.XOR した値に関して Hash BIT の代わりに削除可能なプライオリティキューを使うようにした。提出 #43229096 (AC / 2342 ms)。削除可能なヒープの実装が『アルゴリズムとデータ構造』(メールホルン, サンダース)の課題にあったと思うんだけどどう実装するのか知らなかった。だけどこの前比較可能なキーだけを突っ込めるプライオリティキューにひと皮かぶせてキーに値を関連付ける方法を hmmnrst さんの提出 #42277952 で知ったので、キーに個数を関連付けて削除とするのは簡単だった。ヒープへの出し入れは定数倍が重いので節約術(２個目以降の同一キーはヒープに入れない)としても個数の管理を役立てていきたいと思う。もうひとつ。初めて見る prepend メソッドの使用例でもあった。これは継承を操作するメソッドで、自分が持つ言葉のイメージとは裏腹に prepend されたモジュールは継承階層の末端側に配置される。反対のメソッドは append ではなくて include らしい。そちらはよく知っているが目から鱗の発見でもあった。include↔prepend なのか。prepend は Ruby が 1.9 の頃にはなくて 2.3 の時にはもうあったメソッドらしい。ところで自分の提出では prepend も継承も使っていない。オーバーライドされた親クラスのメソッドを呼び出す方法が見つからなかったからだ。具体的には PQ2#head メソッドの中で、オーバーライドしている PQ2#deq メソッドではなく PQ#deq メソッドを呼び出したかった。同名のメソッドなら super で呼び出せるけど。C++ には明示する文法があるんだけど。図らずも「(可能ならいつでも)継承よりコンポジション」を別の理由から確認する結果になった。たぶん Ruby での方法は alias だけど、あまりにも姑息なやり方だと思う。■４.これは解説を読む前に作っていた「最長の共通プリフィックスを見つける算段は立ったと思うけど、それが b ビットの長さだとすると最大で 2^b 組の XOR から最小値を見つけるのはどうすれば？ SortedMultiSet があれば考えることもないけど(ないんだな)。」と書いていた頃のもの。2^b 組について愚直に全件調べているが意外に健闘した>提出 #43229224 (TLE×14)。

ツッコミを入れる

2023年06月30日 (金) [AtCoder] 精進。ABC146-E「Rem of Sum is Num」(青 diff)。累積和(要素1、要素1+2、要素1+2+3、……)を K で割った余りを数えておく。このとき添字を使って補正することで、要素数１の部分列がとるべき値、要素数２の部分列がとるべき値……が同一の値になるので、ある要素を始点とする部分列のうち条件を満たすものが定数時間で数えられるようになる。注意を要するのは、要素数が K 以上の部分列が条件を満たすことはないので、うっかり K 個以上の累積和を集計してはいけない。■提出 #43073937 (AC / 352 Byte / 224 ms)。全然サンプルが合わなくて、あっちを修正しこっちを修正し、一休みして考え違いを修正して、やっとすべてがあるべき形に納まったときにサンプルが合った。実装ミスが２つ以上あって根本的な考え違いまであったのでは数合わせはほぼ不可能。つらかった。

ツッコミを入れる

2023年06月29日 (木) 馬主。アニメ【推しの子】８話でバヌシと発音されていた。自分もそう読んでいたけど少し前にウマヌシと発音し直される機会があって、音読み訓読みを揃えるならバヌシは異端だったかもしれないなと納得していた。バヌシと読むのが自分だけではないと知って辞書を引いてみたらウマヌシとバヌシに加えてバシュまで載っていた。ただ、微妙な違いもあるらしく、明鏡国語辞典ではバシュとバヌシは相互参照の関係にあるがウマヌシはそうではない。バシュ、バヌシには「馬の持ち主」という意味しかないがウマヌシには２つの意味があって、１番目が「馬の持ち主」でありバシュ、バヌシへの参照がある。２番目がウマヌシ固有の意味で「競走馬の持ち主」とある。広辞苑にもこれら３つの見出しがあるが、やや混乱が見られる。ウマヌシからバシュ、バヌシへの参照があり、バシュ、バヌシが相互参照の関係にあるのは同じだが、バヌシからウマヌシへの参照があるところが異なっている。ウマヌシはバヌシを包含するらしいからバヌシ⇒ウマヌシは(明鏡と異なっていても)不自然ではない。バシュからウマヌシへの参照がないのが不自然。意味はウマヌシが「馬の持主。競走馬の持主」、バシュとバヌシが「（競馬で）馬の持主」とある。「（競馬で）」はまったく余計だと思う。そのせいでウマヌシとの区別が曖昧になるし、競馬ではない馬の持ち主を指す別の言葉があるとも思われないので。あ、普通に持ち主とか飼い主か。

ツッコミを入れる

2023年06月27日 (火) [AtCoder] 精進。ARC060-E「高橋君とホテル」(黄 diff)。ダブリングだという予備知識ありで取り組んだ。「サーバル「ARC060E『高橋君とホテル』がよく似た問題だから考えてみて！」 https://t.co/3rxVISM6ZZ」。提出 #43010235 (AC / 346 Byte / 824 ms)。うん、ただのダブリングだった。移動に向きはないし、進めるだけ進むだけだし。D 関数で reverse_each を忘れてバグらせたのは内緒。出てくる答えがやけに２べきに揃うと思ったんだ。

ツッコミを入れる

2023年06月24日 (土) [AtCoder] 今日は東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 307）があった。コンテスト成績証。C 問題が大変厳しかった。diff を見ても D、E に勝る水 diff になっている。C を飛ばしてさっさと D、E を解いた人も多かったみたい(終了後に提出一覧を見て知った)。以下 B-E の振り返りと F の精進について。■B 問題「racecar」。異なる文字列を組み合わせて回文が作れるかを判定する問題。permutation(2) を使うべきところで combination(2) を使って WA を出した。たぶん「Si と Sj をこの順に連結した文字列が回文となるようなものが存在するか判定してください。」という問題文の「Si と Sj をこの順に連結」という文面から勝手に i<j であるかのような雰囲気を感じ取って勘違いしたのだろう。提出 #42900133 (AC)■C 問題「Ideal Sheet」。制約は大きくないから愚直に実装するだけ。その実装がたいへんだった。ビット列でやるとちょっとは楽になるんだけど、本当にちょっとだけ。これもペナルティをくらった。最初は動かせる範囲を総当たりする４重ループを書いていたのだけど、たとえばシート A がシート X の１行目をカバーしないとき、シート B は必ずシート X の１行目をカバーしないといけない。ということはカバーする範囲を１ずつ動かす総当たりではなく、シート X の四隅をカバーする総当たりでいいのではないかというケチな考えが忍び込んできた。これの罠はシート A と B の一方がシート X を完全にカバーするときで、そこまで想定していながら問題があると気付かずに提出して WA を出してしまった。原因に心当たりがあったのですぐに修正できたのが救い。AC まで 36 分(+ペナ５分)。■D 問題「Mismatched Parentheses」。対の括弧に囲まれた部分を省いて出力すればいい。括弧の中の文字列をスタックで管理するとして、括弧の外の文字列を特別扱いしなければいけない。同じようにスタックで扱えるかと考えてみたけどどうも良くなさそう。AC まで６分半。■E 問題「Distinct Adjacent」。前回の ABC306-D ほどあからさまではないけどこれも２値を記録する DP。人１が選んだ数字とそれ以外の数字をそれぞれ選ぶ場合の数を記録していく。人 N の時点で人１が選ばなかった数字を選ぶ場合の数が答え。AC まで９分。■ところで、E 問題に関して Ruby で一番最初の提出であり AC であるこちらの提出 #42909715 には(目に見える)ループがない。N が数えられないくらい大きな数だった場合は自分の DP 解ではダメでこちらをまねしなければいけない。よく見ると mod(=998244353) の他に mod-1(=998244352) が計算に使われている。mod-1 乗ならともかく mod-1 の累乗にどんな使い道があるのか自分は知らない。■F 問題「Virus 2」(黄 diff) は時間内に解けなかったので精進。長めの時間制限４秒が不安をあおる。ダイクストラ法で感染者からの距離を管理して新規感染者を見つけていきたい。どんな下手を打つと TLE になるだろうか。新規感染者が発生した部屋は次の日には感染者からの距離が０になるわけで、最短距離の更新が広範囲に何度も起こる場合に TLE になりそう。できるだけキューを膨らませないようにケチりはしたけど特別なことはせずに 2863 ms で AC になった。01BFS のように一日一日ステップを刻みながらダイクストラ法を進めるのが頭の中がこんがらかって難しかった。つまり、ダイクストラ法を基本にしつつ日を刻み、１日を２つのステップに分けるのだけど、各ステップでやるべきことすべきでないことを見極めるのが難しかった。無駄を許すと TLE になりそうだったのもあるし、迂闊なことをすると２つのステップが連携できなくて機能しなくなるので。■■■C 問題。ケチな考えを追い出して多少の無駄があっても見通しがいいことを第一に書き直してみた>提出 #42960011 (AC / 515 Byte / 78 ms)。515 バイトはタイプするのに長すぎるということはないね。■■■E 問題の mod-1 について。「グラフ彩色 (ja.wikipedia.org)」のページに `(M-1)^N+(M-1)(-1)^N` という式が書いてある。mod-1 は単にマイナス１のことだった(それはそう)。

ツッコミを入れる

2023年06月22日 (木) 今日初めて気がついたこと。キウンには２つの漢字があってそれぞれ意味が違う。機運(ちょうどいいタイミング)。気運(時勢のなりゆき)。実は３つ目もあった。黄檗希運(あるお坊さん)。以前の精通と同じで、別々には知っていても並べる機会がなかったので。

ツッコミを入れる

2023年06月21日 (水) 気になってるゲームに体験版があったからプレイしてみたら UI がとても目障りでつらい。何か。リストを表示したときフォーカスアイテムの直下にツールチップを出すから実質的にリストの行数が１行しかない。一行一行に注目しながら装備品を選んだり戦闘中の行動を選んだりしないといけない。つねに視界の８割を目隠しされているような不自由なプレイ体験。なぜこうなってしまうのか。リストから選ぶとき、まずは全体の輪郭(各行の長さ)や黒さ(文字の画数)や何個あるうちの何番目かといった属性であたりをつけるでしょう？(そうじゃないんだろうなあ) 何も見えない。何もというか、下を押して選んでみるまで下にある次の項目が見えない。なぜなのか。■四角ボタンで消せた！でもこれ正解はオンオフではなくて固定領域に詳細を表示することなんだよね。

ツッコミを入れる

2023年06月20日 (火) [AtCoder] 先週の ARC162-C「Mex Game on Tree」(ぎりぎり青 diff)。当日は 40 分くらい時間が残っていたけど解けなかった。MEX が K 未満でも K より大きくてもダメなんだよなー、部分木での攻防がより大きな部分木での勝敗に影響したりするかなーとか考えていた。■提出 #42772931 (AC / 345 Byte / 196 ms)。ネタバレをね、読みました。「CはAliceが高々1手操作して勝てないならBobが勝つ。Aliceが操作した場所に応じてBobが適切な頂点にKを置くと、せっかく操作した分が台無しになって、1手操作しても勝てない状態が延々続くからだ。」これがすべて「Bob が…… K を置くと」。でもそれが見えなかったのだし、実装も 13 行目の `k-sk<=v` を最初は `k-sk==v` と間違えていたので何も言えない。難しい問題だった。

ツッコミを入れる

2023年06月19日 (月) [AtCoder] 精進。ABC236-G「Good Vertices」(ぎりぎり橙 diff。この色は前２問の EF ががっつり青 diff だった影響が大いにあると思う)。５日前(20230614)に解いた問題の類題だとのツイートを読んだ>「サーバル「実は「行列の掛け算っぽい計算」さえできれば行列累乗できるから、数え上げ以外の問題でも行列累乗を使うことはあるけど、こっちはかなり難しいね。ABC236Gが例題だよ」 https://t.co/8OvqVZpuLz」。100×100 の行列を 10^9 乗するので３千万の計算量。これを辺を１本１本追加しながら N^2(≦１万)回繰り返すともちろん TLE になる。どうしよう(※)。今回は場合の数を数えるのが目的ではないから、行列の中身に使用した辺が追加された時刻 t の最大値を記録すればいいと思った。(※「どうしよう」この一語にはコンテストが終了してしまうくらいの時間が詰まっている。ときどき思い出しては頭の中で転がしていた)■提出 #42752849 (TLE×52/AC×58)。今回も行列の掛け算を書き間違えたのでこの前の提出を見ながらまねして書いた。そして TLE。ローカルではほぼ９秒以内に完了しているので、ジャッジサーバーでは約半分の 4.5 秒かかる見込み。制限時間は特に長めではない２秒。Ruby でうん千万のオーダーは厳しいよう。■提出 #42753403 (AC / 1995 ms)。`.zip().filter_map{}.min` を `.zip(){}` での逐次処理に書き換えたらローカルで５秒になったので提出したら AC だった。案外いけるもんだ。

ツッコミを入れる

2023年06月17日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2023#3(AtCoder Beginner Contest 306)があったけどジャッジが詰まりまくっていて Unrated になった。「このコンテストは full-feedback 形式のコンテストです」が嘘だったからかな。終了後 20 分経つ現在でも時間内に提出した F 問題が WJ のまま止まっていて生殺しの状態なのだ。今日は既視感のある問題ばかりで 36 分で E 問題まで通ったのだけど、そこから１時間ちかく誤読した F 問題を考え続けていた。■F 問題「Merge Sets」。方針はすぐに立った(この方針が正しいかどうかはまだ不明)。集合を全部まぜまぜしてソートして、ある要素の後ろに何個の要素があるかを二分探索で調べる。つまり、ある要素が他のいくつの要素の添字を押し上げる効果を持っているかを計る方針。ところでね、f(A,B) の計算において A と B は可換ではない。そして求める総和というのは i<j であるすべての f(Si,Sj)。だけどずーーーーっと i<j を区別しない f(Si,Sj) について考えていた。最後に割る２すればいいんじゃないのって考えていた。■制約について１つ気になって確認したことがある。A∩B が空集合だとは書いてあるけど、つまり A と B に共通する要素がないとは書いてあるけど、A の中、B の中に限ったときに共通する要素がないとは書いていなかったと思う(※)。だから添字を使って同値の要素に便宜的に大小関係を導入したんだけど、誤読が明らかになったときにソート列の二分探索から BIT を使う解法に変わったのでそんな面倒な手順は必要なくなっていた。提出 #42363020 (AC) に残ってるのは虫垂みたいなもの。この日記を書いてるうちに AC の結果が出ていた。もう終了から 40 分経ってるよ。ちなみに誤読なしでストレートに実装するとこれだけシンプルになる>提出 #42370906 (AC)。■コンテスト成績証。へなちょこに Unrated を嘆いたりやる気を削がれたりしている暇はないのだ。順位表の１ページ目にいる人たちなんて最初から Unrated なんだから。各色相当の実力があればなるべくしてその色になる。Unrated ばかりならその機会がないけど現状はそこまでひどくない。がっかりするのは上振れに期待しているから。毎回青パフォ以上を出せばいいだけ。建前はそう。でもそれができないのだから、調子がいいときに Unrated なのはつらい。■※「A と B に共通する要素がないとは書いてあるけど、A の中、B の中に限ったときに共通する要素がないとは書いていなかったと思う」やっぱり書いてあったのかなあ。部分文字列の定義は連続するかどうか曖昧だけど、集合の定義は多重かどうか曖昧ではなかったりする？反則的だとは思うけど「A={Ck1,Ck2,…,Ck∣A∣} となるような k1,k2,…,k∣A∣ をとる」ことが曖昧でなくできることから逆説的に重複する要素がないと判断できる？ ……あった！「i1!=i2 または j1!=j2 ならば Ai1,j1!=Ai2,j2」って書いてある！とことん読み違える問題だったなあ。

ツッコミを入れる

2023年06月14日 (水) [AtCoder] 精進。先週の ABC305-G「Banned Substrings」(青 diff)。終了後に４か所で行列累乗というキーワードを見ていた。でも難しい。何×何の行列を用意するのか。その中身は。■提出 #42254964 (AC / 639 Byte / 1622 ms)。まずダメ文字列を表すビット列を１文字から６文字まで DP みたいにして用意した。N が６以下ならこの時点で答えが出せる。次に６文字のダメ文字列を元にして１文字延長を表す 64×64 の行列を作った。ここまでは一歩一歩手探りしながら順調に来たけれど、サンプルの答えが全然合わなくて袋小路に入り込んでしまった。どの部分か。主として 28 行目と 29 行目にあたる部分を延々書き換えながら、なんで掛け算を繰り返すとダメ文字列が答えに現れてくるのか理解に苦しんでいた。私は、行列の掛け算を正しく書くことができません。そこは考えるとことちゃうやん？ただ定義通りに書くだけよ。■計算量。行列の掛け算は３乗なのかな。64^3≒26万。それに累乗部分が logN≒60。行列の列あたりの非ゼロの数が０か２個なので、ゼロだけの行と列がそれなりにありそうだし、疎らなのをいかした効率化もありそう。でも定数倍の改善なら競プロでは評価されないね。■対角化と Jordan 標準形のキーワードを得た！名前だけでもうおなかいっぱいです。ネタもとは『プログラミングのための線形代数』なんだけど、今まさに読んでいる「【第5回】「型」はウェブシステム開発に「エンドゲーム」をもたらすか | GeeklyMedia(ギークリーメディア)」にタイトルが出てきてびっくりしたよ。■最大ケースが `1000000000000000000 0` なのかな。64×64 のうちダメ文字列に対応する行と列を省いたとしても M=0 のケースでは良くならない。それよりも行列のサイズを 32×32 に抑える方が良くなるだろう。32×32 で十分みたいなんだけどわかんない>#42246448。■提出 #42262239 (AC / 769 Byte / 257 ms)。32×32 で足りるというのでとりあえず 32×32 を基本にしてみてダメ文字列の行と列を省いたりもしてみたら１桁早くなった。なんで 64×64 だったり 32×32 だったり行列のサイズがまちまちになるんだろう。１文字分の冗長さはどこから生じてて、なんでお構いなしで答えが合うんだろう。参照する必要のない６文字前を使って入出力を無駄に細かく分類してもそれが理由で間違えるわけではない。なんなら７文字前８文字前まで利用してさらに細分化しても手間が増えるだけで答えが違ってくるわけではない。ということ？

ツッコミを入れる

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

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