脳log[2019-11-20～]

2019年11月20日 (水) 本日の新発見(ATOKで変換できなくて知った)。「総花(的)」は、ソウバナ(テキ)と読む。文盲(モンモウ)、出色(シュッショク)、縦中横(タテチュウヨコ)以来の驚き。類としては縦中横と同じなのかな。

ツッコミを入れる

2019年11月18日 (月)

最終更新: 2020-05-06T23:27+0900

♪ [AtCoder] AtCoder Beginner Contest 145／D問題 Knight

階乗が法外な大きさになるので余りを答える問題。割り算を含む式の余りが求められなかった。もちろん階乗を計算しきってから余りを求めるというのは実行制限に引っかかるので無理。

#AtCoder から見つけたヒント

モジューラ逆数っていうのがあるんですね、これはすごい pow(down,mod-2,mod) 昨日のD問題逆元の計算どうやればいいのかわからなくて1時間くらい経ってしまった
ぼのろんさんのツイート 22:42 - 2019年11月16日

AtcoderのABC145D問題しっかり理解して頭の中整理してすっきりかけた気がする。Python3です。 pic.twitter.com/Dcs3IfoZ95
ぼのろんさんのツイート 22:58 - 2019年11月16日

mod って演習込みでイチから習った記憶がない。「割った余りですよ」以上の理解がない。キーワードすら知らなくてググりようがない。

キーワード

「逆元 - Wikipedia」

「モジュラ逆数 - Wikipedia」

「ユークリッドの互除法 - Wikipedia」

「ベズーの等式 - Wikipedia」

Ruby には Python と違って「冪剰余 - Wikipedia」が求められる関数が用意されていないみたいなので(※補足訂正)、拡張ユークリッド互除法を使う方の求め方を Wikipedia(ja) からコピペ実装した>https://atcoder.jp/contests/abc145/submissions/8508807。明日には理解できないとしても「モジュラ逆数」というものの存在くらいは覚えておきたい。

現在 Ruby で最速の提出(55 ms)>提出 #8501110 - AtCoder Beginner Contest 145

速いからには変わったことをしてる。derive_inverse メソッドが理解できない。法のビットを利用しているみたい。理解できないのは本質を掴んでいないから、演繹が働かないからだろう。「冪剰余#さらなる最適化 - Wikipedia」を実装してるのだろうか、雰囲気的に。

pow メソッドを使って実装された derive_inverse がコメントアウトして残されている。

Ruby で冪乗余

試したら Ruby 2.5 には冪乗余が求められる Integer#pow メソッドが用意されていた。2.6 の「数値関連のメソッドを実際に定義しているクラス一覧」には載ってなかったんだよなあ。Ruby 1.9 時点では pow メソッドはなかった。AtCoder の 2.3 でもまだないかもしれない。

方法色々

つらつら眺めてると、require 'matrix' して lup.solve で勝手に方程式を解いてもらえるとか、require 'openssl' すると mod_inverse が利用できるとか、知らない方法が色々あるもんだ。でも LUP 分解が解らなければ見ても使うべきときが判らないし、知っても使えない。『[単行本] 平岡和幸, 堀玄【プログラミングのための線形代数】オーム社』は中座してるし、『[単行本] ロナルド・L. グレアム, オーレンパタシュニク, ドナルド・E. クヌース【コンピュータの数学】共立出版』もちょっと眺めただけ。若いうちに学校で広く浅くでも詰め込んでおくべきなんだよ。基礎がないと何も積み上がらない。

ツッコミを入れる

2019年11月12日 (火) 「「分母が大きい方が数を正確に表せるんだ(The bigger the denominator, the more exact)。分母は、その表示する目的を達成するために必要最小の数を選択するんだ(But you always use the lowest denominator that will do the job.)」。」■単位長さ(インチ)がまずあって、必要なだけ刻み目を刻んだあとで刻み目の数を数えるのか。へええ。それじゃあインチがあまり短すぎない方がいいかもね。■通分が弱みなのは間違いなさそう。全部のパーツがワンオフの特注品では工業化を妨げて戦争にも負けて、そんなのはアメリカじゃない。■空気圧が計れる空気入れがあって、その目盛りが「空気圧ゲージの表示はpsi/kPaからbar/kPaに順次変更されます」という状態なんだけど、bar と kPa はゼロの数が２つ違うだけ。bar を使うと必ず空気圧が小数で表されることになる。これがどちらも馬鹿馬鹿しいと思うんだ。小学生でもできる計算に対照表はいらないし、常用域が小数になる単位もいらない。なんで psi 表記をなくして bar に直すのかと、アメリカ人的感性で(ほんまか？)一言言いたい。

ツッコミを入れる

2019年11月11日 (月)

最終更新: 2020-08-27T19:59+0900

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

解けなかった。まだ解けていない。考慮すべきが漏れてるのか、何か思い違いがあるのか。

とりあえず、完全に並べ替えても題意を満たせないケースに No を返してみた。該当(AC)１件>https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8356932。

N-2 回の交換

N-1 回の交換だと N 要素の A 数列を完全に思い通りに並べ替えられると思った。ぎりぎり１回足りないのが N-2 回なのかな、と。

ぎりぎり１回足りない条件とは？

A 数列のすべての要素があるべき位置から外れた状態にあり、A 数列のすべての要素が数珠つなぎに位置を交換している、だと思った。

1. A 数列のすべての要素にあるべき位置が存在する(B 数列にあって対応する要素が１つだけしか存在しない)とは

ソート済みの A 数列のどの隣接要素を入れ替えても題意を満たせなくなることだと思った。

逆の例は、B 数列に重複する値が存在する場合や、B 数列の最小要素以下の要素が A 数列に複数ある場合など。その場合は A 数列に区別が不要な要素が存在するということであり、交換回数を節約できてしまう気がした。

2. A 数列のすべての要素が数珠つなぎに位置を交換しているとは

これもそうではない例を考えると、A 数列が k 要素と N-k 要素の２グループに分かれて位置を交換している場合が該当する。k 要素をあるべき位置に並べ替えるのに k-1 回の交換を要し、N-k 要素を並べ替えるのに N-k-1 回の交換を要するのだから、計 N-2 回の交換で A 数列のすべての要素があるべき位置に納まってしまう。

だから A 数列のすべての要素が唯一のグループを作って位置を交換していなければいけない。その場合に最大 N-1 回の交換を要する。

というのをコードにして提出したのだけど、WA が半分>https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8366469。答えが二択なんだから惜しくもない。わっかんねーなー。

続く……

ツッコミを入れる

2019年11月09日 (土) 「Googleが2段階認証の仕様を変更、キャリアメールアドレスへの送信が不可に | スラドモバイル」■本題とは直接関係ないんだけど、スマホが唯一のデバイスであるなら、二段階認証になにほどの意味があるだろうかという疑問がある。自分は PC が基本だからセカンドデバイスとして携帯電話で受信する SMS に意味があるけども(とはいえ送ってくるのは GitHub だけだ)。■■■自己解決。一段階目はデバイスの関与(記憶されたパスワード)は必ずしも必要なくて、むしろ無関係な方が普通で、漏れたパスワードリストなんかを使った不正アクセスが二段階認証で防げる。

ツッコミを入れる

2019年11月07日 (木) [C++] ムーブセマンティクスと右辺値参照。未だによくわからないけどちょっとヒントになりそうなことに気がついた(気がする)。題材は自分も答えが欲しかったこの疑問。「誰も疑問を呈していないことに自分は疑問なのですが、push_back と emplace_back にトレードオフの関係はないのですか？ emplace_back に利点しかないのだとしたら、そもそも関数が分けられずにライブラリ側の push_back 自体の実装が効率の良いものに置き換わるだけで済んだように自分は想像しましたが……。関数が分かれている以上は何かしら使い分けしてほしい意図（ライブラリ側の意図）ががあるものではないのですか？」■よくわからない理由に、右辺値というものの見え方がプログラマとコンパイラの間で180度変わることがあるんじゃないかと思った。最初にそこを区別せずに、右辺値があーだムーブがこーだという文章を読んでも、それぞれが矛盾することを書いているように感じられるのではないか。■右辺値というのはこれまで一時オブジェクト、書き込みできない値、プログラマの制御下にない値だった。ムーブセマンティクスをプログラマが表現できることになり、右辺値でないものを右辺値であるとマークできるようになった。それはプログラマにとって、値に対する制御を手放すという意思表示である。ちょうどコピーした auto_ptr が所有権を手放すがごとく。■コンパイラから見ると従来の右辺値と右辺値であるとマークされた値は、自身が破壊のタイミングを握っている(渡された)、制御下にある値である。■最初の疑問に戻る。emplace_back(push_back のムーブ版だと思ってるけど実は知らない)を使用することは、プログラマに引数となった値に対する制御を手放すことを要求するので、プログラマ自身が意図を込めて選ぶべきものになっているのだと思う。■push_back にムーブ版のオーバーロードを追加することもできたと思うんだけど、できないんだろうか、できるけどやらない方がいいという判断なのだろうか。それはどういう？オーバーロードがあれば `T v; c.push_back(move(v))` みたいなコードを書いて呼び分けることになったと思う。■たぶん std::move って書いても書かなくても同じな場面が多くあると思う。ムーブしてきた値を受け取る側からしても、&& と書いたからといって特別な何かが必ず期待できるわけではないらしいし。俺は煩わしいからできるだけ書きたくないし、書いた方がちょっとだけ嬉しい場面でも書かずに済ませたいクチ。■コンストラクタと代入演算子がムーブとコピーがオーバーロードされる例か。かつての auto_ptr の所有権移転コードのようなものを書くみたい。うっかりリソースを共有した状態にすると二重解放の罠。auto_ptr と違ってちょっとわかりにくいのは、値に対して所有権を持っていないというのがどういう状態か想像しにくいこと。ポインタであれば値が NULL であるとか、値はあっても弱参照でありいつまでデリファレンスできるか不明であるとかが想定されるのだけど。■おべんきょ。「C++のムーブと完全転送を知る - Fixstars Tech Blog /proc/cpuinfo」「メイドでもよく分る右辺値参照 - TXT.TXT」■git もだいぶ時間がかかったけど(ものぐさなだけとも言う)、だいぶ煮詰まってきたんじゃないだろうか。かつての C++ In-Depth シリーズのような本が読めないのが残念でならない。そういう研究が必要ないというのなら、C++ が言語として進化したのではなく単に充実しただけであるということ。進化がないのも研究書が読めないのもどちらも不満。■ムーブってついつい一時オブジェクトの省略(※コピーや移動の終着地点に最初から一度だけオブジェクトを構築して済ませてしまう)と結び付けて効率化の手段だと考えてしまうけど、プログラマが書いたムーブコンストラクタが実行されるなら、それはコピーコンストラクタが実行されるのと変わりがないのでは？利点があるとすればメンバとして保持する外部リソース(ヒープメモリ、ハンドルなど)の確保が省略できる、奪い取って間に合わせられるという点にしかないのでは？■俺は auto_ptr が大好きだし、その制約も喜んで受け入れるし、Rust のメモリ管理も好きだけど(「Rustは何が新しいのか（基本的な言語機能の紹介） - いもす研 (imos laboratory)」)、ムーブは面倒くさいなあ。これまで通りコンパイラの最適化に期待するだけにして、面倒は避けたい、必要に迫られるまでは。

ツッコミを入れる

2019年11月06日 (水) 「[B! コミュニケーション] なぜ「事実」と「意見」を区別して話せない人がいるのか。 | Books&Apps」■タイトルから抱く期待と本文を読んだ感想が一致しない。そういう意味でブコメの流れはもっともである。■新聞の投書欄でたしか読んだけど、医者にかかって「風邪みたいなんです」「それを判断するのは私です(ムスッ」みたいなやりとりって感じ悪いじゃない(少なくとも投稿者はそう受け取っていた)。言い方があるだろうと(「どうしてそう考えたのか話してもらえますか？」)。最初に対立関係や上下関係を作って得する人間が存在するのかと(医者も患者も上司も部下も得していない。ただし医者と上司の目的がマウンティングである場合はこの限りにない)。で、誰が改める？■人間は道具ではないし、頭が付いてるし、それを活用できない上司が無能に見える。もちろんまだ信用して任せるには足りない新人かもしれなくて、判断のプロセスをいちいち確かめる必要があったのかもしれないけど、その場合でも上司に人を育てる視点がまるでないことが、やはり無能に見せる。勝手に育つ、骨のない奴はやめちまえ、なんてのは人余り世代の甘えでしょ。判断の機会を奪い、そのプロセスを鍛えることもせず、部下はいつまでも上司のためのテープレコーダーなのか？(テープ？ IC と言い直しても同じだな。ボイスレコーダーが正解か)

ツッコミを入れる

2019年11月05日 (火) ミネルヴァの続刊をずっと待っていたのだけど、そのせいで他のシリーズに手を出せないでいたのだけど(そういう気質、あるよね)、作家には続刊か新シリーズかのオプションが与えられており、選んだ結果の新シリーズだったらしい。20190703のスライドの作者のツイッターからあいだに一人を挟んで再び名前を見かけることがなければそれまでだった。それは惜しい(どっちが？)。

ツッコミを入れる

2019年11月04日 (月) ひこにゃん(？)のアイコンでツイッターをやっている人をブックマークしていて、なんとなし歴史・地理・漢字クラスタに分類していたのだけど、ふいに AGC(AtCoder Grand Contest)に参加した話が出てきたりもして、たった一人の人間であっても底は知れない。

ツッコミを入れる

2019年10月31日 (木) 疑問に対する答え。「関心の分離や単一責任の原則に通じるところがあるんでしょうか？」■もっとミクロな話で、曖昧さを残さない、惑わせない、その余地を残さないってことだと理解している。■今回の件で言えば、ヌル終端されないケースがあるのかないのかということ。実際は固定長配列で間に合うのだから用意された配列にヌル文字が含まれないケースは存在しないと考えられる。だから仕様でヌル文字の存在を仮定する。存在しない場合を許さないし仮定しない。それが Assertive であるということ。■曖昧な態度をとれば論理がつながらないし、すべてのあり得るケースを十全にカバーしようとしたときに負担が増える。想定ケースに対して念のために１だけ余分に対応できるようにしたコードに対応するためにさらに１の余分が必要になり、それに対応するコードはさらに……。■カバーする必要性に気がつかずに、論理のギャップに対して２人の人間が異なる見方をすれば、それがバグの始まり。■追加された比較演算子のテストはヌル文字が存在しないケースにアイデンティティを与えて存在を認め、仕様として規定した。だとすれば今後(そして既存のコードも) MYDEVMODE の sz と名の付くメンバにヌル文字の存在を仮定することができなくなり、たとえばメッセージボックスをはじめとする文字列関数にそのまま渡すことがバグの温床になる。律儀にやるなら _MAX_PATH+1+1 のバッファに一時コピーしなければいけない。正気か？■現実をテストケースにすれば実装をいじる必要はなかった。実在しないケースをテストにして実装をそれに合わせたのがあの PR。正気か？■俺は怠け者だから行動する者には負けるけど(「うんこコード、放置しててすまんです」)、その動きが右へ進み左へ進みその間に後退もしている(前進はしていない)、というものではないかという疑いの目は向けている。■■■「一応、strncpy的な関数の使い方を誤るとNUL終端されない文字列を作れますので、絶対要らない対応、というわけでもないと思ってました。」テストに対する勘違いがあると思う。ヌル終端しないコードに対してこのテストと実装の修正で何ができるのか、シナリオで示して欲しい。もちろんそれを伝えはしない。聞く耳ねーからな。無駄無駄無駄。■念のために書くけど、「ヌル文字の存在を仮定する」というのを「ヌル文字の存在を信じて暴走すべき(それを許容すべき)である」などと曲解されていては全く浮かばれない。ヌル文字の後ろを比較対象にするのがあるべき仕様の外であるなら(wmemcmp を使わない理由)、構造体のために確保されたメモリの外を比較対象にするのもあるべき仕様からは外れている(wcsncmp を使う理由)。どちらも否定していないし、今は無関係。混同している人間が誤っている。

ツッコミを入れる

2019年10月30日 (水) ぶん殴りたい。共通の理解の上で意見が合わないのなら、それは価値観の違いであり、それをどうこうすることはできない。だけどある程度共通のものがないとどうしたって戦争が避けられないから、批判に堪える出版物を引用する。自分個人の考えや感覚でそれができるとは考えない。しかし価値観以前に共通の理解をこの者との間に築くことができないせいで、無駄に消耗する。全くの無益。耳を塞いで他人にでたらめな要求を押し付けるふるまいを「犯罪的」だというのだ。自己の無謬性にそこまで確信を持てるとは大した自信家じゃないか。「本物は違う」とはこのことではないか。俺の方はといえば事実関係に白黒が付かないことに気も狂わんばかりになっているというのに。■https://github.com/sakura-editor/sakura/pull/1081#pullrequestreview-307582232 の指摘は最初から十分に理解できるものだった(なのに不備を詫びることができるのは報告者の人徳だ)。ここにアクセス違反のおそれがあるとヒントを与えられても見つけられない者に、最初から何が期待できるのかという考えもある。万事この程度の理解度で弁明する者のいない既存コードをふんわりざっくりけなすようなまねをするから、「お前が」「(わざわざ)言うな」の念が募る。■俺はこの者の人格に絶望している。

ツッコミを入れる

2019年10月29日 (火) 日曜日にあった ABC。ちょっと毛色が違った D 問題。「D - Water Bottle」■難しポイント。sin と tan 間違えた。弧度法から度数法への変換を間違えた。高校数学では tan/sin/cos しか習わないので Ruby の Math モジュールのドキュメントを漁って atan と atan2 と atanh のどれが自分の求めるものか確かめないといけなかった(しかも最初 sin 系の関数を試していて角度の変換も間違えた)。これが難しいとか高校生に鼻で笑われる。

ツッコミを入れる

2019年10月26日 (土) もうはばかる理由もないので最初(sourceforge.net)から思っていたことを書くけど、「定石だから」ってのは理由になりはしない。そもそもその「定石」がローカルルールや迷信の類ではないのかという疑いがあるが、そこをクリアしたとしてもやはり同じ。デザインパターンがそうだ。広く流布し認められたパターンであっても、パターンカタログに載っていること自体が、パターンを採用する理由になるわけではない。これまで読んだどのパターン本でも、パターンが適用できる具体的なシナリオと、パターンが持つメリットとデメリットの両方と、同時に比較考量すべき別のパターンが併記されていた。「定石だから」で留まるのは浅はかなんだ(「手段を目的化してしまうと見失いがち。手段は常に目的に対してテストされ、いつでも置き換えられなければいけない」)。盲信するならせめて対象として権威を選ぶくらいはしないと馬鹿なんだ。

ツッコミを入れる