/ 最近 .rdf 追記 設定 本棚

脳log[2020-09-14~]



2020年09月14日 (月) 「見えないものは存在しない」についての面白い比較。■「「見えないものはない」についての考察 | 村中直人の雑記帳」「「見えないものはない」についての考察②ASDとADHDの比較 | 村中直人の雑記帳」■自分の場合。人間とはそのように振る舞うものだという学習の結果としてこの言葉を使っている>20200811。人間を代表する主要なサンプルはもちろん自分自身なんだけど、対象を広くとれば、隠せば見つけられなくなる人がいる、という当たり前のこととして言っている。■注意力と意識とリマインダの話。■たとえば、手が3本必要な状況が発生したとして、片方の手に持っている物を手近な椅子に置くとする。まず間違いなくそれはそのまま置きっぱなしで忘れられてしまう。そういう自分自身との付き合いももうたいがい長いので、今では手を離そうとした瞬間に「あ、これ忘れるやつだ」と気がついて持ち直したり、忘れても大丈夫なように面倒でも定位置に置いて手を空けるようにする(手に持っていた鍵がないとあとで気がついても、鍵の置き場所を探せば見つかる)。常に一部の注意を残しておくような器用なことができない。■たとえば、出かけるときに「あれ買ってきて」と頼まれるとする。必ず紙に書くなどして目に触れるようにしなければ忘れる。必ず忘れる。頼まれたという事実も、何を頼まれたのかも覚えられるけど、帰るまでにやらなければいけない頼まれ事がある、ということが意識に上らない。で、紙に書いた用事をフロントガラスの内側に置いたりします。嫌でも目に入るだろうという考えで。ときどきはその紙に注意が向かないまままっすぐ帰ってきたりするんだけど、不可抗力だからしかたないよね。■「見えないものは存在しないし、目の前にあるからといって見えているとは限らない」■そんなんだからミスの原因は注意力の欠如ではなく必ずシステムや構造、手続きの中に求める。注意をしていれば、ぼんやりしていなければミスをしないはずだ、なんて考えることはできない。それは注意していなければミスをするということだし、自分は必ずミスをするということだから。■これってクリティカルな場面では普通の考えで、プレス機を動かすのに両手が必要とか、(最近では蔑ろにされてるみたいだけど)給油口を開けるのにエンジンキーが必要とか。どんな人間でもバイオリズムの変動はあるわけで、なまじ身体能力が高くて普段苦にしないより常にこういう考えができる方が役に立つと思う(両方持てる人が一番だけど!)。


2020年09月12日 (土)

最終更新: 2020-10-09T18:36+0900

[AtCoder] AtCoder Beginner Contest 128E 問題 Roadwork

精進ですよ。今日*こういうものを読んだ。

【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita

この前の日記(20200907p01)で散々 TLE に苦しめられた問題も、C++ なら変数 r を map に、変数 nmin を multiset にすることで、ある範囲のキーを二分探索で検索することも、小さい方からキーを取り出すことも、STL 任せで妥当な時間で行える。適当に速くて短い提出を選んだけどこんな感じ>「提出 #16578878」。トリックは必要ない。

Qiita の記事で題材にされているのが今日の E 問題 Roadwork で、記事をよく理解するためにまず解きたいと思った。

 提出 #16613595 (TLE×1 / AC×14)

とってもくやしい。

最悪の場合に 200k 要素の配列に 200k 回書き込みを行うのが良くないのかなと思う。掛けて 40G×単位サイズの書き込み量。あ、これはやべーわ。

遅延更新と区間更新が可能なセグメントツリーがあればこのアホな書き込み量はなんとかなる気がするなあ。

 提出 #16618964 (AC / 721 ms)

ループの中でがっつり二分探索して配列のスプライシングをしても通るあたり、この前の F 問題(前掲)より易しい。

二分探索がしたい、線形よりましな時間で挿入がしたい、というときに平衡二分探索木が欲しくなるんだよね。

プライオリティキューを実装するときも、最大(最小)値を得るだけでなく、整列済みのキューにアクセスして操作したいときがある。でも内部構造がヒープだからできない。std::multiset とは違う。

2本目のキューに削除済みとマークした要素を入れておくの頭いい(Qiita の記事)。二分探索はできないけど、一度放り込んだ値を後から取り消したいときが、たしかに以前あった。

 Ruby によるすべての提出 (実行時間昇順)

Ruby のバージョンが違うので一概に比較できないけど、他の AC はどれもヒープを使用していて 1000 ms 以上かかっているところが共通している。配列のスプライスよりヒープの方が賢いよね。

でもスクリプトで手の込んだことをするよりインタープリタに丸投げした方が速いこともある。Python は汎用スクリプト言語でありながらそういうバッチファイル的、グルー言語的なあり方も板についている。

たとえば、ダイクストラ法、ワーシャルフロイド法などのアルゴリズムが名前で利用できる。ヒープ構造もある。二分探索も、比較式をブロックで与えられる汎用性が Ruby にはあるが、それが遅さに繋がってしまう。実は lower_bound, upper_bound だけでほぼ足りる。オブジェクトの形が不定だとしても、key 配列と value 配列を持てば解決する。

Ruby に範囲を指定する Array#fill があるのを、しかも古くからあるのを知ったときは嬉しかったし、同時に自分の不明も明らかになった。Ruby は汎用スクリプト言語だからループやイテレータを使って Array#fill 相当の処理は自在に書ける。書いてきた。でも書かずに fill を1回だけ呼び出すのが賢い(が、実は Ruby で実装されています、という可能性もなくはない)。

* 日記を書いている今日は10日。


2020年09月11日 (金) 【※更新】書籍「タクティカルRPGのAI技術入門」が発売決定。『ファイナルファンタジータクティクス』の開発に携わったスタッフが、シミュレーションRPGの敵AI思考ルーチンを解説」■FFT もベイグラントストーリーも大好きなんだよなあ。更新で(個人誌としての)販売中止が案内されてるけど、出版社から発売されると信じてる。


2020年09月10日 (木) ドコモ口座の件。どうやら他人事ではない。ドコモとは関わりがないが、狙われた地銀に口座がある。■「Web口振受付サービス」というのがデフォルトで有効になっていて、手続きを「パソコンや携帯電話でご利用可能な収納機関のホームページより行います。(当行ホームページからはお申込手続きを行うことができません)」「お申込みの際に、口座番号・口座名義・生年月日およびキャッシュカードの暗証番号等が必要」で、「本サービスの利用をご希望されないお客さまは、ATMから口座振替受付サービスの利用停止登録にて本サービスの利用停止登録ができます。」 利用停止するまで秘密情報と言えるのが4桁の暗証番号だけという守りの緩さで、「ご利用可能な収納機関(2020年7月1日現在)※収納機関は順次拡大予定です」に対して過度の信用を付与した状況にあるということだ。その信頼は銀行のものであって俺のものではない。勝手にばらまかないでほしい。■銀行がこれなら au のやり方も当然か>20190122。どっちも願い下げ。そしてドコモ。俺は関わりがないのに存在するだけで有害。資格がないから銀行とは手を切れ。契約者が口座振替で電話代を払えなくなっても俺は関係ない。■デビットカードが関係するらしい。「利用停止登録をされますと、本サービスとデビットカードの利用を停止します。」 最近 Visa タッチについて調べたけど、この銀行のカードは NFC に対応してない雰囲気だったし、グーグルアカウントなしで Google Pay が使える気もしないので、いらないサービスですね。そんなんで被害に遭いたくねーぞ。■去年携帯電話の回線を au から mineo に替えたので kddi に認めていた口座振替を止めたいと思った。銀行の窓口に問い合わせたのだけど、まあまあ話が通じなかった。よくある話ではないのかも。最終的に用紙はもらえたけど、埋めるの難しそうだった(事務能力ゼロの感想)。■「Web口振受付と即時口振に頼らなければならない新型決済スキームの問題 - novtanの日常」 今は適切な API が整備されていないがゆえの口座振替の乱用状態にあるといっていいのかも。■ドコモのプレスリリースで eKYC をこれから導入するというのがあって、なんぞやと検索してみた。とっても面倒なオンラインでの本人確認手続きらしい。ここでマイナンバーカードに埋め込まれた個人の電子証明書と PIN で本人確認が完了すると、とっても便利なんだけどなあ。無理に5000円くれなくてもカードを作りたくなるんだけどなあ(カードの発行者にこれ以上できることが限られるのはわかる)。マイナンバーカードよりむしろ IC を内蔵したキャッシュカードが利用できるべきなのか。確認したいのは口座の持ち主であることなのだから。■@2020-09-11 今日 KDDI の口座振替を止めてきた。やっぱり窓口でスムーズに進まない。そんなにおかしなことだろうか。電話代を払うために口座振替を申し込む。他所の回線に移ったので口座振替を終了する。普通じゃない? なぜ解除するのか理由を聞かなければいけないのだと窓口の人が言っていた。そんなにか? 用紙は前々から準備していたが提出のきっかけはドコモ口座だよ。説明が早くてけっこう。それと肝心の口座振替受付サービスを ATM で止めてきた。必要のないポートは閉じるべし。■ところで、まだ、ドコモ口座の害悪は拭えていない。KDDI は自分が口座振替の手続きをして、そして今日解除したわけだけど、実はこの口座が現在ドコモと結びついていないとも限らないわけだ。今日 ATM で停止するまで「Web口振受付サービス」が有効だったから。何か月ぶり何年ぶりに記帳してこれまでに不正な出金がなかったことは確認したけど、今後ないとも限らない。だから、後顧の憂いを断つためにドコモを締め出してほしい。銀行に間違いがあって、修正の必要があるのだとしたら、その手段のひとつがこれだ。俺はそれで問題ない。


2020年09月09日 (水) Androidの「電話」アプリに顧客が安心して応答できる企業向けサービス開始 - ITmedia NEWS」■企業向けって言うけど、俺は、そんなサービスに巻き込まれたくないぞ、と思った。グーグルがどこにお墨付きを与えるのかに興味がない。「この機能を使うには、リクエストが必要だ。日本ではまだサービスを提供していないが、リクエストは可能になっている。」 リクエストの主体はたぶん電話アプリのユーザー。こういうところきっちりしてるのいいと思います。


2020年09月08日 (火) 7年目の枕がリフレッシュした。9.0L×2 を使い切ったぜ。目減りしてたかさと香りが元通り。


2020年09月07日 (月)

最終更新: 2021-03-12T19:59+0900

[AtCoder] AtCoder Beginner Contest 177F 問題 I hate Shortest Path Problem

まだ AC してない。(←その後 AC)

 8日3時 提出 #16567031 (TLE×3 / AC×8)

前回の日記(20200905p01)で解いた問題と構造は同じ。一番大きな違いはグリッドの大きさで、こちらは制約上の上限が 200000×200000 だから1マスずつの処理では間に合わない。

そこは何とかなって今は上限20万回のループの中で、上限20万要素からの二分探索が2回と、上限20万要素からの最小値検索を1回行っている。配列からの最小値検索が線形時間なのが明らかにまずいんだよなあ。実はループの中で配列のスプライシングをやってるのもまずくて、まずいのが2つ組み合わさって手がつけられないんだなあ。

 8日23時 提出 #16582545 (TLE×1 / AC×10)

問題のイメージが掴めてきた(今です)。H 枚の板が上から順にやや右下がりで設置されていて、最上段では横一列に並んだ W 個の蛇口から水が流れている。k 段目で注目すべきは水が落下している位置(複数)と、そこに流れ込む水流のうち落下点に最も近い蛇口がどれか。蛇口と落下点を結ぶ線はどれも交わらない。

蛇口と落下点の距離が最小となるものを効率的に見つけるデータ構造がわからんのだよなあ。

あ、TLE が2つ減ったのは nmin, rmin の導入効果。「蛇口と落下点の距離」ごとに数を数えておいて、数がゼロではない距離を小さい順に検索する。距離は増加する一方だから検索範囲は狭まっていく。

 9日0時 提出 #16584229 (AC / 456 ms) やったぜ!

今回のポイントは r を可変長から固定長にしたこと。可変長のときの r のサイズは W から減っていく一方だったのだけど、固定長だと最初から最後まで W(+1)。それでどうして速くなるのか。

r の中身について。これまでは落下点と落下点までの横移動コストを記録していた。今回は落下点は(固定長)配列の添字となり、配列の中身に蛇口の位置を記録した。落下点までの移動コストは計算で求まる。

ここでトリック。落下点と蛇口の位置関係は「蛇口<=落下点」で決まってるので、「添字<中身」の場合を、落下点を見落とさずに配列のスキャンを安全にスキップするための情報とした。

Ruby で提出してると AtCoder Problems で確認できる Shortest Code の数がいつの間にか増えている現象がある。この提出が(いまのところ)そうだし、巨大企業(20200607p01)もそう。

 Ruby によるすべての提出

AC 一番乗りである。C++ は甘え。まあ、Python は普通に AC がいくつもあるんだけど>「Python によるすべての提出

 提出 #16590103 (AC / 453 ms)

  1. コメントをプラスして、
  2. ちょっとだけ余分にスキップするようにして、
  3. ありえないケース(すでにある落水点の最近蛇口更新)に対応したコードを省いたが、

見事なまでに変わらず。スキップ情報を UnionFind と同じように深さ優先探索で貪欲に求めて書き込むようにしても、やっぱり変わらないだろうなと思ってる。


2020年09月05日 (土)

最終更新: 2020-12-01T21:25+0900

[AtCoder] AtCoder Beginner Contest 175E 問題 Picking Goods

今週は ABC がないようなので精進である。D 問題が「コンテスト時間中には解けなかった」ので E 問題は問題文を読みさえしなかった。

 提出 #16526116 (AC / 1195 ms)

一行ずつ左から処理するにあたり保持するデータを vs = [0]*4 と定めたあとは、特に詰まるところはなかった。つまりそこで詰まったということであり、一番のお楽しみポイントだったということ。あるマスにおける状態と、状態から状態への遷移が、4要素の配列でまかなえることの発見が。

 Ruby によるすべての提出

今のところ2番目の提出より倍くらい速いみたい。だけど書き方による違いかもしれないね。

 (飛び道具*なしの) Python で一番速い 提出 #16010823 (ikatakos さん / 357 ms)

この人の名前は AtCoder を初めて日記に書いた 20190907 のこの部分(20190907p01.05)で初めて目にした。このときも Python で一、二を争うくらい速くて、同じくらい速い他の複数の提出から参考にしたと参照されていた。

参考にできるところがあるだろうか。

自分のスクリプトで気になっているのが r0[c] = vs.max と書いた部分で、長さ 4 の vs 配列のうち 1,2,3 番目は基本的に昇順ソート済みなのだけど、0 番目にイレギュラーが飛び込んでくるせいで vs[3] や vs[-1] とは書けずに vs.max と(4要素とはいえ)配列を走査するほかなくなっている。

up = dp[i - 1][j][3]
for w in range(4):
   dp[i][j][w] = max(dp[i][j - 1][w], up)

上のように、隣の行から値を引っぱってくるときに最大4要素を更新すればすべてソート済みであるとして末尾の要素を最大値として取り出すことができるんだけど……

 遅くなったよ! 提出 #16526544 (AC / 1480 ms)

もうわからぬ。

 kuma_rb さんの2つの提出

違いは入力 RCV を配列に記録するかハッシュテーブルに記録するかだけ。速くてメモリ食いが配列。遅い方がハッシュテーブル。要素数が少ないときはメモリ食いなのもハッシュテーブルの方なのであって、(メモリと GC が気にならない限り)いつでも配列を使っていきたいんだけど、この問題について言えば、R×C に比べて K がかなり少ないみたい。制約が「1 ≤ K ≤ min(2×10^5, R×C)」だから、最悪の場合が 900 万になるか 20 万になるかという違い。

ところで、いくつか見た感想なんだけど、作業配列は C+4 要素で十分だと思うんですよ。C×4 でも C×4×2 でもなく。入力を記録する R×C サイズの配列の前では霞んでしまう違いだけども、numpy の場合のパフォーマンス特性はわからないけども、要素の更新量は確実に減る。

 提出 #16528314 (AC / 934 ms / 36832 KB)

Python で一番速い提出 #16084621 を読んだ。コンパイル済みのバイナリを書き出して実行するなら Python である理由がないじゃん、と思ったんだけど、元になった Python のソースをちゃんと読めるようにしてくれている。コンパイル前のソースが Python なのだった。

長さ C の作業配列が昇順ソート済みだという特性が活用できていなかったことがわかったので、それを踏まえたコードに。あまり速くはならず。結局 R×C 回配列を更新するところは変わりがないから。

 提出 #16528556 (AC / 1813 ms / 188724 KB)

配列を昇順ソート済みにするための書き込みを省いて、配列の重複のない範囲から最大値を抽出するだけにすれば良くなると思った。倍遅くなってメモリ消費も激増した。むしろ逆で、予想外のメモリ消費がスローダウンを招いた? Array#[] か Array#max に何かある?

 提出 #16528834 (AC / 1038 ms / 46636 KB)

vs[0] = [vs[0],r0[c0..c].max].max

# r0 に関わらない処理

r0[c] = vs.max

だったものを

vs[0] = [vs[0],r0[(c0..c).max_by{|i|r0[i]}]].max

# r0 に関わらない処理

r0[c] = vs.max

に書き換えたところ、1つ前の異常なメモリ消費、異常な実行時間だったものが、2つ前よりメモリも時間もやや悪いという、予想の範囲内の結果に収まった。

いや、悪くなってるのはがっかりなんだけど、1つ前の悪くなり方はやはり尋常じゃなかった。配列に最大値を聞くのではなく、添字の範囲を使って配列の最大値を求めるという回りくどいやり方より遙かに遅かったのだから。

素直なやり方で予測可能な結果が出るなら速かったりしないかなあ。

 提出 #16543158 (AC / 727 ms / 37188 KB)

困ったときのセグメントツリー。もう3回目の実装なので空で書いてバグも無し(でも一応内部データを目視するテストはした)(1回目と2回目は空で書いてバグだらけ)。メモリ参照の局所性なんて関係ないハードウェアから遠い言語でできる悪あがき。今のところのベスト。こんな作業ってアルゴリズムひとつで桁違いの差をつけて置いて行かれる類のものだ。楽しくはあるけどこれで終わり。

@l の利用場所すべてで @l+1 って書いてるから @l の定義から -1 を削っておけば良かった。

* コンパイル済みのバイナリ展開とか。


2020年08月27日 (木) 大阪・関西万博ロゴマークが「なんかこわい」とネットざわつく 発表後即「コロシテ」がトレンド入りする事態 (1/2) - ねとらぼ」■【速報】大阪万博ロゴ決定 ナイスデザインと話題に : 暇人\(^o^)/速報 - ライブドアブログ■「いのちの輝き - Bing News」■「キーワード検索 - コロシテ」■「触手を振り回す未知の怪物となって暴れるホラーメトロイドヴァニア『CARRION』レビュー」■すごく「らしくて」いいと思う。大阪だからね。不気味ちゃうで愛嬌やで。


2020年08月26日 (水) [Ruby] 当然あるだろうと、先にタイプしてから存在を確認するメソッドに Numeric#sign がある。ところが 2.7 にもないのである。zero?, nonzero?, positive?, negative? は存在している。でも -1,0,+1 のいずれかを返す sign メソッドはないのである。レシーバが -0.0,+0.0 の場合に何を返すべきかはすぐにはわからないけど、-1.0,+1.0 を返すのは罠になりそうなのでレシーバ自身が無難だろう。■「sign メソッド」で検索したらトップに出た>「Math.Sign メソッド (System) | Microsoft Docs」。ほらほら。■■■わかったぞ。i <=> 0 で代用できる。メソッドであってほしいものと演算子で十分なものと、なんかちぐはぐだね。■<=> (Spaceship Operator) についてビャーネさんが何か言いたそうにしていたのをどこかで読んだ。Ruby での存在意義はこの1メソッドを定義するだけでクラスを Comparable にできることだと認めてはいる。でも C++ では何を追加しても、互換性を保って追加をする限り、煩雑さを増すことにしかならないだろう。■Uniform Function Call が一番楽しみだな、C++ に導入されるとしたら。シンタックスの統一はテンプレートの適用を拡大するし、メンバ変数を使用しないアクセサリメソッドをグルーピングのためだけにメンバ関数にするような暴挙を阻止できる。

最終更新: 2021-10-24T17:45+0900

[AtCoder] 第二回全国統一プログラミング王決定戦予選 - AtCoderC 問題 - Swaps ()

読んだ眺めた>「競プロerのための群論 (swapと順列と対称群) - little star's memory

数学の用語で何か抽象的なことを言ってるなーということと、Swaps と Moving Piece の2問(だけじゃないけど)が取り上げられているということはわかった。

Moving Piece は先日解いたので(20200820p01)、以前解けなかった(20191111p01) Swaps も解ける気がした。

 提出 #16248329 (AC / 403 Byte / 283 ms)

もちろん今日も AC に至るまでに WA を出した。それも前回と全く同じ入力に対して同じように誤った答えを出した。前回書いたスクリプトはひとつも参考にしなかったにも関わらず、構成も結果も瓜二つなのは、書いた人間が同じだからですね。同じところに留まっている……。

 デバッグ

前回と違ったのはテストケースが利用できたこと>「atcoder_testcases > nikkeiqual_2019 > C

今回のような Yes/No 問題の場合、間違った方法ででたらめな答えが出ても2分の1の確率で AC になってしまいデバッグが捗らない。そのような場合に(テストケースなしでも)使える手法をひとつ思い付いた。

 提出 #16245274 (TLE)

スクリプトの真ん中に sleep (※引数なしなら永眠)を仕込んで、前半部分の Yes/No 判断に誤りがないかを確かめた。結果は TLE と AC のみだったので、前半部の判断は間違っていない。

 提出 #16245473 (WA)

予想外の WA (TLE なし)だった。これは後半部の No を sleep に置き換えたものなのだけど、1つも TLE がなかった。1つもないというのは(入力とバグり方がコラボした)偶然の結果なのだけど、偶然でもなんでも無条件 Yes は明らかなバグだ。

こんな感じで TLE(sleep) や RE(ヌルポ、0除算、変数名タイポ)が Yes/No ではない第3、第4の答えとしてデバッグに利用できると思った。こういう(アナーキーな)考え方ってゴルファーが得意としてそうだよね。常識だと思ってそう(違うんですよ)。

 バグ

わかってみれば些細なことで、思えば去年もインデックスの扱いに確信が持てずに試行錯誤をしていた。どうして B 数列が予めソート済みではないという、そのひと手間で穴にはまるのか、何度でも。

つまり、A 数列の初期配列と B 数列の初期配列。A 数列のソート済み配列と B 数列のソート済み配列。A, B 両者の扱いが対等なこれら4つは脳みその中に居場所が確保されていた。しかし、B 数列の初期配列をソート済みとする、と条件を整えたときに A 数列の初期配列がどうなるか(ソート済みではないし、元の初期配列とも異なる)、という概念が脳みそからすっぽり抜け落ちていた。A, B の対称部分に気持ちを良くして、差異に向ける目がなかった。去年も、今回も(初めは)。

 去年の借りを返す 提出 #16278383 (AC / 445 Byte / 199 ms)

「去年の WA」を完成させたもの。必要以上に慎重だった(見極めが甘く無駄だった)二分探索がないぶん、冒頭の AC 提出より速い。

 考察(おまけ)

前回の日記に全部書いてある(あれで全部だった)。ひとつだけ付け加えるなら、「逆の例は、B 数列に重複する値が存在する場合や、B 数列の最小要素以下の要素が A 数列に複数ある場合など」の「など」でごまかした具体例の3つ目。

ソート済みの B 数列に異なる値を持つ隣接要素 B[i] と B[i+1] があって、B[i] < A[k] <= B[i+1] となる A[k] が存在しないときも、A 数列のすべての要素にあるべき位置が存在するとは言えなくなる。(A 数列がソート済みなら B[i] < A[i+1] を確かめるだけでいい)

最終更新: 2021-08-15T23:54+0900

[AtCoder] 第二回全国統一プログラミング王決定戦予選 - AtCoderD 問題 Shortest Path on a Line

余勢を駆って前回2つの WA であっさり引き下がっていた D 問題に再挑戦した。これも C 問題と同じ 600 点問題。

 提出 #16254983 (AC / 387 Byte / 402 ms)

実は区間の片端に着目した貪欲法で解けるんですよ、というのが目から鱗だったスケジューリング問題そのままだった。どこにそう書いてあったかは忘れた*

前回の WA 提出 #8424473 を見ると、今と同じことは考えていたことがわかる。C 問題の場合にも言えるけど、そこで結果を分けたものが何か。考えたことを過不足なく言い換えることと、バグなくコードに置き換えること。それができるかどうか。

それはどうやったらできるようになるんですか? という問いは、どうしてそこで間違えたんですか? という問いと対になる。わかりませんよ。ワーキングメモリが足りないんじゃね?(テキトー) こういうとき脳筋は手を動かして慣れるしかない。そうすればより少ない脳のリソースで解けるようになったり、型通りの手法で解けるようになったりして、うっかりや見落としで間違えることがなくなる(という期待)。

 去年の借りを返す 提出 #16288240 (AC / 319 Byte / 375 ms)

区間のどちら端に着目するか。冒頭の AC 提出では L のソート順に処理していたが、「前回の WA」では R でソートしていた。それを完成させてみたら、冒頭の AC 提出で使用していた Array#slice! と Array#insert という、配列に対して呼び出すにはやや気が引けるメソッドが、Array#pop と Array#push という配列に相応しいメソッドに置き換わっていた。二分探索も3回から2回に減っている。Swaps の場合もそうだったけど、AC に至りさえするなら部分的には過去の方が優れてるのなんでだろう。

 解説記事を読んでもわからないので自分で書く。

グラフとか最短経路とかコスト0の辺を張るとかわからへんねん。

R でソートするバージョン(#p02.02)。

  1. RC を、ある地点(R)に到達する最低コスト(C)を記録したリストとする。R が同じならコストの低い方を記録する。R についても C についても昇順(2要素の比較において R が大きければ C も大きい)。リストは最初空で、R の昇順に伸長していくこととする。
  2. 区間 [L,R] から R までをコスト C で繋ぐ場合を考える。
    1. RC を二分探索し、最初に L かそれより後ろに到達する要素を見つける。より遠くに到達する要素はより高コストなので「最初」を見つける。

      見つからない場合は断絶があるということでありパスする。R の昇順に RC に要素を追加しているのであり、今後 [L,R) の区間に到達する辺は現れない。R に到達する辺があとから追加されることはあるが、C が負ではないのでパスで良い。

    2. 見つけた要素のコストを加算して C′とする。辺を追加することによりコスト C′で R に到達できることになる(始点は問わない)。
    3. RC に記録されている C′より高コストの要素は用済みであり取り除く(RC がコストの昇順であることを利用する)。処理時点で R が最遠到達地点であり、それより近くに高コストで到達することに価値がないから。
    4. ペア [R,C′] に記録する価値があるなら RC の末尾に追加する。
  3. ということの繰り返し。

ひょっとしたらこれも DP (動的計画法) の一種かもしれないけど、わからんけど、自分が頑なに DP の用語を使わないのは、それを言ってもメリットがないから。

一行ずつ左から処理するにあたり保持するデータを vs = [0]*4 と定めたあとは、特に詰まるところはなかった。つまりそこで詰まったということであり、一番のお楽しみポイントだったということ。あるマスにおける状態と、状態から状態への遷移が、4要素の配列でまかなえることの発見が。

これもそう。DP の核心は何を記録して遷移するかであり、それがわからないのに、「あ、これ DP だ」ということを言っても問題が解けない。むしろそれを言うことで何かわかったつもりになることが目眩ましになって問題に集中できない。過去に何度かそういう失敗をして、DP だということは言わないことにした。dp という変数名も自分にとって何も説明していないので使わない。

DP の一語でなく、配る DP、集める DP まで区別できるとまた違うのかもしれないけど、自分はそれらを識別しない。

 @2021-08-15 ARC026-C 蛍光灯 が同じ問題だった。

どちらがどちらと同じと言うかはまあいいや。

 提出 #25085547 (AC / 295 Byte / 269 ms)

速いでそ>「Ruby によるすべての提出」 それ以前に提出が少なすぎる……。

* 蟻本(初版第1刷)の43ページ「区間スケジューリング問題」だった。


2020年08月25日 (火) 【第104回インディ500速報】佐藤琢磨がディクソンの猛追を抑え2017年以来2度目の快挙を達成 | 海外レース他 | autosport web


2020年08月24日 (月) 日本人が間違えやすい英語表現シリーズ」■Congratulations! の s は見れば必ず付いてるよね、バック(bag)とか細かいところをいいかげんにする人を除いて。think の目的語に対応する疑問詞が what なのは中学生のときに(塾で)くどいほど……。「納豆食べられる?」は日本語が文字通りの意味でないせいでわかりにくいのかなと思う。能力的な話をすれば胃ろうをしているような人でなければ食べられるのは間違いのないところで、「食べられる?」が実際に聞いているのが「あなた納豆食べる人?(納豆をお出ししても大丈夫?)」であるあたりが逐語訳を誤らせるのだと思う。「日本の首都はどこ?」はどうだろう。Where's my bag? がありなら Where is the capital of Japan? の答えは「このでっぱり(房総半島)の左(東京湾)に面したこの小さいエリアがそうだよ」になりそうではある(なんの問題が?)。know of の of は何か距離を感じさせるね。話には聞いたことがある、という感じ。still five の誤りはエンドレスエイトを想像させるところにありそう。今5時でさっきも5時だった、みたいな。「still⇔まだ」ではない。still のイメージは静止・停滞だと思ってる。留まり続けていることに対して、まだそこにいるのか、という印象を still で表現することはあっても、すべてのまだが still になるわけではない(と思うんだよ)。only five はちょっと出てこないな(覚えておこう)。


2020年08月23日 (日)

最終更新: 2020-08-26T10:30+0900

[SakuraEditor] 上書き禁止と排他制御と編集禁止

 CDocLocker とは

ある時点でのファイルへの書き込みアクセスの可否を保存し、エディタの「上書き禁止モード」を体現するクラス。CDocLocker::IsDocWritable が第一義。

  1. 書き込みアクセスができた
  2. CDocLocker.IsDocWritable(); // true
  3. 上書き禁止モードではない

 上書き禁止モードと排他制御

排他制御を行うのに書き込みアクセスは必須ではない。しかし書き込みアクセスができることをエディタは条件にしている。自身が書き込みできないファイルに対して「お前らこのファイルは俺のものだぞ。勝手に読んだり書いたりするなよ」と主張することのナンセンスを考えれば納得できる。

書き込みアクセスがないなら排他制御はやめとこか、くらいの温度感なので、CDocLocker.IsDocWritable() に基づいて判断を下している。今現在の瞬間の書き込みアクセスを条件にしているわけではない。

 上書き禁止モードと編集禁止(※編集禁止は状態としてはビューモードと同じ)

「上書き禁止検出時は編集禁止にする」というオプションによって、上書き禁止モードがより制限の強い編集禁止状態へと格上げされる。

(別のファイルとして保存するために)上書きできなくても編集はしたいという考えも、上書きできないのなら編集できても意味がないという考えもどちらもあるだろう。そこはどちらでもいい。

 上書き不可の検出タイミングについて考えたい

これは CDocLocker.IsDocWritable() の値が変化しうるタイミングと同義。次のようになっている。

  • ファイルを開いたあと
  • ファイルを開き直したあと
  • ファイルを保存したあと
  • 排他オプションの設定(しない/上書きを禁止する/読み書きを禁止する)を変更したとき
  • ビューモードのオンオフを切り替えたとき
  • タイマーで外部からのファイル更新を監視するついで(※)

※ 最後だけは「書込禁止の監視を廃止(復活させるなら「更新の監視」付随ではなく別オプションにしてほしい)」というコメントとともに無効化されている。

上書き禁止モードの変化が排他制御を試みるかどうかと編集禁止モードのオンオフに影響するのはすでに書いた。

  1. 排他オプションを変更したときに上書き可否を改めて検知しているのは理に適っている
  2. 「上書き禁止検出時は編集禁止にする」にチェックを入れたときに上書き禁止モードのオンオフを改めようとしないのは、排他オプションの場合と比較してちぐはぐ。
  1. ファイルを開き直したあとの上書き禁止モード改め時には「すでに編集できない状態ならファイルロックのメッセージを表示しない」という再メッセージ抑制策がとられている。
  2. ビューモードをオフにしたときには、何度でも「ファイルがロックされている(上書きが禁止されている)」というようなメッセージが出る。モードの切り替えとファイルの開き直しを比較して、メッセージ抑制策の有無の分かれ目とは?

2組の比較を挙げたけども、どうにも扱いがちぐはぐで行き当たりばったり感がある。上書き禁止がいつ検知・再検知されるのか、すっきり説明できるようにしたい。

 再検知により上書き禁止モードがオフからオンになることについて

オプションにより編集禁止モードと連動する。ファイルを開いたときに上書き可否を検知し編集が禁止されるのは、ユーザーの選択でもありなんの問題もない。

しかし一度編集を開始したファイルに対して、アンドゥバッファが溜まり更新フラグが立ったファイルに対して、先ほど挙げた再検知タイミングを挟んで、上書き不可が検知され編集が禁止される事態が起こりうる。これはユーザーの望む動作であろうか。いたずらにユーザーの操作を制限しているだけではないのか。

ビューモードをオンオフするタイミング次第でエディタが編集可能になったり不可能になったりするようなことを誰が望んでいるのか。結局のところ編集禁止の根拠となっている上書き禁止モード、つまりは書き込みアクセスができたかどうかは、過去のある時点ではそうだったというだけなのに。

 上書きができないことと上書き禁止モードの差

ファイルの保存をしようとしてその直前のテストで書き込みアクセスが拒否されたところに、こういうコメントがあるのがおもしろい。「たとえ上書き保存の場合でもここでの失敗では書込み禁止へは遷移しない

上書き禁止モードを体現する CDocLocker.IsDocWritable() の値が変化しうるタイミングをいくつかすでに挙げたけども、実際に上書き保存をする直前というタイミングがそのリストから明示的に除外されていることになる。

実際上の理由はわかる。最初の上書き失敗を理由にして2回目以降のトライを勝手に諦めてもらっては困るからだ(上書き禁止モードで上書き保存は選べない)。

上書き禁止モードが何ではないのかがよくわかるコメントではないか。

 ビューモードと上書き禁止モード(と編集モード)の差

  • ビューモードはユーザーがオンオフできるが、上書き禁止モードは自動で発動する。

なお、自動で発動する上書き禁止モードをビューモード相当の制限に格上げすることができる(「上書き禁止は編集禁止」オプション)。

 上書き禁止モードをユーザーがオンオフできてもいいのでは?

上書き禁止モードを仮にユーザーがオフにしたところで、上書きできないときには上書き保存に失敗するだけのことだ。ついさっき挙げた、この失敗から上書き禁止に遷移はしない、というコメントの状況が発生するだけのことだ。

ビューモードほど強い制限でなく、ファイルシステムからの要請でもなく、ユーザーが自分の意思でこのファイルには上書きしないと宣言するモード(上書き禁止モード)があってもいいのでは?

 ビューモードをオフにする行為とは?

派生して、ビューモードをオフにするタイミングで書き込みアクセスの可否を再判定して、上書きモードのオンオフを更新する現在の挙動についても再考する。

上書き禁止モードは結局のところエディタやユーザーの選択の結果でしかない。書き込みアクセスが拒絶されたとて、そうあらねばならないモードではない。

ビューモードのオンオフ、上書き禁止モードのオンオフという操作によりユーザーが3つのモードを自在に行き来する状況を想定すれば、ビューモードのオフは編集モードへの移行であるべきでは?

 上書き禁止は編集禁止、あらため、上書き禁止はビューモード

ファイルを開いた際にユーザーの便宜のために自動で上書き禁止モードやビューモードを適用する機能があっていい。今は何が違うかというと……

  • 上書き禁止モードへの移行を拒否できない。
  • 上書き禁止モードが任意でオフにできない。
  • 「上書き禁止は編集禁止」オプションが文字通りの意味であり、上書き禁止モード(編集は可能)が上書き禁止モード(編集も禁止)によって上書きされている。
  • 上書き可否検出タイミングが場合により不合理(一度テキスト編集を開始したあとで編集を禁止されることになると……)。

 サクラエディタでファイル(テキストファイル等)を開くとファイルの更新日時が変更されてしまいます。

せっかくなので理解した内容を長々書いてきたけどもそちらは本題ではなく、そもそもは標記の現象のための作業をしていた>コード。それで何か嬉しいことができたかというとそういうことはない。現在のステータス……

  • 書き込みアクセスの要求が原因だとは決まっていない。
  • 予備的に書き込みアクセスを要求しないようにコードを修正しても、排他制御の判断と、上書き禁止は編集禁止オプションと、文字列展開のためにはやっぱり必要。
  • 書き込みアクセスを確認する、より穏当な代替手段を探しては?
  • ファイルを保護するというお節介ソフトの挙動をそういうものだと受け入れては?