/ 最近 .rdf 追記設定本棚

脳log[2022-04]

前月へ 2022-04 翌月へ

2022年04月01日 (金) [AtCoder] 精進。ABC100-D「Patisserie ABC」(水 diff)。一晩寝かせたら解けた(寝る前には解けなかった)。最初は８通り３ステップの解法を考えていた。つまり、３つある軸ごとに正の方向に最大化するか負の方向に最大化するかの組み合わせが８通り。３軸を順番に最大化するのに３ステップ。これだと３分の１くらいのケースで間違える。最大化するより他の軸とのあいだでうまく折り合いを付けた方が総合的に得する場合が漏れたのだろう。前後のステップを通して２軸のバランスはとれていたはずだけど、３軸の総合バランスが考慮できない。■提出 #30611715 (AC / 229 Byte / 68 ms)。３軸をまとめて８通り１ステップの解法で AC。肝心の５行目がちょっと冗長。`x.zip(y,z).map(&:sum).max(M).sum` でいい。

ツッコミを入れる

2022年04月02日 (土) Excel 2007 日記 (前回>20220324)。テーブルと名前付き範囲の関係。テーブルとオートコレクトの関係。「Excelでテーブルに数式をセットする際の注意点 | ∞ワークス」ならばテーブルとは？■テーブルの列にサブクエリの結果を付け加えたい。たとえばキーと日付のペアが記録されているテーブルがあったとして、キーを追加したときにキーに対応する前回の日付を表示する第３の列を用意したい。このテーブルは待ち行列なのであって、適切なインターバルを空けるために前回の日付を参照してフィルタリングするために、同じテーブルを参照する再帰的なサブクエリを発行して列を付け加えたい。VLOOKUP では最初に見つかった行の値になる。DMAX では CRITERIA 引数部分に構造化参照が使えると書いていない。集計表としてピボットテーブルを作成しておいて VLOOKUP でピックアップしようとした。「ピボットテーブルとVLOOKUP関数を組み合わせて使う【Excelの応用】 | Howpon[ハウポン]」ピボットテーブル名ってテーブル名と互換性があるような見た目をしてるけど管理された名前付き範囲ではないのね。シート名とセルの絶対参照を検索範囲にして VLOOKUP しないといけない。実は日付だけでなく文字列フィールドも集計の対象のひとつなのであって何か書いてあれば駄目フラグとして扱うつもりなのだけど、ピボットテーブルの集計関数(最大値)は最初に数値化してしまうらしく文字列ではなく 0 が集計されるのだった。ピボットテーブルは名前の扱いも集計関数も不都合なので結局 Microsoft Query を通して集計表を作成しておくことにした。SQL を直接編集すれば GROUP BY も MAX 関数も使えるし、文字列フィールドの最大値はきちんと文字列が返ってきた。この SQL はデータソースが解釈、実行するらしいのだけど、ソースが TSV ファイルや Excel ブックの場合は Microsoft {Text|Excel} Driver が実行しているのかどうか。フォーマットに関する情報しかない。「Text File Format (Text File Driver) - Open Database Connectivity (ODBC) | Microsoft Docs」■どんどん深みにはまっている感覚がある。何がいけないって、まずフォントや色や文字の配置といった時間が余ったときの仕上げ行程にふさわしい操作がありとあらゆる機会に目に入り目当ての操作を隠し答えのない脇道へと誘惑する。次に自由度の高さ。制約が乏しくありとあらゆる部分でアドホックに手を入れてデータや構造を壊せてしまう。そんな方眼紙や自由帳のような自由はいらない。■複合グラフ。新しいバージョンでのような導線がないだけであって Excel 2007 でも作れる。「Excel 2007 / 2010 / 2013 / 2016 で複合グラフを作る｜クリエアナブキのちょこテク」データ系列の書式設定を自力で見つけることはできなかったよ。■GetPivotData 関数の存在に気がついた(オプション項目で目にしていたけど関数名だと思わなかった)。列番号ではなく列の名前と値を使って目当てのセルを特定できるのが特長なのかな。セルを特定するのに行と列の２次元とは限らないところが難しい。基本的には総計が返る。フィールド名と値のペアを引数に追加するごとにより限定された小計が返る、という感じ。要するにこうだ。最初に集計項目を選び、追加のパラメータでいくつか属性を絞り、積集合部分の集計値が返る。このクエリに高速に答えられるのがいわゆる Wavelet ～というデータ構造なのだろうか。クエリごとにインデックスを用意するならデータベースでおなじみだという BTree でいいんだろうけど、Excel はクエリがプログラマブルだから予め個々のインデックスを用意しておけないと思う。専用の関数だけど名前で対象のピボットテーブルが特定できるわけではないらしくやっぱり番地で参照しないといけない。しかし目当ての集計値を特定するのには番地を必要とせずピボットテーブルの表示状態に左右されないところが GetPivotData が必要とされた理由なのかな。■INDIRECT 関数がおもしろそう(どんな悪さができるかという意味で)。eval です。■複数のセルの値を条件にして VLOOKUP する方法。検索していくつか見つかったページはどれもセルの内容を連結した検索用の列を追加する方法だった。予想はしてた。■複数セルに一括入力。選択、入力して Ctrl+Enter。■予めソートしておくから VLOOKUP に二分探索で完全一致検索をしてほしい。TRUE(lower_bound)/FALSE(線形探索) の二択では足りない。■Microsoft Query はテーブルを認識していない？オプションでテーブルとシステムテーブルの両方ともにチェックを入れるとシートやクエリの名前が出てくるけどテーブル名は含まれていない。あと外部プログラムだからブックを保存しないとクエリ結果が古いブックに基づいたものになってしまう。やっぱり新しい Excel で Power Query が使いたいんだよなあ。「LOOKUP の結果を表として扱いたい。俺が書きたいのは SQL の SELECT 文だ。特定のセルを左上の頂点とする複数行複数列の範囲に収まるように、クエリ結果を上書きまたは下に押し出し挿入または右に押し出し挿入したい」と書いていたものもスピル(覆水盆に返らずの Spill)がそれっぽいらしいし。■最初は VLOOKUP が良さそうに見えてもいずれ必ず INDEX+MATCH に置き換えられる運命。検索キーより右側にある列の値しか拾えないとか、降順のデータから効率良く検索できないとかの、VLOOKUP の制約が表データと適合しなくなったらそうする他ない。

ツッコミを入れる

2022年04月13日 (水) クイズクイズ「競技プログラミング用語の略さないやつ | クイズメーカー - こたえてあそぶ・つくってあそぶ・クイズのプラットフォームサービス」。■結果。「競技プログラミング用語の略さないやつ 10問中 7問正解しました！【 ①○ ②✕ ③○ ④✕ ⑤○ ⑥○ ⑦○ ⑧○ ⑨○ ⑩✕ 】」■間違えたの。「LCM」Multiplier だと思ってた。言われれば掛けるものではなく掛けた結果ではある。Multiple(倍数)だって。「BFS」パンのような息のような読めない奴としか覚えていない。ちなみに Width もワイズのようなウィズのような読めない奴という認識にとどまっている。「LCA」Least だと思ったら Lowest だった。日本語だと最小～が多くて最近～もあるかな、という雰囲気。日本語ファーストで(いかたこさんのところで)覚えた概念だから Lowest より Least を選んでしまった。実際のところ Lowest も Least も最小もしっくりこないせいでこれまで何度も L が何の略だったか頭を悩ませてきていて、LCA は LCA であるということでもう済ませてしまっている。他人と共有しないのなら概念は概念のままでラベルだって本当はいらない。でも思い出すきっかけとしてラベルが有用なことはある。LCS と区別するために Ancestor だけわかれば十分。余談。LCS の S は Sequence の S ではないのだ。■正解したの。GCD、DFS、DAG、DP、BIT、DSU、SCC。

ツッコミを入れる

2022年04月15日 (金) [AtCoder] 精進。全国統一プログラミング王決定戦予選-D「Restore the Tree」(水 diff)。子孫ノードへのショートカットが M 本追加された(元)木からショートカットを取り除く問題。ショートカット先が子孫ノードに限定されているのでそれほど複雑なグラフになるわけではない。たとえば根から始めて各ノードの深さを決めていくとする。ショートカットがあるので親が１つとは限らないわけで、異なる複数の深さが１つのノードに与えられそうになるけれど、常に最大の深さがそのノードの本来の深さで間違いない。深さを比べれば親がわかる。■しかし TLE。幅優先探索でも max-heap でも min-heap でも時間内に深さが決められない。■提出 #30984890 (AC / 267 ms) 一夜明けての AC。方針転換を決めてからは早かった。すべての親が到着するのを待ってから下方向への探索をキューに入れる。深さを決める問題が部分木ごとに独立した問題になるから問題ない。最後に到着した親が本当の親。うまく型にはまってくれない問題だった。解く側の印象はそうなんだけど、他の人の Ruby での解答をざっと見た印象では、自分のとやっていることがほぼ同じだった。親の数をデクリメントするあたりが特徴的。型にはまらないように見えて解答の型はがっちり決まっていた、ということ。

ツッコミを入れる

2022年04月18日 (月) 最近ちょいちょい耳にする戦争犯罪という言葉(概念)を自分は知らない。当たり前のように使われているけれど。戦争と付けることで、まあしゃあない部分もあるかもなと割り引いて考えればいいのか、言語道断絶対許すまじと処罰感情増し増しで受け止めればいいのか、そのどちらでもないのかよくわからないで聞いている。もうひとつ思いついたのは、犯罪行為を裁くのはウクライナかロシアか場所や人の当事国の役割だと思うけど、ロシアがロシア兵を裁くことに期待はできないから、戦争犯罪という扱いを既成事実化することで戦勝国が裁くんだぞという空気を醸成しているのかなと思うなどした。言葉と歴史を知らない。調べもしない。

ツッコミを入れる

2022年04月19日 (火) 今日の新発見。これまで同時に考えることがなかったので気がついていなかったけど、精通って２通りの意味がある！どうしよう使いにくい言葉になってしまったな。むりやり通暁しているとか言い替えても大げさすぎて自分で何事⁈って驚いちゃうもんな。

ツッコミを入れる

2022年04月27日 (水) [AtCoder] 精進。先週あったモノグサプログラミングコンテスト2022（AtCoder Beginner Contest 249）-F「Ignore Operations」(青 diff)。コンテスト当日は同じ青 diff だけど F より難しいことになっている E 問題「RLE」で詰まっていた。E 問題は制約上限が 3000 なんだけど愚直にやると N の３乗になって TLE が避けられない。最内ループの足し上げる部分をなんとかしたかったけどどうにもならなかった。N<300 くらいまでしか間に合わない。■さておき F 問題。まずどの t=1 を無視しないかを決める。そうするとそれより前にある操作は存在しないのと同じ。それより後にある t=1 はすべて無視しなければいけない。後にある t=2 のうち 0<=y のものは当然無視せず(K を消費せず)最大値に寄与させる。後にある t=2 のうち y<0 のものは小さいものから無視できるだけ無視する。問題はこれをどう効率良く処理するか。特に負の y の累積和。ソート済みの状態を保ちながら y を順次追加しつつ、その累積和を利用したい。■提出 #31310696 (AC / 1130 Byte / 520 ms)。BIT を２本使ってがんばる。■そうだ思い出した。E 問題で詰まっていたのは本当だけど、D 問題を諦めて飛ばした上で詰まっていたのだった(つまり３完)。D 問題の制約上限 20 万にびびって手がつけられなかったのだけど、解説を読めば「さて、実は……」とか書いてある。それがわかんねーんだよな。10 数個だけ解けずに残っている選ばれし緑 diff の１つ「Coprime」の仲間だと思った(それなら解けない)。

ツッコミを入れる

最新のものから順番に表示

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