/ 最近 .rdf 追記設定本棚

脳log[2022-03-14～]

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

2022年03月14日 (月) 続いている Excel 日記 (20200325、20211120、20220211)。Excel でできなかったこと。シートと TSV ファイルを結びつけて１ボタンで最新の TSV がシートに反映されるようになっている(自動更新は気に入らない)。この時点ではただの「範囲」であるシートをテーブル化して便利に使いたいのだけど、テーブル化すると TSV との接続を削除されてしまう。二者択一。テーブル機能っていうのは静的な、死んだデータに対してしか利用できない機能なのか。薄々察しつつあるのだけど、Excel の花形は方眼紙や注釈や色分けなどのプレゼンテーション方面(どうでもいい！)であって、お賢い機能はまだ見ぬ Access にこそあるのか。目の前にあるのより新しい Excel にはリンクテーブルという名前の機能があると知って、やっぱりできるはずだよねーと思ったし、「[テキストファイルウィザード] が見つからない / 起動できないとき｜クリエアナブキのちょこテク」という記事を読むとテキストファイルウィザードに代わる新しい「テキストまたは CSV から」というコマンドにも見込みがありそうなんだけど(旧機能が単発のインポート機能であるのに対して新機能は継続的な接続機能であるように見える)、Excel くんよ、進化の方向は正しいと思うんだけど、君はまだ発展途上だったのかい。2000 年あたりにはもう完成していたぐらいの期待を持っていたのだけど。■次なるキーワード「Microsoft Query」「ODBC」。Excel のバージョンが古いからキーワードも古めかしい、といって以前から知っていたわけではなくてこれから試すんだけど。

ツッコミを入れる

2022年03月13日 (日) [AtCoder] 昨日あった ABC243。特に書くことはないかな。E 問題までノータイムで実装に取りかかれたけど結果は ABCD の４完。E 問題は？ 300 の３乗のワーシャルフロイド法が無しだと思って迷走して TLE で終わってしまった。■E 問題>提出 #30084536 (AC / 1281 ms)。辺のコストが２点間距離より大きい場合と、等しいけど代替経路がある場合に取り除ける。代替経路は中継地点の存在によって見つかる。あとから中継地点を探索しても計算量は変わらないけど、ワーシャルフロイド法のついでにメモしておくとちょっとは速いかな、と思いました。その他にはスタート地点までの距離を 0 にしないで初期値のままにしておくと中継地点の探索が楽になるとか(中継地点が端点のどちらかと一致する場合を除外しないで済む)、初期値を無限大ではなく nil にしておいて nil を検出したらループをさっさと抜けるとか、そういう小手先 Tips。実装量からいっても水 diff 下位だと思ったけどギリギリ青 diff だったもよう。意外。■次のステップはこういう回で F 問題に時間を残して通せないと来ないんだよ。今回の F 問題は解答の提出フォーマットがすでに謎なんだけども。■■■E 問題。「Numo::NArray でワーシャル–フロイド法の多重ループを記述削減 - Qiita」■E 問題の考察がノータイムだったのって第七回 PAST の K 問題「急ぎ旅」を解いていたからかもしれない>20210721p01.11。最短経路はどの２点間を取り出しても最短だし、最短経路同士はどの２本も分岐と合流を繰り返しながら平行して走っているってやつ。

ツッコミを入れる

2022年03月06日 (日) [AtCoder] 精進。昨日あった ABC242-F「Black and White Rooks」(黄 diff)。求めるものは読めばすぐわかる。盤面の行と列を白と黒(と中立)で分け合う場合の数。ただ、白でも黒でもいいのだけど、片方の色が何行何列を占めている場合の数が求めにくい。テキトーに配置すると想定より少ない行、少ない列の範囲内に収まってしまう。本城裕二。参考問題を知っている。ABC003-D「AtCoder社の冬」(黄 diff)。これを４か月前に解いていた>20211222。求める場合の数が一筋縄で求まらないことがわかったなら、DP で漸進的に求めていく方針も立てやすい。■提出 #29926956 (AC / 537 Byte / 715 ms)。けっこう制約が優しくて、ループ内で愚直にスキャンして掛けて足し合わせても間に合いそうではある。一応簡単にまとめられる掛け算はまとめたけども。見直していたらまとめ忘れてるところを見つけたけども。□他の提出を見て書くのだけど、ぼかしても Ruby に限るとそれは１つしか存在しないのだけど、DP を白と黒の２回やると TLE になるみたい。１回でいい理由は、白か黒の片方がきっちり X 行 Y 列を占めている場合の数が求まったなら、他方の色は N-X 行、M-Y 列の範囲にテキトーに散らしていいので、それはただのコンビネーション１つで求まる。□あと実は同じ DP だと思っていたのだけど式が違っていた。自分は包除原理の足したり引いたりを理解していないので、ある色を X 行 Y 列にテキトーに配置する場合の数から、X 未満の行、Y 未満の列に収まってしまう場合の数を引いて、X 行 Y 列をきっちり占める場合の数としている。X と Y を徐々に増やして過去の計算結果を再利用しながら求めている。解説を読んだらこちらが DP としてあちらが包除原理として両方ともが紹介されていた。■ところで昨日の結果は？自分のすべての提出。終了３分前に D 問題に滑り込み AC して４完最遅パフォでレートは微減。４完だけど６問解けたのでヨシ！前々回も似たようなことを……「３完だけど５問解けたのでヨシ！」 ABC242 は D 問題と E 問題が脳みそを絞られるような「きっつい」問題で(３回口に出た)、F 問題だけがとっても ABC らしい問題だった。D と E みたいなのは出し惜しみして ARC にまわしてくれると、ゼロ完が回避できて喜びますよ。ABC に出ても嬉しくない。

ツッコミを入れる

2022年02月28日 (月) [AtCoder] 復習(精進と復習の違いは初めて AC したかすでに AC していたかということにしてる)。20220226に関連して ABC217-D「Cutting Woods」と ABC241-D「Sequence Query」の２問。■一切の猶予なしに左右のバランスを常にとる二分木を配列に詰め込んだものは二分探索のために予め並べ替えただけのソート済み配列なのではないか、性質はそれと同じか実装を頑張った分だけ遅いだろう、二分ヒープがテキトーにつっこんだ数列からソート列を効率良く取り出せるのは内部構造の制約がほどよく緩いからだろう、じゃあちょっとルーズにするとある程度幅を持った固定長のソート済み配列が入れ子になったものになるのかな、それって (a,b)-木って名前がついてるもののことかな、っていうのが 20200930p01 の内容。■Cutting Woods の提出 #29779137 (AC / 1551 Byte / 578 ms)。Sequence Query の提出 #29779230 (AC / 1523 Byte / 865 ms)。どちらも 30 から 60 の範囲に長さを制限したソート済み配列を入れ子にした構造を共通に利用していて、1.5 KB のほとんどがそれ。問題に固有の部分はどちらも 10 行前後。次はこれを貼り付けよう。でもまだ必要なかったから削除操作はないよ。■Sequence Query を Ruby で AC してる提出を見てみると色々ある。BIT/ST を使ったもの>#29681469、#29688407、#29763276。LazySort というどうして速くなるのかよくわかんないアイデアを使ったもの>#29722776。色々っていうか今のところ AC はこれだけ。BIT を使った解法はコンテスト中に一番に考えたんだよね。20220111の日記から PAST の「Deadnames」に提出したソースコードを探してきて貼り付けた。でも WA に TLE に RE と散々の結果だったので(#29703047)、見切りをつけて別の方向に行ったのだった。■(2,3)-木でやろうとしているお仲間がいた>#29773657 (WA/TLE)。図書カードにいつも見つける名前のように「アルゴリズムと数学　演習問題集」の提出欄に常に先んじて名前が残っている人だよね。完成させてほしい。□ていうか完成してるよね？ Cutting Woods のテストケースはすべて通った。Sequence Query のサンプルは que2 メソッドの `(k-1).times` を `k.times` にすると合うようになる(search メソッドの仕様が適切にコメントしてあるからすぐわかる)。あとは速度だけ。それも 2182 ms であって 22xx ms とは違うから 182 ms 削るだけ。■テストケースが利用できる Cutting Woods でソート済み配列の分割パラメータである A,B を 30,60 から何パターンか変えて実行してみると、ほとんど傾向は変わらないんだけどやっぱり 2,3 くらい極端だとちょっと遅い。Ruby で実装してるから動的配列でありオブジェクトであるノードを細かく分けると空間コストも操作コストも無駄に大きくなりがち。スクリプトはできるだけ多くの処理をインタープリタに任せる方が性能が出やすいと思う。もちろんインタープリタもアルゴリズムのオーダーには従うから構造を工夫しているところではあり、その範囲内でのことだけど(全部を１つの Array につっこむ無茶をインタープリタに任せるとは言わない)。■めでたい。提出 #29810599 (AC /「2-3木 (高速化した第2版。仕様も変わっているので注意)」)

ツッコミを入れる

2022年02月27日 (日) [AtCoder] 今日は ARC136 の日。Writer を見ればゼロ完も覚悟するんだよなあ。幸いにも A 問題でおもてなしを受けました。B 問題からはお察し(脳みその程度を察してください)。

ツッコミを入れる

2022年02月26日 (土) [AtCoder] 今日は ABC241(Sponsored by Panasonic)があった。結果は ABC の３完。40 分考えて D 問題「Sequence Query」が解けなかった。途中から E 問題「Putting Candies」に浮気してそちらは 20 分で解けたけどコンテストは終了していた>提出 #29711639 (AC)。これは ABC175-D「Moving Piece」と同じ問題だった(どちらかといえば易しいくらい)。そのまま F 問題「Skate」にとりかかって 25 分で解けたけどコンテストは終了していた>提出 #29714203 (AC)。これはやるだけの問題だった。３完だけど５問解けたのでヨシ！■D 問題>提出 #29718230 (AC / C++)。C++ だと multiset と lower_bound/upper_bound が使えますか、というだけの問題になるんだけど、Ruby で通してる人がいる以上 C++ は甘えなんだよなあ。Twitter で読んだけど ABC217-D「Cutting Woods」を Ruby でまじめに解いた人は対策ができていたらしい。自分はテストケースの悪意を読んだヒューリスティクスで Array だけを使って通したので対策はなかった>提出 #26804547。■C 問題「Connect 6」も実は遅い言語には厳しい制約で、盤面の大きさ 100 万に対して係数が 24(=6×4) は 3 秒でもさすがに通らないだろうと思われた。縦と横だけテキトーに高速化するのに 45 分かけて WA も一度出しているあたり、がんばりましょうという感じ>提出 #29690673 (AC / 2088 ms)。■E 問題と F 問題の軽さに対して C 問題が重く D 問題が重すぎた。どんな本でもはじがきと目次と１章から順番に読む以外の発想を持たない人間のことを考えて問題列を構成してほしいものだ(わがまま)。■■■さっき書いた。「Twitter で読んだけど ABC217-D「Cutting Woods」を Ruby でまじめに解いた人は対策ができていたらしい。自分は(略)なかった」嘘だった。別解として BIT バージョンを通していた>提出 #28790707 (AC)。「対策」とは値から添字を逆引きする BIT のあまり一般的ではないメソッドのことであり、これを通したのがちょうどひと月前だってのに、どうして今日通せなかったの？■@2022-03-01 20220228で (30,60)-木を使って通したあとだけど、コンテスト中の最初の方針であった BIT を使っても D 問題を通したよ>提出 #29790983 (AC / 1944 ms / 後註)。Hash ベースの BIT でギリギリ間に合ってるのに最初の提出(Array ベースの BIT を使っていて有利)で RE/WA/TLE になったのなんでだろう。ともあれ、WA の原因は BIT の使い方に間違いがあったからなんだけど、貼り付けた自分のコードが信用できなくてサンプルを合わせるときに手を入れる場所を間違えたんだな。RE/WA だけならデバッグをがんばれたけど TLE もあったので諦めてしまった。□(註) さっきの提出のコメントに嘘があった。「アクセス可能な範囲(0..@n-1)なら」の正しい範囲は `0..@n-2`。スクリプトは合ってる。コメントだけ嘘。

ツッコミを入れる

2022年02月25日 (金) [AtCoder] 「すべての提出」ページの仕様が微妙に変わっていて、セミコロン区切りのパラメータが受け付けられなくなってる。ブックマークレットを修正した。URL を HTML(※CDATA にしていない SCRIPT タグの中も)に埋め込んだときに & を & に置き換えるのが煩わしいから(そもそも、忘れていませんか？)最初はセミコロンを使うんだけど、使えないことはまあまあ、わりと、珍しくない程度にある。フレームワークが必ずしもお手本を実装していない。■「HTTP query string」で検索したら、標準はないとあちこちに書いてある。その中で英語版の Wikipedia「Query_string#Web_forms」から。「The series of pairs is separated by the ampersand, "&" (or semicolon, ";" for URLs embedded in HTML and not generated by a <form>...</form>. See below).」「This convention is a W3C recommendation.[6] W3C recommends that all web servers support semicolon separators in addition to ampersand separators[9] to allow application/x-www-form-urlencoded query strings in URLs within HTML documents without having to entity escape ampersands.」 W3C がってところが今となっては、かなあ。もちろん立場が違えばセミコロンが解釈できなくて話が通じない相手とはそれまでっていうのが自分のスタンスなんだけど、AtCoder には合わせるしかない。■@2022-03-07 最近 OpenBD のデータが、抜けているというより常に取得できてないなと気がついて見たら、セミコロン区切りのせいでクエリが失敗するようになっていた。ここでもなのか。

ツッコミを入れる

2022年02月23日 (水) [AtCoder] 精進。ABC010-D「浮気予防」(青 diff)。ABC239-G「Builder Takahashi」を解こうとして思い出したのが考えても解けていなかったこの問題。浮気予防を解くために浮気予防の解説を読むのは癪だけど、Builder Takahashi を解くために浮気予防の解説を読むのは許されるような風潮が、あるとは思いませんか(そもそも禁じられていない)。読んだら最小カットだって。聞いたことだけはある。蟻本を開いたらちょうどのページにしおりが挟んであった。TODO ということでありまだ理解できていないということ。190 ページのプログラムを Ruby に翻訳しただけ>提出 #29610100 (AC / 366 Byte / 89 ms)。ソースコードを見れば一目瞭然だけど、高橋くんのギルティは疑いようがない。本命の Builder Takahashi はわかりません。

ツッコミを入れる

2022年02月22日 (火) [Xperia 10] 購入前に悩んでいた(20190511)携帯手段について書いていなかった。端末と同時に買ったガラスフィルムとプラスチックケースを付けて布袋「日本製スマホケース帆布手作りスマートフォン用ポーチ iPhone6/Samsung マルチケースＬサイズ (インディゴブルー)」に入れたものを前ポケットに突っ込んでる。カラビナにベルトを通して。Xperia 10 は長いからどうしても片方の角がポケットから出るし、たとえばトイレでズボンを下ろしてしゃがんだ時にはポケットの天地が逆向きになって落下しそうになってるんだけど、ボタンがあるので安心。位置的に車から降りようとして振り向くような動きをするときに角が削れそうになるのだけは注意かな。プラケースと筐体の左下隅が 1 mm ほど欠けてる。帆布製のケースは内寸が 16 cm 強で、Xperia 10 が 16 cm 弱だから、あつらえたように 5 mm ほど余裕を残して収まって無駄も不足もない。スナップボタンの裏側は裏地に隠れていて傷を付ける心配がない。もっとも、画面の側が太ももに向くように(そして逆立ちするように)しまうんだけど。この布袋を見つけたから今 Xperia が持ち歩けている。携帯できない電話ならいらねーんだ。これは今の Xperia の大きさや比率に不満があるということではなくて、むしろ電話らしいフォルムを保っていることが重要なファクターだった。人間の耳と口の位置は決まっているわけなので、短さや小ささが必ずしも正義ではない。スライド式(20071026p01)や折りたたみ式でないことが残念ではあるけど、それだって画面の広さや薄さをトレードオフとして差し出して得られるものなので、懐古趣味の無い物ねだりではある。

ツッコミを入れる

2022年02月21日 (月) [AtCoder] 復習。おとといの、だけど前々回の ABC、デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）-F「Construct Highway」(青 diff)。頂点数と辺の数から木であることを読み取り十分に利用しなければいけない。コンテスト中唯一の提出は終了３分前のこれ>提出 #29471962 (WA×18 / AC×11)。木である条件が十分に詰められていなかったし、効率にも配慮できていない(ループ中の find メソッド)。■数時間後の提出 #29479636 (TLE×7 / AC×22)。効率にも配慮したつもりだったけど当然起こりうる状況が想定できていなくて、24 行目の flat_map が予想外に非効率で TLE。単要素の配列が信じられないくらい大量に作られることになる。■さらに２時間後の提出 #29483013 (AC)。この問題のキーであるあと１本だけ辺が欲しい連結成分を特別扱いすることで効率を改善して AC。おまけにソートもなくなった。ところで、不可(-1)を出力して終了する no! メソッドの呼び出しが８か所もあるって多すぎだよね。■今日の提出 #29561496 (AC)。no! の数を５個に厳選してそれぞれに理由を示すコメントを付けた。保険のための余分な no! はもうないと思う。もっと減らしたかったけど 22 行目の `no! if U[a,b]` の no! を取り除くとダメになるケース(`8 4／3 3 3 1 1 1 1 1／1 2／1 3／2 3／7 8`)がある。この提出 #29483417 (WA×1) を阻んでいる random_21.txt が同等の(無駄な辺と森化による辺の必要数の減少が相殺する)ケースだと思う。■■■E 問題「Subtree K-th Max」。最近似た名前の問題がありましたね>「Prefix K-th Max」。一読して表現の微妙な変化に気がついたんですよ。ABC234で「K 番目に大きい値」という表現だったものが ABC239 では「大きい方から Ki 番目の値」になっていた。それが「中途半端な値は見ようによって大きい値でもあるし小さい値でもある。自分に言わせればそれは単に「大きい方から K 番目の値」なんであって、大きい値でも小さい値でもない」をうけての変化だとは思わないけど、自分が理解しやすい表現になっていたのは間違いない。それなのに AC 前の５分で 2 WA しました(WA、WA、AC)。読んで、表現の変化にも気がついて、でも結局間違えるんだ。手癖で書いてるってことなんだろうなあ。■「AtCoderの公式生放送「あーだこーだー」第51回 - YouTube」を聞いていると E 問題「Subtree K-th Max」に関連して Wavelet Matrix の単語が何度も聞こえてきた。E 問題では K の上限が意図的に小さく抑えられていて、ここを突破口にして解けよ、というヒントがあからさまだったけど、さもなければ Wavelet Matrix を使って解くことになったらしい。Crystal では通ってるぽいのに Ruby で TLE になるの悔しいよね。通ってほしい。参考図書『[単行本] 岡野原大輔【高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)】岩波書店』は持ってるだけは持ってる。WEB+DB PRESS vol.42 の記事を読んで著者の名前を覚えていた。

ツッコミを入れる

2022年02月20日 (日) [AtCoder] 今日は ABC240 があった。見たことのある問題が多かったかな(万年 ABC rated だからだよ)。■C 問題「Jumping Takahashi」。アルゴリズムと数学　演習問題集の 96 問目「Cooking」が ABC204-D と同じ問題で、すでに ABC で解いていたけどそのときの解法が思い出せなかったのでビット演算で解き直していた>提出 #29359695 (AC)。それが４日前。今日の提出もビット演算で>提出 #29519763 (AC)。気がついたけど、ほんのちょっと前の ABC-D が ABC-C として出たってことなのね。■D 問題「Strange Balls」。ぷよだと思ったけど連鎖がなくてちょっと物足りない。必要な情報をメモしてシミュレートするだけ>提出 #29524639 (AC)。■E 問題「Ranges on Tree」。問題文が難しい。３割くらい理解を投げ出しかかっていたけど、途中でもうオイラーツアーが見えていたのでそれをガイドにして(予想がついている内容が外れていないことだけを確認して)読み通すことができた。昨日の F 問題「Construct Highway」がコンテスト終了後とはいえ解けていて気力が充実しているのでなければ危なかった。適当なタイミングで数字をインクリメントするだけ>提出 #29531766 (AC)。こういう問題をもっぱらスタックを陽に持ったループで解くのは 20 万回の再帰呼び出しがローカルではスタックオーバーフローを起こしてデバッグも答え合わせもできなくなるから。ネットで読んだ方法が効かないのはなんでなの？■F 問題「Sum Sum Max」。加速度と速度と距離。それは３か月前に解いたこれ「ARC077-E「guruguru」(黄 diff)。それほど難しくはないかな。ABC-D＋α という感じ。プラスアルファで悉くつまずいて AC に辿り着けないのが自分ではあるが。(略)。時間軸に沿って加速度と加速度の累積としての速度と速度の累積としての移動距離を記録して答えにする」。極大値が見えていなかったりとりあえず代入しておいた初期値を答えにしてしまったり、逆に開始点を答えの候補から漏らしてしまったり、答えを合わせるのに大変苦労した。「プラスアルファで悉くつまずいて AC に辿り着けない」とか「区間の左右端と節約回数の上下端が off-by-one エラーを誘発しやすい感じ(ドツボにはまった経験から書いています)」を今日も再現しておかしくはなかった。早々に愚直解とランダム入力を組み合わせてダメケースの発見に努めることができたのが運命の分かれ目。終了３分前の提出 #29545375 (AC)。これ水 diff なんだって。全く同じではないにしてもかつての黄 diff が形無しですよ。

ツッコミを入れる

2022年02月19日 (土) 「よーわからんが、unsignedの2数の平均だったら、2で割ったものを足すだけでいいんじゃないの？ 1ビット分誤差が入るからダメって？」 / Twitter」■これ文脈が二分探索なのでは。統計処理ではなくて。整数型なのには意味がある。このトピックが定期的に取り上げられるのはオーバーフローが原因となって言語(ライブラリ)が修正される事例がある上に、知らなければ最初に書いてしまう式だからだと思う。誰もが通る道。１ビットの誤差について、仮に二分探索で左が 3 で右が 5 のときピボットが 3/2+5/2 == 3 になってしまうと 4 がテストされる前に探索が終了してしまう。それは誤り。２数が１の場合でも UINT_MAX の場合でも誤差が１なら「1ビット分誤差が入るからダメって？」に対するツッコミにならないのでは？という疑問には、それはそうと思う。誤差が大きすぎるという納得はわからない。

ツッコミを入れる

2022年02月18日 (金) 「3000ミリ秒近くかかっている。なお Perl で同じコードを実行してみたところ、5ミリ秒で終わった。 Ruby では 22 秒（ミリ秒ではない！）かかった。正規表現の実装が、ぜんぜん違いそうである。」 / Twitter」■へー。たしかに Ruby だと 30 秒くらいかかる。よくある * や + を入れ子にしてバックトラックが～というのではなく、単純にマッチ開始位置とマッチ失敗までのスキャンとがともに入力に比例する N^2 時間かかってる雰囲気。マッチテスト開始位置をずらしたときに「おや、ここはもう通った道だ」と気が付ければいいんだろうか。文字列内の位置とエンジンの内部状態が一致するならすでに出ている結論を流用できる、的な。テキトー言ってるけども。シチュエーションを限定しないとどんだけコストがかかるか想像できないけども。■「正規表現の脆弱性 (ReDoS) を JavaScript で学ぶ」

ツッコミを入れる

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

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