/ 最近 .rdf 追記設定本棚

脳log[2022-05-04～]

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

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)

ツッコミを入れる

2022年03月26日 (土) [AtCoder] 今日は ABC245 があった。なんか変な回だった。自分のすべての提出。AC までの時間が……A=４分半、B=２分、C=６分半、D=未提出、D+E=１時間８分、F=９分。D 問題解きたかったなあ。知ってる問題を早く解くのが能じゃないんだよ。■D 問題解けたよー。提出 #30487945 (AC / 183 Byte / 64 ms)。行列を使わないと決めて考えれば特に難しくはなかった。なんかそれっぽい雰囲気に惑わされて慣れないことをしようとしていたのだった。最高次の係数から確定していく。確定した係数の影響を書き込んでいくことでより低次の係数を確定する準備とする。変数が M+1 個なのに対して方程式が N+M+1 個あって式が N 個余る気がするのに戸惑うんだけど、そこは An 以外の A は 0 になることがあるので勘定に入れてはいけないとかそういうこと？

ツッコミを入れる

2022年03月24日 (木) Excel 日記(前回>20220314)。Microsoft Query なら Excel 2007 でも使えるし、TSV ファイルをインポートした結果の範囲データが含まれるシートをテーブルとして抽出することもできる。できたのだけど、更新に問題があった。■背景。TSV ファイルと接続していて更新ボタンを押すことで最新の内容がインポートされるシートがまずあって、同じブックの別のシートへ Microsoft Query を通してそのシートの内容をテーブルとして取り込もうとしている。回りくどいことに同じブックのシート(最新の TSV を反映する範囲データ)からシート(テーブルデータ)へデータを変換するために Microsoft Query を経由している。最近の Excel で使えるらしいリンクテーブルや[データの取得と変換]機能が使えないことと、TSV との接続を保ったまま範囲データをテーブル化できないことからとりあえずこうなっている。■Microsoft Query を使って同じブックの別のシートの範囲データをテーブルとして取得することはできた。しかし更新しようとするとブックの形式が無効だとかそんなエラーが出て更新ができない。そのブックってエラーを出しているあなた(Excel)が作成した(そして今開いている)ブックなんですよ。それともエラーを出しているのは Microsoft Query なのか。でも最初の取得はできたんだよ。Excel が Microsoft Query をうまく操縦できていないのではないか。排他制御とかが関係してるんか。■自動更新テーブルが利用できないなら Excel のバージョンを新しいものに限るのもやむなし。更新(行の拡張)にしろテーブルの結合(列の拡張)にしろ、手作業でちまちまやりたくねーもんな。どっちも機械にやらせたい。範囲データからピボットテーブルを作成したとして、後から追加されたレコードは範囲外になるからピボットテーブルを更新しても反映されないらしいのだ。テーブル化してあるとそういう落とし穴がないらしいので、自動更新もテーブル化も必須。■これなのかなあ。「ODBC接続設定画面のようなものが出ます。ここにExcel Filesというものがあるのですが、これは旧形式のxls形式しか使えないので、ここでは新規データソースを選び、OKを押します。データソースの名前は適当に。対応するドライバーの選択では、Microsoft Excel Driverでxlsxやxlsmを使えるものを選択します。」でも Excel Files を選んだあとのファイル選択ダイアログの拡張子フィルタは .xls になっていて、信じるなら .xlsx は対象に含まれる。そして実際にテーブルを抽出できていた。でもまあ他の方法を試してもいいだろう。■TSV の元データは COBOL のデータベースから変換した SQLite3 データベースなので(20170315、20170807)、TSV を経由しないで SQLite ODBC Driver を使うことも考えてる。でもあんまりたくさんのバイナリファイルに依存したくないお気持ち。■翌日@2022-03-25 その他のデータソースで .xlsx に対応した Microsoft Excel Driver を選ぶことで抽出から更新まで普通にできたわね。こうなると欲が出てきて、*.csv に対応した Text Driver を使うことで TSV ファイルを直接テーブルとして取得したくなるんだけど、ファイルの場所としてローカルドライブとネットワークドライブしか選ばせてくれない。コンピュータ名を使いたい。管理ツールに「データソース (ODBC)」という項目を見つけたのだけど、何か使えるだろうか。■Microsoft Text Driver はたぶん「ANSI」と「Unicode」にしか対応していない。UTF-8 だとエラーメッセージを出して読んでくれない。今以て Excel 自身が UTF-8 な TSV/CSV ファイルを開けないことに驚かされるくらいなのでまあ(メモ帳にも劣るんだよなあ)。Word は差し込み印刷のためのソースとして TSV/CSV を選んだときにコードページ一覧から選ばせてくれるから UTF-8 でも大丈夫(えらい)。

ツッコミを入れる

2022年03月23日 (水) [AtCoder] 精進。大和証券プログラミングコンテスト2021（AtCoder Regular Contest 128）-C「Max Dot」(青 diff)。「茶 diff も緑 diff も解けないゼロ完だった」回の ARC。今もって A 問題も B 問題も解けないんだけど C 問題はなんとかなった。だけど難しい。■もっとも単純なケースとして A 数列が昇順に並んでいる場合を考える。この場合は A 数列を後ろから見ていって、合計が S を超えない範囲で順番に上限である M の重みを割り振っていけば最大値が達成できるし、前から見ていったときに重みが減少していてはいけないという条件も満足できる。次に１つだけイレギュラーを起こして、A 数列のある要素が直前の要素より小さくなった場合を考える(ある要素を除けば全体として昇順になっている)。ある小さな要素と直前の要素をその平均で置き換えたときに数列の全体が昇順になるのなら、最初の場合と同じようにして最大値が達成できる。平均を取った２つの要素に揃って M の重みを割り振るにはもちろん S から 2M 分の割り当てを確保しなければいけない。これらを踏まえて実際に行う操作は、数列を後ろから見ていって基本的には平均を取る。現在の要素とこれまでの平均を比べて昇順になっている(現在の要素の方が小さい)なら平均を取るのを区切って新たな平均を取り始める。そして先頭まで処理が済んだら昇順になった区間に後ろから重みを割り振っていく。■提出 #30369066 (AC / 64 ms)。自分は１回の操作で満足していたのだけどテストケースが合わなかったので数列が完全に昇順になるまで何度でも操作を繰り返すようにしたらなぜか時間内に答えが出た。考えれば１回の操作で数列の長さは必ず１以上縮むのだから、最悪 N の２乗を想定しておけば答えは出るのだった。64 ms は 5000 の２乗よりずっと速いので何かが見えていない可能性はあるが。■これを「やるだけ」とか言って解きたいものだ。■自分のは ixrs さんのこの提出 #26597419 (AC / 61 ms) の劣化版みたいなものだな。自分が前半のループで `if ～ else ～ end` と書いているところがあちらでは `until groups.empty? do ～ end` になっていて、新しい配列を伸ばす一方ではなく処理対象にしてしまっている。そのおかげで一度のスキャンで必要な処理を終えられているのだろう。自分のように何度も何度もスキャンしないで済んでいる。それ以外の部分は全体的によく似ていて理解がしやすいあたり、O(N) 解法までわりと惜しいところまでいっていたのだな。解説に書いてあった O(N) 解法のヒント(凸包)が何のことかはさっぱりわかりませんが(「俺は凸包の点数はいらねーんだ」「それは自分の人生とは一切関わることのない専門用語」)。■まねまね>提出 #30381972 (AC / 66 ms)。

ツッコミを入れる

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

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