/ 最近 .rdf 追記設定本棚

脳log[2022-05-09～]

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

2022年05月09日 (月) Bing も Google みたいにリダイレクタを検索結果として並べるようになった。そうするとすでに見たページかどうかがリンクの色で判別できなくなる。本当に余計なことをする。まあ、Unicode の幅 0 スペースで区切られた嘘の URL を HTML に埋め込み緑色の字で表示していたグーグルほどではない。そういうのってステータスコード 200 で Not Found ページを返すのと同じ神経だと思う。さすがにもうやってないと思うが。■ちょっと考えたら「そうすると～できなくなる」は繋がらない。そうではなく、不定なトラッキング ID だかハッシュ値のようなものをパラメータとして付加するからブラウザの履歴が機能しなくなる。本当に余計なことをする。

ツッコミを入れる

2022年05月08日 (日) [AtCoder] 今日は ABC250 があった。自分の提出一覧。それぞれの問題にかかった時間が、A=３分強、B=10分、C=６分強、D=５分、E=17分、F=49分。B 問題難しすぎ。■E 問題「Prefix Equality」が面白かった。こういう手触りの問題好き。特別な道具や知識を必要としないところ(あと解法が２つ３つはあるらしいのもポイント高い)。最近の精進では 20211112 で解いた「Connected?」が似た感じ。集合の同一性を考えるのに、集合のサイズをキーにした。考えるべき集合は必ず先頭から始まる X 項から重複を除いたものになるので、X が増えるにしたがって集合のサイズも増える一方。集合のサイズごとに、２つの集合が一致するかしないかが決まる。それを予め調べておけば、クエリに対して２つの集合のサイズがそれぞれいくつになるかを調べ、サイズが一致していればそのサイズの集合が同一かどうかはすでに調べてあるので答えが出せる。制限時間が４秒だったけど 568 ms で十分だった。■F 問題「One Fourth」は典型90問で似たのをやった。「009 - Three Point Angle（★6）」かな。それとも他にもっと似た問題があったかも。やることは尺取り(もしくは累積和を二分探索)なんだけど、図形がからむと diff が高くなりがち(ギリギリ黄 diff だったもよう。もちろんほとんど青という意味でギリギリ)。図形要素はコンテスト中に検索したよ「多角形の面積」。

ツッコミを入れる

2022年05月06日 (金) [AtCoder] 精進。AGC035-A「XOR Circle」(茶 diff)。成立する条件はすごく限られていて、でも 0 が絡むとちょっとだけ事情が異なっていて、それを６分岐で。提出 #31475254 (AC / 268 Byte)。Ruby で一番最初の提出を見てみたらこれ>提出 #6371698 (haccht さん / 82 Byte)。えっ天才では？■……と思ったけど `A = 1,1,1,1` のとき答えが食い違う。えっテストケースざるでは？ Yes であるための必要条件ではあるけど十分条件ではないのだな。

ツッコミを入れる

2022年05月04日 (水) [AtCoder] 精進。灘校文化祭コンテスト 2022 Day1-D,F。有志コンに不用意に手を出して思い知らされるのは、AtCoder の ABC がいかに初心者向けに手心を加えてくれているか、ということ。難しくて解けないんだよ。■さて４問目。D 問題「Double Permutations」(400点)。ループする数直線上に N 個の点があって、点 0 からスタートする。1 から N-1 の歩幅を１回ずつ使って数直線上の N 点すべてに止まりたい。向きは変えられない。なにか雲を掴むような話。しらみつぶしに調べたいけど制約上限が 20 万で許されない。おおよそ線形時間で解きたい。一日放置していたら、ペアを作ってみようと考えた。雲は掴めないから共通の性質を与えて共通の取り扱いをする手掛かりとしたい。0 と N-1、1 と N-2 という感じで和が N-1 のペアが一番多く作れる。ペア１つにつき１周に１足りないからスタート地点の１つ手前に戻ってくる。これを繰り返すとどうなるか。N が偶数の時はうまく行きそう。N<10 の範囲で全探索したけど、N=1 を除いて N が奇数の時は解がない。提出 #31433409 (AC / 132 Byte / 127 ms)。なんでうまくいくのかはわからない。■F 問題「Mth Next Permutation」(６問目・500点)。Pi=1 と Pj=K を含む巡回グループの周期を考える。グループのメンバーを選び、並べ替え、グループ外の数列を並べ替え、掛け合わせる。提出 #31434643 (AC / 521 Byte / 202 ms)。K=1 の場合を特別扱いしたけど、うまく一緒に考えられるのだろうか。■全部で 16 問あるんだけど、解ける方が少ない。■■■精進２。灘校文化祭コンテスト 2022 Day2-A,B■A 問題「ACPN」(300 点)。実験したら M 個の剰余が出現する周期は K と M の最大公約数で分割されるようだった。たとえば M が 10 なら剰余は 10 種類あるが、K が 5 のとき最大公約数は 5 で、M 個の値は周期 2 の組が 5 組となって出現する。あとはこの周期で N が割り切れるかどうか。提出 #31438777 (AC / 70 Byte / 59 ms) 中国剰余定理はわからない。でもそろそろわかるかもしれない。■B 問題「Min Max Min」(400 点)。２日目は全体的に配点が１日目より高め、とはいえ２問目はまだ 400 点、なのにもう難しい。A と B の要素数の上限がどちらも 20 万だから、A と B の組み合わせを考えることがもう許されていない。どうするの？提出 #31440194 (AC / 386 Byte / 250 ms)。お風呂で考えた。数列を順番に見ていって、現在の要素を範囲の右端とする。この要素が最大値(最小値)として通用する範囲がどこまでかを調べる。最大値の範囲と最小値の範囲は食い違うわけだけど、広い方の範囲を採用する。その範囲で最大値の最大値最小値と最小値の最大値最小値の組み合わせ(２×２＝４通り。実際にはどちらかが１つの値しかとらないので２通り)の積が答えの候補。２問目でこれはなしだよ。３問目を読む気力がもうない。■B 問題の謎解答。提出 #31445298 (kotatsugame さん / 72 Byte / 167 ms)。短いだけでなく速い。なんで答えの候補を `A.maxB.min` と `A.zip(B).map{|a,b| ab }` に限定していいのかわからない。この一連のツイートが Day2 の B 問題についてのものだろうか。「@kotatsugame_t これならひっかかってませんか？ https://t.co/CFIYrhdR68」「～のときは、区間は短いほど得なので、長さ１の区間のみで十分です。」ああなるほどって思えないからこれが関連ツイートなのかどうかわからないんだよね。

ツッコミを入れる

2022年05月02日 (月) 「本人よりも詐欺師の方が高い「秘密の質問」の正解率 | スラドセキュリティ」■前にも書いたけど、腐す前に区別しような。「秘密の質問とかなぞなぞ認証には２種類あることを知っているだろうか。愚かなのは(推測しやすい)第二第三のパスワードとして(必ず)設定させるもの。そうとばかりは言えないのは、たとえばいつもの端末とは違うところからパスワードを使ってログインしてきたときに、あなたは本当に本人ですかと念の為に尋ねるためのもの。罵る前に区別できてますか？それとも、どっちも同じようにダメ？」

ツッコミを入れる

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」の仲間だと思った(それなら解けない)。

ツッコミを入れる

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

ツッコミを入れる

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

ツッコミを入れる

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

ツッコミを入れる

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

ツッコミを入れる

2022年03月29日 (火) [AtCoder] 精進。前回の ABC245-G「Foreign Friends」(黄 diff)。AtCoder Live の解説放送を初めて見たんです。「多始点ダイクストラ法でやる」「同じグループの場合を除外する」「トップ２を記録する」まで教えてもらうと解けそうな気がしました。要素技術は持っていたのに道が入り組んでいてゴールが見通せなかった感じ。たとえばトップ２を記録する戦略は「Bracket Sequencing」への提出 #17712418 で採用したことがある(_l 型のベストな要素と r_ 型のベストな要素が同一の要素だったときにベスト-ベストの組み合わせが作れないので、ベスト-２番、２番-ベストを次善の選択肢として用意しておいた)。■提出 #30555571 (AC / 1230 Byte / 1087 ms)

ツッコミを入れる

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

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