/ 最近 .rdf 追記 設定 本棚

脳log[2022-01-17～]

最近

2022年01月17日 (月) [AtCoder] 精進。ABC027-D「ロボット」(黄 diff)。初見ではない。埋めきれなかった古い ABC を埋め直している。入力に関する制約が解法を制約するヒントになっている。一度だけスキャンして答えが出せる。縦のものを横に見られるかどうか。+/- に応じて +x/-x するというのが縦の見かたなら、M に応じて x を +1/-1 することが +x/-x する操作にそれぞれ何回寄与するかを考えるのが横からの見かた。提出 #28608177 (AC / 157 Byte / 72 ms)。気がつくと簡単に答えが出て気持ちがいい。■横からの見かたが培われたのはたぶんこのとき>「足し算とはそういうものだ、と言われたら言葉がない。私は足し算がわかりません。」 なんだ、より難しい類題を解説 AC していたから解けただけだった。

ツッコミを入れる

2022年01月16日 (日) [AtCoder] 精進。キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227)-E「Swap」(黄 diff)。「D 問題ダメでした」の回の ABC なので E 問題は読んでいなかった。考えたのはどうやって状態をまとめることができるか。並び順を区別してしまうと、たとえば K,E,Y がそれぞれ 10 個ずつ使われている場合に 30!÷10!÷10!÷10! > 5.5 兆通り(本当？)の文字列を考えないといけなくなって間に合わない。並びではなくて、それぞれの文字をいくつ使ったかと、それだけ使うのに何回の操作を要したかの組み合わせを考えることにした。たとえば K と E と Y を１回ずつ使って長さ３の文字列を構成することを考えると、KEY,KYE,EKY,EYK,YKE,YEK のそれぞれを作るのに要する操作回数は同じになる場合も異なる場合もあるので、操作回数ごとにまとめて場合の数を記録する。それら操作回数と場合の数のペアが (K×1;E×1;Y×1) という(長さ３の文字列がとる１つの)状態に対応する。これを長さ０の文字列から始めて１文字、２文字と遷移していく DP で。■提出 #28591194 (AC / 1008 Byte / 92 ms)。1007 Byte を書き下して実行してみれば文字列が閉じていないというシンタックスエラーを除いてバグ無しでびっくりした。入力される文字列長が最大で 30 だから内側のループで線形時間の愚直スキャンをしても許されるのが優しい。だからこその ABC-E だったのかもしれないけど……(E 問題はおろか D 問題も解けなかった)。■こちらの提出(#27283710)によると公式解説動画でメモ化再帰を紹介していたもよう。すっごく短く書けるっぽい。長くはなったけど 92 ms は Python と比べても速いみたいなので良しとしよう。■ダメだった D 問題は「実は……」と解説に書かれている内容を鵜呑みにして AC をとっただけなので日記にはなりませんでした。提出 #28342280 (AC)。■ところで、E-Swap に提出した AC スクリプトにおける I 変数は、昨日あった HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235）-C「The Kth Time Query」のためのデータと同じ構造をしている。C 問題が E 問題を解く道具になっていることが確認できるのはいいね。

ツッコミを入れる

2022年01月11日 (火) [AtCoder] 精進。第九回 アルゴリズム実技検定 過去問-M「名前の変更」。やることは明確で簡単(英語の問題名が「Deadnames」ってこれヒントですよね？ 言語差別だー)。問題は制約の大きさ。BIT でやった>提出 #28465041 (AC / 1054 Byte / 2778 ms)。提出したスクリプトで BIT#index が担当する、値から添字を逆引きする処理をこれまで書いたことがなく、できるかどうか、どうやるのかも知らず、デバッグに大変苦労した。そういう処理を書かなくても BIT#[] メソッドと二分探索を組み合わせて代わりにすることはできるだろうけど、計算量が log^2 になるのが問題になりそうだった。その失敗は LCA のダブリングを初めて書いたときにすでに経験している>20210617p01.02。log が log^2 になったとき 2778 ms が制限時間の４秒におさまるかどうかは、どうだろう。ところで、サイズ N の BIT を N より多く確保して許されるかどうかは運でした。■Python で一番速い提出では BalancingTree という構造を使っていたが知らない>#28312971。その次の人は AVL 木という名前の構造を使っていたが知らない>#28339871。Python で一番短くて速い提出が２つのメソッドと２つの配列で何をやっているのかはさっぱりわからない>#28288268。■どうせ運に任せるのなら N×N の規模の BIT を１つだけ使うのでも良かったのでは？>提出 #28467644 (AC / 757 Byte / 2894 ms)。ちょっとだけ遅くなった。

ツッコミを入れる

2022年01月09日 (日) [AtCoder] 昨日あった ABC234-D「Prefix K-th Max」。解けなかったんだよ。言い訳がいくつもある。一度はプライオリティキューを貼り付けたし、プライオリティキューを使わないで適当なメモを使ってうまくやる方法もずっと考えていた。一番の誤算は「K 番目に大きい値」に対する勘違い。解法を一通り検討した後でサンプルを読んで間違いに気がついた。この用語の難しさについては AtCoder 社長のツイートで読んで知っていたのに、迷いなく小さい方から K 番目の値を答えようとしていたのだからどうしようもない。そこから頭の中をリセットするということがまず難しかった。K 個の値を蓄えたプライオリティキューから最大の値を答えつつ、K+1 個目の最小値をキューから追い出さなければいけないような気がしてしまって手詰まりに陥っていた。意味不明なキメラ。言い訳ですよ。能力の絶対値が低いところをさまよっているからこういうところでつまづくし、そのまま転んでしまう。■PQ 解法>#28432346 (810 ms)。メモ-スライド解法>#28433511 (527 ms)。■自分は雰囲気で文字を読んでいる。2nd largest だとか for the first time in 10 years だとか K-th max だなんてのは罠なんだ。maximum value より大きい値が K-1 個もあるだなんて詐欺なんだ(K-1 個は小さい方にありそうな「雰囲気」がしない？)。中途半端な値は見ようによって大きい値でもあるし小さい値でもある。自分に言わせればそれは単に「大きい方から K 番目の値」なんであって、大きい値でも小さい値でもない。はい、愚痴でした。何回も水色に上がれるなんてお得だね(果たして次はあるのか？)。

ツッコミを入れる

2022年01月07日 (金) [BOOX Max2] ３年ちょっと前に購入した BOOX Max2。先週あたりにバッテリーの具合が急変して、たいへんよろしくない。どういう状態か。満充電から 70-80 % まで順当に使用していたと思ったら、次の瞬間に残量が 15% を切ったときの警告音が鳴る。その後数分で電源が落ちる。その落ち方も異常だ。これまでならバッテリーが尽きるまで使用を続けていると、電源が切れると同時に画面にはバッテリーマークが表示されていた。落ちるときにも最後に画面を書き換えるだけの余力を残していた。それが最近の数回はページめくりの途中で、乱れた画面を残してボタン操作への反応を喪失してしまう。電源ボタン長押しも効かない。画面の異常さからフリーズしたのかとあせるけど、電源につなげば無事に再起動する。だけどほんの５分10分前にはまだバッテリー残量は半分以上残っていたのだし、満充電から半日も使用していないのだからバッテリー警告は何かの間違いだと思っていた。バッテリー容量が７割方どこかへ消失したかのようだ。それも徐々に劣化して、というのではなく。リチウムイオン電池は寒さで見かけの容量が減る(暖めると回復する)けど、氷点下でも屋外でもないのだよ。過放電で不可逆的に劣化するというけど、残り数％まで使ってはいけなかったのか(15％で警告が出てから、キリがいいところまでは読みたいじゃない)。充電の進捗もおかしい。ケーブルをつなげば残量が10数％あって、30分程度かけても 2-3％しか増えない。今後は常時ひも付きで使うしかないのかなあ。ちょっと不便。■こういうことをしている人がいたよ。「2021年9月 BOOX MAX2をバッテリー交換して使っています。 | きょうは毒きのこ日和です - 楽天ブログ」「なす漬: ONIX Boox max2 Battery repair (DIY)」■ちなみに 10 年ちょっと前に買った Sony Reader (PRS-650) とは使い分けていて、そちらは外出＆風呂用にしている。バッテリーの持ちは悪くなってるけど数日は使えるし、毎週のように充電している(要するに毎週ではない。５、６日に１回かな)。バッテリーの具合は知らんけど、予備機も確保してある(そんで思い出した頃に充電している)。

ツッコミを入れる

2021年12月24日 (金) [AtCoder] PAST の支払いチャレンジ。支払い方法の案内がなくて実際に手続きを進めるしか知る方法がなかった。以前は途中で引き返したけど今日は atcoder.jp のログインパスワードを引っ張り出してきてもう少し先へ進んだ。(オンラインサービスが採用する第一の選択肢だと思ってる)クレジットカードだけなんだろうと半ばあきらめていたのだけどインターネットバンキングにも対応していた(「銀行決済取り扱い可能な金融機関一覧(2020年2月現在)」)。一覧に利用している銀行名があったので進んだのだけど、そういえばインターネットバンキングの利用開始手続きは５年前に断念したっきりだった。「インターネットバンキングを申し込もうとして、利用規定と個人情報の取り扱いについての PDF 2つを流し読みして、読みました同意しますとチェックを入れたのだが、タイムアウトで次のページへ移行できなかった。読んでないことをチェックするためにタイムアウトが存在している」。クレカを(AtCoder のために)持つよりインターネットバンキングを利用する方がハードルが低いけど、どうだろうなあ。OS が古いとかブラウザが古いとかで弾かれそうなイメージがある。OS を Windows 10 にするとか変なプログラムをインストールするとかは考えられないよ。とりあえず次は利用開始手続きに再挑戦するところから。

ツッコミを入れる

2021年12月23日 (木) 今期は運命ちゃん(コゼット)が可愛かった。何も知らんかったけどたまたま目に入った１話目で惚れたよね。まずはキャラデザの勝利。それからキャラクター造形とシナリオの勝利。大勝利。良かった。タイタンいい子。

ツッコミを入れる

2021年12月22日 (水) [AtCoder] 精進。ABC003-D「AtCoder社の冬」(ギリギリ黄 diff)。難しいというか、場合分けが面倒くさい。あるいはうまい考え方があるのかもしれないけど。Project Euler の 72 問目(20110315p01)に出てきたオイラーの φ 関数が関係するような気がするけど、四辺の組み合わせを考えるだけなので全部ベタ書きした。提出 #28054417 (AC / 463 Byte / 64 ms)。あっ、関係するのは「「ポリアの数え上げ定理」や「バーンサイドの(ではない)補題」といった異次元キーワード」かも。なんか提出スクリプト(#24021051)でやってる足し引きの雰囲気が似てる(←ふわっふわですよ)。

ツッコミを入れる

2021年12月21日 (火) [AtCoder] 改行を詰めるだけのボットに Shortest を７つほど取られてしまった。残り３つ。■メーリングリストやら GitHub コメントやらコミットログに機械の活動報告が流れてくると、人間の活動は必ず数で圧倒されてしまうので良くないと俺は思う。そういうログは人間が読むものではなくなって人を遠ざけてしまう。

ツッコミを入れる

2021年12月19日 (日) [AtCoder] 今日は M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232) があった。ABC で ABC の三完を嘆いていたのが先々月のこと>20211010p01。今日はついに C 問題が解けなかった>提出 #28000177 (WA / 341 Byte)。B 問題でも WA を出した>提出 #27988292 (WA)。もう終わりだよ。脳細胞が死滅し尽くしている。■(C 問題が)解けた！ 提出 #28019725 (AC / 341 Byte)。特に嬉しくはない。■E 問題は「Rook Path」だった。前日に Queen の問題を解いていたのは不思議な偶然>20211218。当然のこと Queen の解法が最初に頭に浮かんだけど、それは使えなかった。それもまた当然。提出 #28011903 (AC / 286 Byte / 523 ms)。この形の DP は「自分が DP を知らなかった昔に DP と知らずに書いたのと同じ形」だから一番なじみがある。行列累乗で高速化することまでは考えが及びませんが>#28012377 (63 ms でありつつほぼ同時刻の提出！)。

ツッコミを入れる

2021年12月18日 (土) [AtCoder] 精進。ABC183-E「Queen on Grid」(水 diff)。400 万マスのグリッド問題。グリッド全体を一度だけスキャンして答えを出さなければいけない。現在のマスにあるクイーンが移動できる先のマスを処理対象にすることはできない。現在のマスに移動してくることができるクイーンの移動経路の数が知りたい。コンテストの最中と直後は、一歩右と一歩下と一歩右下を操作対象にして累積的な効果を持たせることを考えていて、できなかった。今日は ABC224-E「Integers on Grid」を解いたときの記憶があったので(20211023p01.02)、どういう記録をつければいいのかすぐにわかった。提出 #27972471 (AC / 292 Byte / 723 ms)。わかるときとわからないときの差がわからない。論理で舗装した必然の道を敷くことができないんだろうなあとは思う。ひらめき待ち。

ツッコミを入れる

2021年12月17日 (金) もはや何チャンネルなのかわからんところの「ミニマップを表示すると、Backspaceで文字を連続で削除するのが超絶遅くなるけど、仕様？ 使いものにならない…」に対する答え。書き込めなかったのでここに。「たぶん３種類くらい遅さがあって 1. バックスペースをカーソル左移動と Delete の２操作に分解して実行しているがゆえにアンドゥ履歴が２倍記録されて遅い。 2. ミニマップを表示してると文書サイズに比例して改行の入力/削除が遅い。 3. 文書末([EOF]マークがある位置)での文字入力/削除がなぜかひときわ遅い。さてどれでしょう」 2 と 3 は同根かもしれないのと、実際のところ 1 とミニマップの繋がりは(現象としては確認できても)まったく明らかではないしよくわかんない。■■■なんかアンドゥに関係してかしないでか(ミニマップを含む)全ビューの再描画が無駄に行われていたらしかった。「BSキーでカーソル前を削除時に画面が余計に再描画される事を防ぐ by beru · Pull Request #1754 · sakura-editor/sakura」 m_nOpeBlkRedawCount って初めて見るけどどういう役割なのかな。結局行き着くところはミニマップの構造的・原理的問題だよね。文書の全体を(たぶん愚直に)描画しているからいろいろと遅い。全体を俯瞰するのがミニマップの用途だと思うけど、俯瞰したいほど大きな文書を扱うのに難がある。LOD (Level of Detail) が必要？

ツッコミを入れる

2021年12月16日 (木) [AtCoder] JOI 2021/2022 二次予選 過去問から精進２問。■C 問題「国土分割 (Land Division)」。すること自体は難しくない。目指すべき状態を作ることも判定することも簡単にできる。だから仕切り方を全探索して数えるのは簡単にできるはず。それでは時間が足りないから効率がいいように手続きを組み立てるわけだけど、実装するのにすごく迷った。関数を抽出して処理がまとめられそうでまとめられなくて、でもやっぱりまとめたくてできなくて。提出 #27909751 (100 点 / 566 Byte / 69 ms)。結局抽出できたのは I 関数のみで、メインの処理は似た構造を重ねた二重ループのままになった。■E 問題「交易計画 (Trade Plan)」。制約上限が頂点数、辺数、クエリ数すべてで 40 万なので、判定はほぼ定数時間で行わなければいけない。UnionFind をうまく使うだけ。提出 #27932262 (100 点 / 727 Byte / 2581 ms)。もちろん一度は間違えた>WA。最初からうまくはできない。■飛ばされた D 問題「飴 2 (Candies 2)」。解けないんだよなあ。DP で間違いないと思うんだけど。単体の数と２数の和の２種類の数があって、２数の和から単体の数(と見なせる状態)への遷移があって、そういうのを整理しながら数列をスキャンしていって最大値を答えるんだと思うんだけど、答えにたどりつかない。

ツッコミを入れる
最近
Generated by tDiary version 2.3.3.20091124
Powered by Ruby version 2.5.9-p229