/ 最近 .rdf 追記 設定 本棚

脳log[2022-05-23~]



2022年05月23日 (月) [AtCoder] 精進。ARC045-C「エックスオア多橋君」(ギリギリ黄 diff)。一読して全方位(?)木 DP だと思った。提出 #31922668 (AC / 555 Byte / 626 ms)。20211014 で解いた第八回 PAST の H 問題「最短経路」と同じ解答の形。■Ruby での提出一覧を見ると一番速いのが 392 ms のこちら>提出 #2757184。仮に頂点 1 に値 0 を割り振って、その他の頂点の値が何になるかを求めている。それから XOR が X になる値の組を数えている。頂点 1 からのパスによって決まる値だけを考えて答えを出していい理由は、たぶん LCA までのパスが相殺されるからとか? 最後から2行目の ans -= N if X == 0 がはまりやすい罠に見える。X がゼロの時、同一頂点をペアにして数えてしまうのを除外している。もしやと思って直前の WA 提出 #2757181 を調べてみるとこれが原因だった。WA から3分半で気がつくかあ。無理だよ。他に Ruby で解いている人はゴルファーが一人いるだけ。古い問題なのもあるだろうけど、一見して面倒くさく見えるのも影響してそう。■ブログ記事を7つ読んだけどどれも LCA で相殺を利用していた。考える前に手を動かしている脳筋はいないのか、脳筋は。


2022年05月22日 (日) [BOOX Max2] 20220107 に書いたときからさらに劣化してバッテリーの寿命が尽きていることが間違いのない Max2。ケーブルを繋ぎっぱなしで使えばいいのだけど、家の外に持ち出さないにしても案外に煩わしい。Max2 対応をうたうバッテリー交換キットが売っていたので博打のつもりで交換してみた。さてどうなるか(充電中)。発火さえしなければいいよ。■■■完・全・復・活!


2022年05月20日 (金) 入力中の個人情報が“送信ボタンを押す前に”収集されている問題 約10万のWebサイトを調査:Innovative Tech - ITmedia NEWS」■こういうことがあり得ると思ったから、毎月自動振替で利用しているサービスのログイン画面にキャプチャ(CAPTCHA)のための外部スクリプトが埋め込まれたときに、ログインできなくなった、そのドメインを信頼してスクリプトの実行を許可してもいいかと問い合わせたよね。めんどくせー奴。最初は良くてもあとからこのように(「2020年7月にサービスを終了しましたアクセスログ解析サービス Visionalist においてログ収集システムとして利用しておりました“tracer.jp”ドメインを、当社が廃止した後、第三者がドメイン管理会社から取得し、セキュリティ上問題があるスクリプトを設置している可能性があることが判明しております。」)、ドメインの所有者が変わって(変わらなくても)中身が変わることがあるわけなので、接続しているサイトと異なるドメインから送られてくるスクリプトは基本的にブロックするよね。tracer.jp ドメインがその例だし、今でも facebook.com とか google-analytics.com から送られてくるのとか必ず。めんどくせー奴。


2022年05月18日 (水) [AtCoder] 精進。パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 251)-G「Intersection of Polygons」(ギリギリ橙 diff)。答えをね、見ました。「アライグマ「G問題は、多角形の内側が「辺のこっち側」の積集合になることを知ってれば解けるのだ!」 フェネック「逆に、このことだけに気を取られてると嘘解法に引っかかる問題もあるよ。考えてみてねー」 https://t.co/9AbUhEnUZq」。といってもツイートがストレートに答えというわけではない。「辺の~積集合」に注目してちょっとは考えた。最大 50 角形の凸多角形が最大 20 万個あるわけなので辺の数は最大 1000 万本。これを一本一本チェックしていては最大 20 万個のクエリには答えられない。最大 20 万本の平行な辺から代表を1本だけ選ぶことにすれば、各クエリに対して最大 50 本の辺をチェックするだけで済む。提出 #31786740 (AC / 557 Byte / 1727 ms)。■自分の提出が 1727 ms のところ Ruby で先に AC していた hmmnrst さんの提出 #31756127 が 1551 ms。この差は明らかにメインループの照合部分が (a-x)*dy<=(b-y)*dx (遅い) か dx * px + dy * py >= threshold (速い) かに由来している。演算子の数が違うからね。だけど3つのペクトルをどう組み合わせれば引き算部分を事前に済ませておけるのかわからない。もうひとつ 10 行目の offsets.max_by もわからなかったよね。自分は辺と点の関係をあっち側こっち側の2値でしか扱わなかったから、値の大小を比較する max_by が選択肢になかった。外積が平行四辺形の面積なら値の大小は高さの大小であり符号と絶対値は辺のどちら側にどれだけ離れているかを表している。こちら側に一番離れている点が選ぶべき代表点であり、それを max_by で選べると事前準備の M 回の繰り返しがすごくシンプルになる。自分の提出は少なくとも2つの点で遅れをとっていた。■というのを踏まえて整理しました。提出 #31797336 (AC / 333 Byte / 1575 ms)。短く速くなった。速さは同じくらいに追いついたけどメモリ使用量がほぼ例外なく 1.5 倍くらいあるのがよくわからない。とくに富豪的な無駄遣いはしてないはずだけど……(多重代入?)。事前計算については意味を考えず単純に展開してクエリと無関係な定数部分を括りだして覚えておいた。


2022年05月17日 (火) [AtCoder] 精進。Code Formula 2014 本選-F「100個の円」(水 diff)。■AtCoder ではなかなか類題が見つからない問題。まずは面積の比較。敷き詰める範囲が 1500×1500 = 2250000。そこに置く円の面積の合計が約 1062958 (48 %)。円が四角形だとすると 1353400 (61 %)。それほど厳しくはないのかな。空き領域と置く円をすべて正方形として扱うことにする。大きい正方形ほど置く場所に困るから、一辺が 200 の正方形から順番に置いていくことにする。■提出 #31770604 (AC / 325 Byte / 60 ms)。ブログや提出一覧を見るといろいろな考え方があることがわかる。自分の解答のできがいいとは思わないけど、許容範囲の広い制約だったのだ。


2022年05月16日 (月) You Suck at Excel with Joel Spolsky - YouTube」■『Joel on Software』と『More Joel on Software』でおなじみスポルスキさん。ほぼ1時間まるまる見ちゃった。英語なので聞き取れるのはいいとこ 5 % くらいだけどそこは画面で補える。最近書いている Excel 日記をなぞる内容がほとんどだったのも理解を助けている>202204022022032420220314202202112021112020200325。■Excel の理解を助ける豆知識の補足。Excel における日付と時刻とは何か。日付は整数で時刻は1未満の小数、だと理解したんだけどどうだろう。整数や1未満の小数やそれを足したものを書式設定で日時に見せている。だからたぶん DATE 関数の値と TIME 関数の値は足し算できると思うんだけど(まだ試していない)、知らないから DATETIME 関数を探したよね。■Ctrl+Enter と Ctrl+Semicolon は知ってるから聞き取れたけど、行データが並んでいる範囲の大枠(テーブル化しているわけではない)を一括して選択する方法は聞き取れなかった。何ページ分も画面をスクロールしたくないから、それはすごく知りたい。あとすごかったのはセルの値を決めてからそのセルに影響するセルのうちの1つの値を逆算させられるってこと。Excel は高機能だしはまればすごいのは確かなんだよね。セルの右下に現れる+ボタンとかマジ万能。結果が予測可能で結果が望んだものである限りは。■最近感心したのはピボットテーブルの集計値の種類に基準値との比率というのがあることと、その基準値の選び方に前の値というのがあること。前年同月比を表示する方法を調べていて見つけたんだけど、まさしくそういうニーズに応えるために用意されている項目だと思う。データベースだと行同士の関連だとか並びだとかは想定されないので、前の行の値が参照できるのは決して当たり前ではない。


2022年05月15日 (日) [AtCoder] 昨日の ABC251 の終了時刻前後のどたばた。「@chokudai コンテスト終了直前30秒くらいは提出ができなかったことは正しいですか?(502エラーが出た ことは僕以外にも複数観測しているので)」 / Twitter」■自分は終了間際に提出はしなかったけど、終了直後に提出一覧を確認しようとして2、3度 502 エラー(だったと思う。サーバー起因のエラーだった。だから 500 番台)画面を見た。終了間際の駆け込み提出みたいな行動が傾向として存在するなら、処理能力オーバーからのエラーで不受理(&提出リトライが間に合わず)は十分に考えられそう。■■■今日は ARC140 があった。昨日の ABC について(すぐそこに)書いていたのは ARC 開始直前だったのだけど、まさか今日の自分が滑り込み AC をするとは思っていなかった。提出 #31729672 (AC / 2022-05-15 22:59:55 / 終了5秒前。コンテスト終了のメッセージ背後の暗転した画面でジャッジが進行する様を見守るのは心臓に悪い。たったの 1 WA であってももう修正はできないのだから)。もしこの AC がサーバーエラーで不受理だったらと考えると、受け入れるのはなかなか難しいだろうなあ。飛び上がって喜ぶ瞬間だったはずなんだもの。■慰めとしては、早めの N 完と N+1 完最遅のパフォは連続している(ほとんど差がない)ので、粘って粘って1問余分に解いたことで上乗せされるパフォーマンスは、苦労や達成感に見合ってはいないなあといつも思います。自分のパフォーマンスのばらつきが 1000~1600,1900 くらいなので、100 や 200 の差は誤差なんだよね。解けへんかってもほとんどおんなじパフォやったやんけって思う。嬉しいような嬉しくないような。ここから得られる教訓。最後の1問と定めて腰を据えるのならばその1問は後ろの方から選ぶこと。解ける見込みがわずかでもあるならそれで十分。賭け金(一番解きやすいであろう次の1問を解いて得られるパフォーマンス)は安い。■■■AtCoder から障害報告。「【ABC251の障害について 1/3】 前回のコンテストにおいて、22:39頃に、サーバのうち一台が502エラーを返す現象が発生しており、一部提出が出来なかったユーザが発生しておりました。申し訳ありません。 コンテストへの影響が小さいため、コンテスト自体はそのままRatedとさせて頂きます。/ Twitter」 Unrated なら今度はこっちががっかりしちゃうし、仮に Unrated が続くと張り合いも参加意欲も減退するのが避けられないから、妥当な判断かな。


2022年05月14日 (土) 古典を教わった先生が同じ学校の校長先生になっているらしい。みんな年をとったのだ。


2022年05月13日 (金) [AtCoder] 精進。Code Formula 2014 予選B-C「仲良し文字列」(水 diff)。AtCoder Problems の Recommendation なのであって特に選んだわけではないけど、おととい(20220511)解いた「Make UTPC」と似た雰囲気の問題であった。こちら(仲良し文字列)の方がやや易しく感じられるのは、注目している文字列の外から文字が供給されないところ。スワップ対象がすべて見えている。それによりスワップ関係(ペアでの位置交換)にない要素はローテート(三つ組以上での位置交換)の一部だと決め打っていける。3個以下のペアと2個以下のローテートで全体が把握できる。■提出 #31625678 (AC / 560 Byte / 61 ms)。不一致の数と、並べ替えで一致するかどうかと、位置を交換しているペアの数と、余った手数を費やす無効な(同じ文字同士の)交換が利用可能かどうかを調べれば答えが出る。□あと、バグがありますよ。11 行目の c+d を文字列の連結のつもりで書いたけど 7 行目で .chars ではなく .bytes を呼んでるので文字コードの足し算になってしまってる。それだと a と d が位置を交換している場合と b と c が位置を交換している場合など、異なる文字コードの組み合わせだけど和が一致する場合を区別できない。


2022年05月12日 (木) [COSMOS] 家のルーター(WZR-AGL300NH)がここ1年で何度か Wi-Fi が繋がらなくなって再起動すると直るということを繰り返している。正直まだ使って使えないこともないけど、少し前に新しいものを物色していた(けどやめた)こともあり、Wi-Fi が死んでいるのに気がつくのが遅れると知らず「ギガ」が減る罠もあり、今の機種の発売が 14 年前なのもあり、もう潮時かなと。■あらためて調べたら下から五千円、一万五千円、二万円、三万円という感じ。VPN サーバー機能を内蔵してますよとか USB ハードディスクを繋ぐだけで NAS になりますよとかいう機能があれば惹かれるけど、そうすると2万円になる。そのレベルでのこだわりはないかな。■実質タダで光電話アダプタに無線 LAN 対応のルーター機能を統合できる(対応機器に交換する)ことがわかったのでそれで。今日届いたので入れ替えた。


2022年05月11日 (水) [AtCoder] 精進。UTPC 2021-A「Make UTPC」。「A 問題は運営の想定でセット内で最も易しい問題です」。すっごく難しかったよ。■最初は長さ4の文字列をすべて切り出して「UTPC」との不一致を数えればいいと思った>提出 #31608295 (WA×13)。これはスワップによる交換回数の節約が考慮できていない。■そこで交換が1組ある場合と2組ある場合を列挙した。提出 #31608534 (WA×6)。これはスワップしていない部分が「UTPC」と一致していることを(勝手に)条件にしていて列挙に漏れがあった。■提出 #31608677 (WA×3)。一致不一致とスワップを独立して数えるようにしたら WA が3つ減った。だけどこれは3つ組4つ組が位置をローテートしている場合の交換回数の節約が考慮できていない。■提出 #31608753 (WA×3 / 列挙漏れ)。提出 #31608788 (WA×3 / 列挙漏れ)。■提出 #31609353 (WA×1)。ようやくローテートしているものを考慮することで WA が2つ減ったけど、唯一残る WA は「UTPC」との一致がゼロでスワップもゼロで「UTPC」のアナグラムでもないケース。つまり考え得る最悪のケース。全列挙して調べたけど、実は交換回数の最大は4回ではなく3回だった。■提出 #31609535 (AC)。すっごく難しかったよ。


2022年05月10日 (火) [AtCoder] 精進。灘校文化祭コンテスト 2022 Day1-H「Traveling PCT Problem」。やることの9割は典型90問の「035 - Preserve Connectivity(★7)」と同じ。それはすぐわかる。それへの提出 #23482781 の最後の1行 ds.sum/2 (相当)を ds.sum-ds.max に変えるだけでいけると思ったけど駄目だった>提出 #31435269 (WA×20 / AC ×14)。■今日の提出 #31585826 (AC / 1068 Byte / 1671 ms)。答えをね、見ました。「Hは与えられた点を連結にする辺だけ残した部分木を考えて、それの辺数の2倍から直径を引く」。引くのは目についたテキトーな数字(ds.max)ではなく直径だと。言われれば、うーん、まあ、うーん、そうかもね、という感じ(わかっていない)。木の直径についてはこのとき(20211004p01.02)に一応のイメージを持っていたが、自分では見つけられない。


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