/ 最近 .rdf 追記 設定 本棚

脳log[2020-05-15~]



2020年05月15日 (金) 10万円、何度も申請できちゃう?本末転倒のオンライン [新型コロナウイルス]:朝日新聞デジタル」■申請とかはまあ大した問題ではないのでは? 何度も申し込みできるのも(受ける方が忙殺されるらしいのはともかく)冪等性があって当然として問題ないのでは? どの口座に何番さんと何番さんの給付金を振り込みました、が確実に記録されていれば、多少のミスはリカバリーできるのでは?■一世帯丸ごと単位でしか申請できないなら(DVで避難している人などは例外)、この照合作業は省略できたのでは? 「対象者に正しく支給するには、世帯情報をまとめる住民基本台帳ネットワークの情報と申請時に入力された情報との照合が必要だ。世帯情報は自治体だけが持っているため、申請内容が正しいかどうか、職員が1件ずつ確認している。」 結局給付に必要な情報は自治体がほぼすべて持っている。「誰の給付金をどこの口座へ」という最後のピースだけに集中したい。■申請者のミスに対しては……。「給付金は世帯ごとに世帯主が申請するルールだが、別世帯の祖父母の分まで合わせて申し込む間違いなどが目立つという。」「手続き完了を知らせるメールが、「迷惑メール」に分類されて申請者が気付かず、区に問い合わせるといった別のトラブルも続き、職員が対応に忙殺されている。」 ポータルサイトとアプリがあるんだよね? 自分で自分の間違いに気づけるよう情報を提供する仕組みがあって、基本は自助で、問い合わせがあってもそこへの誘導で済ませたい。でもすっごく難しそうではある>「マイナポータルで特別定額給付金の申請(と思ったら違ってぴったりサービス)」。個人の電子証明書をもっと手軽に活用できるインフラが整っていれば。「私は(電子証明書)です。(PIN を入力)。給付金を申請します」「私は(電子証明書)です。(PIN を入力)。現在のステータスを教えてください」で済ませたい。■@hosakanobuto「「電子申請」と聞けば、オンラインショップやチケット予約等のイメージで、まさか「電子申請」が届いてから自治体職員が、情報連結のない「住民基本台帳」を照合して一人一人確認作業をしているとは想像がつかないだろう。電子手続きは入口だけ。あとは「目視して確認」する必要があるとは信じがたい。」 理想と現実は主客が転倒しているようだ。理想では振り込み準備完了までの手続きがデジタルで完結していて、その作業を申請者本人にやらせるためにポータルサイトがあって、PC やスマホなどアクセス手段を持たない人の作業を代行するために郵送という抜け道が用意されていて、という風であってほしい。■ポータルサイト(1つ)が、自治体(複数)が持つ世帯情報を盗み見ることができてはいけないという制約がある? 認証・認可の仕組みを使って申請者がポータルに権限を与えられないの? でも自治体(複数)の側にアクセスを受け付けるインフラがないか。オフラインだったり専用ネットワークだったりするか。個々の自治体がデジタルでの処理能力を持つしかない。それでエントリーだけインターネットに開放する。だからポータルサイトが単なる認証代行になってる。でも今回のように特例的な制度をどう自動化する? 人海戦術もひとつの選択だとして、自動化したときにポータルとどうやって連携できる? 「住民基本台帳は門外不出だから手続きの内容や進捗をインターネット経由で見せることはできません」? 「国民のプライバシーに配慮した結果だからしかたありません」? まあ、お漏らしに対するゼロリスク願望はある。何か起これば自分が何かを得るために望んで受け入れたことではないと責める気持ちが予想できる。■マイナポータルを見てみたら「行政機関などが保有するあなたの情報(世帯情報・税・社会保障等)を確認することができます。」って書いてあるね。インターネットで見られる。給付金については「本サービスで特別定額給付金のオンライン申請が可能となりました。準備のととのった市町村より順次受付を開始しています。」という文言がある。これだと手作業で大変なところもある、みたいな話にも思えてくるけど、そう思いたいけど、自動化を阻むような気の狂った運用ルールがあっても驚きはしない。昔も今も人が安い国なのだ。■■■@2020-05-18 首長さんが自分とこの事例を踏まえて対応方針の大まかな分類と実作業手順などを。「なぜ10万円給付に時間がかかるのか|東修平(四條畷市長)|note」■現在の仕組みはデジタルデータを印刷した書類をやりとりする方法に最適化されている(業者がまるっと引き受けている)、みたいな感じ。マイナポータルから引き渡されるデータはユーザー入力部分が多くバリデーションの手間が余計にかかるだけみたい。自治体側の最適化っていうのがデジタル化によるものではなく業者を利用することによるものだっていうのが、過渡的であり解消されてほしいボトルネックである気がするなあ。デジタルデータを活用できるのがシステムを構築した業者だけであり、その業者は紙ベースのプロセスを支援する存在であるらしいから。でもこれって自治体側が仕事のやり方を変えると決めて、業者と共同作業でシステムとプロセスを構築していくのでないと、現在の形から抜け出すことはできないのではないか。


2020年05月14日 (木) AtCoder の言語アップデートが過去問に遡及したらしい。ゴルフが大変だぞー。「atgolfer (@atgolfer1)さんはTwitterを利用しています


2020年05月13日 (水) [Xperia 10] ほとんど待ち受けだけだと11日経ってバッテリーの残りが23%>Screenshot_20200513-132807.png。ガラケーがスマホになったからって使い方は変わりません。■(おそらく) SwiftKey キーボードのアップデートで一度アイドル時のバッテリー消費がひどく悪化したが、その後のアップデートで、むしろ以前よりバッテリー消費が抑えられるようになったという経緯がある>20190518p01.04.01


2020年05月12日 (火) ジェイン オースティンの著作『高慢と偏見』は翻訳によって『自負と偏見』とされることもある。まだ読んだことはない、タイトルだけ。どちらも真実であるなら、横に並べば自負に見えるものが、下から見上げれば高慢に映ることがあるんだろうな、と想像している。■とある掲示板で、「態度の悪いやつ、傲慢な開発者をつるし上げようぜ」と煽動する者がいた。ここで、傲慢というワードは不首尾に終わった煽動者が独自に持ち出したものだった。傲慢と高慢は似ていると思う。匿名なのをいいことに味方の振りをして板の流れを自分のものにしようとしたのかどうか、煽動者の意図は知る由もないし、そうやって徒党を組もうとする行為が俺の理解や行動の埒外にあるのでどうでもいいのだが、傲慢という語がどこに立つ誰の言葉であったのかには、興味がある。■最近のことだけど策動という語を初めて知った。あの煽動が利己的な意図に基づくものであったなら、実際に働きかけが成功していたのなら、実に悪知恵が働くと言えるだろう。理解の外にあるから俺には為す術がない。


2020年05月11日 (月)

最終更新: 2020-10-29T15:09+0900

[AtCoder] AtCoder Beginner Contest 167F 問題 Bracket Sequencing

 わからない。提出 #13147757 (WA)

解説 PDF で考え違いを教えてもらおうと思ったら解説動画しかなくて、うんまあ、じゃあいいや。(追記) 13日の現在はPDFもあるみたい。

これを読んでも間違っているとされている定義のどこに問題があるのかわからんのだよね。果たしてそれで解けるものか。>「競プロでよくある「バランスのとれた括弧列」の定義が壊れがちな話 - notブログ

 まだわからない。提出 #13156522 (WA)

正規表現の ?* に変えたことで、AC は増えたけどまだ WA がある。

こういう生成スクリプトでテストした結果、最初の提出で使用した正規表現パターンに問題が見つかった。

def puts s
	re = /(?<p>\(\g<p>?\))/ # バグあり。提出 #13147757 より。
	re = /(?<p>\(\g<p>*\))/ # 意図通り。提出 #13156522 より。
	t = s.gsub(re,'')
	print "#{t.empty?}:\t#{s}\t#{t}\n"
end

L,R = '('*5,')'*5
10.times{
	puts L+((L+R).chars.shuffle.join(''))+R
}

LR = '()'
10.times{
	puts 10.times.inject(''){|s,| s.insert(rand(s.size+1),LR) }
}

そうするともう、提出したスクリプトは完全に自分の意図通りに動作しているはずなんだけど、WA がある。書き間違いではなく、考え違いがある。

 そっか、)( 型の s を連結する順番によって結果が変わる。

)))()((( の2つの s があるとき、連結のしかたによって )))((( が残る場合と )( が残る場合に分かれる。)( を残した方が 'Yes' と答えられる確率が高くなる。

 提出 #13158713 (AC / 1014 ms / 16076 KB)

 バグがありますよ。)( 型の文字列が1つだけのときに必ず No と答えてしまいそう。

今現在 Ruby で一番速い提出は 498 ms だ。>すべての提出 - AtCoder Beginner Contest 167

再帰ありの正規表現(※矛盾した表現)を使ってる時点で勝ち目はない。左括弧の数が負になれないのに気をつけながら、左括弧と右括弧を対消滅させながら、左括弧と右括弧がいくつ残るかを数えればいいんだろうけども。

 問題はそこではなかった。>提出 #13160001 (AC / 821 ms / 14380 KB)

しかたない、省メモリを売りにしていこう。>すべての提出 - AtCoder Beginner Contest 167

ソートを必要としてないあたりで(※)ちょっとは有利を得てもよさそうなもんなんだけど、トップの提出はソート対象を )( 型に限るなどしてる。※ループ内で2要素のソートもあかんか?

 これが限界>提出 #13174623 (AC / 533 ms / 14308 KB)

 ちなみに

( 型の文字列を最優先に、)( 型のうち ( 優位のものを優先的に、最後に ) 型を、という感じで連結していくのがストレートな解答らしい。

3つの型の文字列を統一的にソートすることもできるし、)( 型だけソートしてもいい。

自分はどれもソートしてないんだけど、)( 型の中から1番目と2番目に条件のいい文字列をピックアップするための比較演算()( 型の文字列1つにつき1~2回)が重くてソートした方が速い。

 @2020-10-29 提出 #17712418 (AC / 391 Byte / 377 ms / 19604 KB)

(ゴルフ勢を除けば)わりと短くてそこそこ省メモリで今のところ Ruby で一番速い。すべては正規表現エンジンとそれを使う gsub のちから。

やってる内容は最初の AC と変わらない。入力をがばっとひとまとめに処理するようにしたのと、最小2要素を取り出すのに一度全体を配列に蓄えてから min メソッドを使うようにしただけ。


2020年05月10日 (日) 『パンダかめんの最期』というやたらお話が印象に残ったマンガがあって、その人の8年ぶりの新刊をチェックしてみたらあまりにも路線を外したカバーで躊躇してしまった。で、エロソムリエのレビューをあてにしようとして圧倒されてしまったよという話。>>「酒とエロ漫画の日々。: 本日のバウムクーヘン。


2020年05月08日 (金) 今日から読み始めた『こころの処方箋』(河合隼雄)を知るきっかけは piro さんのツイートだったような気がしないではない(※勘違いなら、勘違いした原因は「耳が痛い」という共通点にある。ツイートも本もありがたい内容である)。この本を前提として昨日の話(20200507)がどのように繋がるか考えたい。■友人が自分に「俺はバナナが好きだ」と告げる状況を想像する。「そうか友人はバナナが好きなんだな」と心に浮かぶのは素直な反応で良いけれど、考えるべきは、「考える」と呼ぶにふさわしい精神活動は、友人が自分にバナナが好きだと告げる意味について考えを及ばせることだと思う。■ここで「俺はバナナが好きだ」を自分がよく知らない言語に置き換えてみると、頭の回転が速い人と遅い人の両方の気持ちが想像できる。よく知らない言語では、聞き取りに苦労するだろうし、単語の意味もうろ覚えで、知らない単語もある。「たぶん彼はバナナが好きだと言ってるんだろうな」というレベルの疎通ができたりできなかったりするのが「一般人」の対話だとする。(※「対話」ができないでグルーミングのような「会話」しかできない「一般人」も多いと思う。この2つの単語を使い分けることについて最近読んだ本に書かれていたが、どれか忘れてしまった)。■例文を日本語に戻して頭の回転を速くすると、「俺はバナナが好きだ」というのは当然の前提であって、思考はその先へ飛んでいる。それこそ一を聞いて十を知るように理解を深めていって、それでぶつかるのが理解したそれらの土台であり源である人間という存在ではないか。人間は単独ではなく他者との関わりの中で存在しているから、それら全体を把握しなければさらなる理解に近づくことができない。そんなのはほとんど不可能に思える。聡明な人ほどそれを知っているだろう。■昨日リンクした quora の記事の中のエピソード。「検査結果を伝えてくれた臨床・公認心理士さんのおっしゃった 「ギフテッドです。いままでよくがんばってきましたね」 という言葉は、涙が出るほど嬉しかったです。それは努力が報われたから……勉強ではなくて、どうやったら人と交わることができるのか思春期を通じてずっと悩み苦しんできた私に対するねぎらいの言葉だったからです。」 quora の人はこのレベルで他者を理解し、理解されたいと考えているのではないか。それは簡単ではないから、決して「俺は理解している。お前たちも理解しろ」というような態度には結びつかないと思う。■時間をかけてでもこのレベルの理解に追いつきたいと考えることができているか、「一般人」が問われている。たぶん多様性を受け入れるのに必要な態度と同じか似ていると思う。多様なものは自分の理解や想像の外にも広がっているから、自分が理解可能、許容可能な範囲の中だけに限ることができないから、努力と妥協なしには共存できない。■■■「chokudai(高橋 直大)🌸🍆さんはTwitterを使っています 「大企業の役員さんレベルと話すと、やっぱめちゃめちゃ頭の回転とか認識能力とか高くてやべーなー、ってなる。AtCoderが出来る人とはまた違う凄さを感じる。」 / Twitter」 自分が想像するのは、理解が及ぶ広さ、深さ、早さに優れた人。それを備えていることが会う人にどのような印象を与えるのかは、会う機会がないので知りません。


2020年05月07日 (木) Latest topics > 「もっと考えろよ」「想像力なさすぎだろ」みたいな言い方を僕はしたくないなっていう話 - outsider reflex」とそこを経由して「IQが20違うと会話が成立しないと言うのは、事実なのでしょうか?経験はありますか?に対する松本 直樹 (Naoki Matsumoto)さんの回答 - Quora」■piro さんは自分なんかよりもいい経験と出会いをしていてものが良く見えているし、ものが考えられる人だとときどきアンテナに引っかかってくる記事やツイッターを通して知ったつもりでいるんだけど、ちょっと引っかかったので、ちょっとだけ書いてみようと思う。■引っかかったのはこの部分。「この記事を書かれた方(ギフテッドの人)には、もしかして、自分の話を相手に理解してもらえなかった経験はあっても、相手の話が自分には理解できなかった経験が無かったりするんだろうか?」■quora に書いた人はたしかに「でも実際に起きていることは、上のような「なんで何回も説明しないとだめなの」「なんで伝わってくれないの」というようなコミュニケーション不全による高IQ側の孤独さです。なぜ伝わらないのか、何がいけないのかと頭を抱えて涙している、そういうシーンです。」と、わかっている立場から書いているけど、同時に「そもそも自分の日本語が間違っているかもしれない、自分のアイディアが頓珍漢なものかもしれないという恐怖感」が訪れるとも書いているし、また、「馬鹿なことを言っているのは自分じゃないのか、人と満足に交われないのは自分の性格が悪いのではないか、と悩み苦しみ」と、弱い立場からも書いている。孤独な人間は自分の正しさを確かめるために他者を利用できない。自分で自分が信じられなくなったら狂人へまっさかさまだ。「一般人」に囲まれたときそういう恐怖の内にある。だから「相手の話が自分には理解できなかった経験が無かったりする」というのは想定される像から外れると思うのだ。quora の方で「高慢ちきな高IQが「お前たち低能とは話が合わない」と吐き捨てるように告げるシーン」は実像に合わないと否定されているのだが、そのイメージに近づきすぎていやしないかと思うのだ。■『心を読みすぎる 心の理論を支えるワーキングメモリの心理学』(前原 由喜夫) という本を読んだ。「心を読みすぎる」というワードでは伝わらないと思うんだけど、この言葉に込められた意味は、他人の考えが自分にはよくわかっている、と考えているときこそ他人が見えていない、見えていないから(自己を投影しているだけだから)そう思えてしまう、というようなことだ。「ワーキングメモリ」というワードが quora の記事と共通している。quora の記事を書いた人は明らかに単純バカではないから、他人のことを理解しているなどと安直に思い込んで安心することはできないのではないか。だから確かめたいし歩み寄る努力をするんだけど、「一般人」の側があまりにも簡単に、「気持ち悪い」という言葉や「何言ってるの……?」という不審な目でもって、「意味不明な話をしている気味の悪いやつを排斥」してしまうのではないか。■伝える努力をしたくても、理解しよう受け止めようという姿勢を「一般人」の側が持てなければコミュニケーションは成立しない。「「やばい、相手の言ってることがまるで自分には理解できない。どんなに説明されてもチンプンカンプンだ」という感覚」。やばいと感じているうちは大丈夫。「「相手の言ってる事がまるで分からない」時、僕は、すごく惨めな気分になるし、相手に対する申し訳なさや負い目を感じます。」 この気持ちがあるなら大丈夫。でも一方が諦めて排斥して開き直ったら、どうしようもない。そういうことを quora の記事は書いているのではないか。■だから quora の記事がきっかけにすぎなかったとしても、十分に踏まえられていない感じが気になった。


2020年05月05日 (火) もう何年にもわたって屋内では極力かかとを着けないように心がけている。屋内に限ったのは靴をはいてある程度以上の歩幅で自然に歩くことと両立できないからだが、屋外であっても、自転車のペダルとバイク(※アメリカンではない)のステップは土踏まずではなく拇指球でもって踏んづけるものであるから、そのときは同じような足の形になっている。それは大げさな身振りを伴わない抜き足差し足であり、かかとからドッスンドッスン着地しながら歩くことへのカウンターであり、ねこの足つきである。■日常にすぐにでも取り入れられるエクササイズのようなものとしていいことづくめだと思ってるんだけど、どうだろう。膝とかふくらはぎとか体幹とか。唯一の欠点は靴下の同じ部分がいつも一番に破れることか。■たしか Vibram FiveFingers が話題になったり、町中でジョギングする人が目立ってきた頃からだったと思う。結局あれはコストパフォーマンスが悪そうで買わなかったんだけど(唯一無二ではあるが高いよね? 耐久性高くないらしいじゃない?)。■屋内での歩き方を3通りに表現したが、もうひとつ思い付いた。滑る雪の上を歩くとき、ローラースケートをはいてるとき、スケートのとき、スキーのときの体重の乗せ方と共通点があるかも。雪の上では前に放り出してかかとから着地した脚をつっかい棒にするような歩き方ではこける。足が滑って前に逃げても着いて行けるような体重の乗せ方が必要になる。で、そういうのは膝を曲げて腰を落としたような歩き方になるから、「靴をはいてある程度以上の歩幅で自然に歩くことと両立できない」。


2020年05月04日 (月) 風俗嬢とカツオの刺し身の違いを論理的に説明して」■スーパーのカツオの記事は参考になるなと読んでいた。岡村風俗発言は下種いなと思っていた。共通項には考え及ばなかった。違うと思いたいし違いがあると思ったけど、決定的な違いを俺も教えてほしい。■商品の違いと、どこまで遡って言及しているかと、積極性の違いが人によって境目になるみたい。俺にも境目がある。「いつもと同じ値段でおいしい。ラッキー」「買うのは風俗落ちした素人ではなくカツオ」「買わないことが助けにはならない」というところで自分を許している。■風俗落ちというところに想像を超えたボーダーが俺にはある。すごく不幸なことに見える。これは俺の偏見。「~落ち」という表現にもそれが込められている。自分で想像できない背景を読み込んだ「コロナの影響でスーパーで買うカツオの刺身が美味すぎる。」という記事に感心して参考にしたのと同じように、岡村発言に一瞬「あ、そういうことがあるのか」と得心したのも事実。秘めておくべき深夜の男集団のノリだけども。


2020年05月02日 (土)

最終更新: 2020-05-29T19:43+0900

[AtCoder] AtCoder Beginner Contest 165D 問題 Floor Function

数弱さんには厳しい回だった。E 問題は読む時間さえなかったので今日の日記は D 問題。次の整数式を考察するだけ。

x*A/B - x/B*A

A を掛けてから B で整数除算するか、B で整数除算してから A を掛けるかという違いで生じる値の差について。その最大。

 1. x が大きいほど大きいんじゃないの?>提出 #12618779

違います。B を周期として第一項と第二項が一致します。A がその周期に与える影響はよくわかりません。

ちなみに B の上限は 10^{12} のため周期全体をテストすることはできません。>提出 #12633357

 2. x が B の倍数マイナス1のとき第二項の整数除算で切り捨てられる値が最大になるんじゃないの?

  • →引き算される第二項が相対的に小さくなる
  • →全体として大きくなる

たぶんその通り。だけど説明を端折った N との関係がわかんなかったのと、A と B の因数によって第一項と第二項で周期 B の位相がずれていくんじゃないかという気がしたので探索した。>提出 #12640433。でも錯覚。位相がずれるなら「B を周期として第一項と第二項が一致します」が嘘じゃんねえ。

Ruby で提出している他の人は、提出の早さも実行速度も優秀だった。>すべての提出 - AtCoder Beginner Contest 165

 B 問題 1%

実は B 問題で15分近く詰まっていた。瞬殺できないとあせる。最初は(もはやうろ覚えの) log を使って計算していた。

X = gets.to_i
p ((Math.log(X) - Math.log(100)) / (Math.log(101) - Math.log(100))).ceil

でも大まかにしか数字が一致しない。同じかちょっと小さい数字になる。俺が log を忘れているか浮動小数点数の誤差か(近い数字の引き算とか良くないのでは?)これの影響じゃないかと>「(複利、小数点以下切り捨て)」。複利の計算をするごとに切り捨てなければいけないのでは?

B 問題なので手続き的に解いても TLE にならないのはわかっていた>提出 #12601266

 C 問題 Many Requirements

実は C 問題でも30分近く詰まっていた。A 数列の総当たりでいこうと決めるまでに制約条件を総当たりしようとしていて、他の制約にまったく制約されない孤立した制約条件の扱いをうだうだ考えていた。

再帰をループにするとかの効率を考えずにちゃっちゃと書いただけなので、提出へのリンクはなし。

上手い人のゲームプレイ動画と AtCoder の解説 PDF のあいだの共通点。多様性のなさ。へたくその動画の方がバラエティに富んでいて見ていて面白くさえある。間違え方というのは本当に千差万別で、ありとあらゆる機会を逃さずに、そう来るかと予想もできない脱線をする。たったひとつのゴールに向かう限られたルートに収斂していくということがない。

当人にとっては面白くもなんともないので、B 問題、C 問題に詰まらないような世界線に乗っていきたい。

 あ、この問題ってそういう見かたができるのか。>小数部を分離

chokudai(高橋 直大)🌸🍆 Verified Account @chokudai

とはいえ、高度な問題を解く時に、「floorが出てきたら整数部と小数部に分離して式変形!」って結構大切な考え方なので、Dみたいなのを出さないと、後半問題で突然そういう数学力が応用状態で問われることになるので、そのあたりの塩梅がむずかしいよね。

x が固定小数点数で小数部が5桁なら、x - x/100000*100000 が小数部分になる。……という話ではない? D 問題を解くときの話?

以前にもはっとさせられたことがあった。

kを使った場合のコストは、k-1以下のすべてを使ったコストより高い

これって要は 100000 > 11111 (2進数) と同じことなんだけど、自分のような人間は「この一連の操作のコストは(書き換えた要素の数によらず)2^k である」という問題文を読んだだけではたどり着けなくて、上のように事実として示されて2進数で考えてみて初めて了解できることだったりする。

一を聞いて十を知る(20200508)」ってこういうことだと思う。賢い人は「いやそれって同じことだから一の内に入るのでは?」と思うかもしれないけど、全然違うのである。

そして自分が AGC022C 700点問題 にまるで歯が立たない理由には、列挙された要素の数とそれらを煮詰める段階の深さに関係があると思ってる。「理解が及ぶ広さ、深さ、早さに優れ(20200508)」という風に書いたけども、そうでない自分は頭の中で抱えきれないし、整理して外に出して部分ごとに解決することもできない。

アストロノーカやテラリアですでに知ってるんだけど、ツリー状にねずみ算式に倍々に増えていく要求リソースの全体を把握すること、並列に進行する精製過程をストールさせないように需給を絶えず調整すること、このサプライチェーンの階層がある程度以上になると(たぶん3くらい)完全にお手上げになってしまう。そういう能力がない。

たぶん3くらい」 深さが3、二分木なら葉の数8までしか脳内で扱えないんです。

 「アルゴリズム格言」

ちょっと検索したら「銀の格言」としてこんなのが列挙されてる。

  • 攻めは銀、受けは金
  • 銀は千鳥に使え
  • 桂頭の銀定跡なり
  • 銀は成らずに好手あり

つまりはこういうことなんでしょう?

chokudai(高橋 直大)🌸🍆 Verified Account @chokudai

「この問題だったらこうするだろ」って感じに無意識にやってることってめちゃめちゃ多くて、その「無意識」を言語化して列挙するだけでもめちゃめちゃ有効だと思うのよねえ。

chokudai(高橋 直大)🌸🍆 Verified Account @chokudai

「chokudaiのアルゴリズム格言1000」とか作って、こういうのをひたすら列挙しまくると、格言の組み合わせだけで良い感じに解ける問題がたくさんできそうだな、と思っていて、アルゴリズム名とは別レイヤーで浸透させたいな、ってちょっと思ってる。

解説なんかだと、正しいルート以外はすっ飛ばされちゃう」というのがまさしく今日書いたことで(20200502p01.04)、解説PDFよりも「競技プログラミングの強みと「典型力」について - chokudaiのブログ」という思考の跡が見えるブログ記事の方が自分には有用となる理由。アルゴリズム格言に期待する理由。


2020年04月28日 (火) AtCoder から精進する者に報いようとする意思を感じる。解説 PDF でさっさと復習するか。■以前一度だけ読んでみたことがあって、「こうやったら解けるんですよ、簡単ですね」とは書いてなかったけど、「何でそうやってみようと思うのか」とか「そうやったものが答えになるのがわからん」みたいな感想を持った。■まあ、そういうのは慣れてから理解が追いついてくるのを待ってもよいのではないか、というのが今の心境。先を見れば問題文が頭に入ってこないレベルの問題がまだまだ控えている。解説読んだってわからんぜ、ていうか読めないだろうな。

最終更新: 2020-06-15T20:02+0900

[AtCoder] AtCoder Beginner Contest 164E 問題 Two Currencies

日付のあたりに書いた通り解説PDFを読んで実装した。だけどあれ全然答えじゃないね。Chokudai さんのブログで以前読んだような、ちょっとひねってあるのをいかにして典型問題に落とし込むかというタイプの問題だったらしい。ある意味そこまで含めて典型では。でも一度も実装したことのないパターンだから「(現在の頂点, 所持している銀貨の枚数) を状態としてdijkstra 法を適用すると、(略) 解くことができます。」とだけ書かれても、~を状態とするってどういうことですか?

 提出 #12489199 (TLE / 2206 ms / 19760 KB)

Wikipedia の「ダイクストラ法」を読みながら雰囲気でPDFに書いてあった方針で実装しようとした。一応答えは出たがサンプル入力ですら一瞬の間を感じさせる激遅スクリプト。

N 個の頂点と銀貨の枚数を組み合わせて状態にするといっても、訪れなければいけない地点は依然として N 個のままなわけで、そのあたりの状態を集約する手つきが具体化できなかった。最終的に提出したスクリプトで「すべての地点を一度でも訪れた時点で完了」としたところとか、「銭なしの再訪に用なし」とコメントしたあたりがそうだと思うんだけど。

苦しんで何度か書き直すうちに原型を失いつつもすっきり書けて、プロファイルをとりながらの実行もすっきりだったから「どうだ!」と提出したら、AC の中1つだけが TLE で脱力。これ以上は無理ですよ。

この段階で他の人の提出を見た>「すべての提出 - AtCoder Beginner Contest 164」。

Ruby での全提出は1ページに収まるほどで、AC していたのは2人だけ。TLE 仲間の提出を覗いてみれば、自分が TLE になった入力(とサンプル)だけ AC していたりして、line_2.txt が何と癖の強い入力であることか。

 提出 #12498094 (AC / 205 ms / 14528 KB)

ダイクストラ法に立ち返らないといけないかと思っていたが、diff をとらないと判らないレベルのチューニングでなんとかなった。不思議。

要修正その1
M.times.map の .map がいらない。
.each の短縮形として .map と書くことがあるみたいだけど、.times (ブロックを受け取る)があるのでここではただの無駄。定数 E で map を受けていたときのなごり。
要修正その2
PQ#deq の変数名 max は min の誤り。
プライオリティキューが必要になるたびにこのとき(20190916p01)の max-heap を使った実装を書き換えて使ってるせい。必要になるのはほぼ min-heap。符号を反転させてそのまま使うのと手間はどっこいどっこい。

 ところで、Python (3.8.2) で今一番速いのがこれ>提出 #12430772 (140 ms)

すっごく読みやすいんだよなあ。何をやっているのか手に取るようにわかる(笑)。配列総なめが嫌だからって冗長なカウンター変数を用意するところまで。

自分に欠けていた工夫が2つあって、

  1. ある頂点から出る辺を予めソートしておいて、除外条件に一度引っ掛かれば以降の辺をまとめて無視してる。
  2. 効果のないちまちました両替をひとまとめにしてる。(ソートした辺がここでも役に立っている)

特に2番目は効果が大きいんじゃないかなあ。キューへの出し入れがボトルネックだから、エンキューをひとつ節約するごとにそこから波及する複数のエンキューが節約されるのは大きい。

それはそれとして、Python は AC だけに限っても5ページの提出があるのがうらやましい。傾向として判で押したように似たような提出が多くはあるが。理由のひとつはヒープ(データ構造)とかダイクストラ法とか、名前のついたアルゴリズムが簡単に利用できるところにある。

 Ruby (2.7.1) のこの提出>提出 #12467639

読めない記述がある。この行

  (v = V[n]&.&SM) ? (next if v>=s || v>2500) : R << [n,t]

演算子(に見えるがメソッド)をドット記法で呼び出せる(それが結合規則を変えるのでゴルフに使える)というのは読んだことがあって、たとえば 1&31.&(3) は同じ意味になる。でも &.& をどう解釈すればよいか。SM はただの数値変数だからブロック引数化の & ではないと思う。

他にもアロー記法だとか、暗黙のブロック変数(_1, _2 とか)だとか、Ruby 2.7 を読むには知識が足りない。ローカルにインストールしている Ruby 2.5 ではまだ使えない記法だったりする。まだ gem コマンドを一度も使ったことがないから、デフォルト添付ライブラリ(prime とか)の gem 化は歓迎できない

ブロック変数には悩ましいところがあって、.map(&f) とか .map(&:to_i) とか書けるときには積極的に書いていきたいんだけど、.to_i ではなく .to_i(2) を適用したくなると途端に .map{|_|_.to_i(2)} と書かなければいけなくなる。.to_i に 2 (と self)を予め束縛した関数がサッと(記述コストと実行コストなしに)利用できるといいんだけど、なかなかそうもいかないらしく、とりあえず .map{_1.to_i(2)} と書けますよ、ということ。たぶん。まだ試したことない。

 メソッド呼び出しで `.' の代わりに `&.' を使うことができます。この形式でメソッドを呼びだそうとすると、レシーバが nil の場合は以下のように働きます。

  • 引数の評価が行なわれない
  • メソッド呼び出しが行われない
  • nil を返す

&.& が何だったかと言えば、nil テストを含んだ & 演算だったと。Swift とか C# にあるやつじゃない? どっちも使わんしよう知らんけど。

 提出 #12550661 (AC / 154 ms / 14520 KB)

51 ms 縮まったけど本質的な改善ではないと思う(配列4とか比較が雑で適応が限られるし、ない方がいいかも)。シンプルさも失われていいことない。しかも Python (140 ms) に負けてる! Ruby のバージョンが 2.3 から 2.7 になって、実行前のオーバーヘッドが 40 ms ほど大きくなったと思うんだよなあ(それでも勝ちたい。ユーザー数で負けても質で勝ちたい)。

 参考にされた!>提出 #12916854 (146 ms)

嬉しい! 自分で解釈して手を動かして理解してる! 立派! 自分で好き勝手書くより他人の考えをトレースする方が難しいものよ。

タイムが縮んでるのはホットスポットである PQ#up_heap (PriorityQueue#update_heap_to_up) で配列アクセスを減らしてるからなんだろうか。キューが長くなるほど効果があると思う。

あと自分は意味まとまりのある変数群を一行で定義するために多重代入を多用するんだけど、実は字数が減るわけではないし、多重代入式に対応する配列値が作り捨てられているとしたら、もったいないことをしてる。

地味に変数の定義位置をずらして無駄な計算を減らしたりもしてる。自分は変数の定義をひとつにしたいがために効果のない値([0,0] とか)を使用して効果のない加算を実行してたりするんだけど、贅沢ではある。関連>20181029

 改善点みっけ

(自分の提出だよ)

	z, y = 2[v]+a, 3[v]+a # z < y
	if z < s
		c, d = s < y ? X[v][s-a,3[v]] : [0,0]

X[v] が返す関数が受け取る引数2つ(s-a3[v])はその差だけに意味があるから、両方に a を足して、X[v][s,y] とすると引き算1つと配列アクセス1つが省略できる。そもそもが引数が2つある冗長性から生じた無駄であるな。

こういう楽しみがあるのはスクリプトならではなんだよなあ。C++ コンパイラにかかると本質的でない差異は全部同じにされてしまう。そこに性能を犠牲にせずに読みやすい表記を追求する余地があるとも見られるんだけど。

 即セルフツッコミ「C++ コンパイラにかかると本質的でない差異は全部同じにされてしまう。」

もう一度asmコードをよく読むと不要なはずの配列の初期化が走ってる模様. デフォルトcstrは空のはずなんだけどと自分のコードを見直すと、FpDblクラスだけ配列の初期化が入っていた.

うっかりいれちゃっていた模様. 削除するとgcc-7.5で13%高速化. おおこいつのせいだったのか. それでもclang-8より4%ほど遅いけど気がすっきりした. でも配列の初期化で1割変わるというのは(clangは速いだけに)何か変なことしてるのかな.

プログラマに指示されたらコンパイラは無視できない(こともある? clang の場合をどう解釈する?)。結果に影響しない表面上はささいに見える違いが思わぬペナルティを生むことも。

 実装比較。この件>>20200428p01.07

  • 提出 #13001464 (1349 ms) 自分のプライオリティキュー実装を利用した richvote さんの提出。
  • 提出 #13001205 (1273 ms) 自分のプライオリティキュー実装を基にした? yappy0625 さんの実装を利用した richvote さんの提出。

プライオリティキューの実装が違うだけで、メインループは共通して richvote さんのオリジナル。

richvote さんの提出は、自分が最初唯一の TLE を食らった line_2.txt という入力が際立って他のケースより速いため、明らかに異なる部分に着目して探索の優先順位を決めている。

それはさておいて、俺の目には2つのプライオリティキュー実装に違いがあるとは見えないんだけど、俺の書き方の方が遅いという傾向が間違いなくあるようだ。

loop{} と書くより while 0; end と書く方が速いというように、気をつけておくと得する書き方がまだあるみたい。だけどわからん。

 多重代入と代入
require 'benchmark'

N = 10_000_000
Benchmark.bm{|x|
	x.report('多重'){ N.times{ a,b,c = 1,2,3 } }
	x.report('代入'){ N.times{ a=1;b=2;c=3 } }
}

これを Ruby 2.5 で実行してみた。

> ruby25 a.rb
       user     system      total        real
多重  1.591000   0.000000   1.591000 (  1.585992)
代入  0.967000   0.000000   0.967000 (  0.969697)

多重代入遅いなあ。(bm メソッドを bmbm に変更してリハーサルを行っても同じ結果)

あと最近驚いて、確かめてみたら Ruby 1.8 の昔から一貫して同じ挙動だったんだけど、多重代入の評価順って、単純に右辺から左辺とか、カンマで区切られた左から右ではないみたい。次のスクリプトの実行結果に驚いた。

i, a = 0, [0,1,2] # 準備
i, a[i] = 2, i # どうなる?
puts "i=#{i}; a=#{a.inspect}" #=> i=2; a=[0, 1, 0]

最初に右辺を評価して、それから左辺の評価と代入を左から順番に実行していく感じかな? 右辺の一時記憶が必要?

多重代入は遅くて時々評価順が難しい、というのが現在の評価。

 2.6 でデフォルト gem 化というのを読んだんだけど、普通に require 'prime' できる。gem 化されなかったのか、gem 化について勘違いしているのか。


2020年04月26日 (日) 面倒になった。もういいや。何も考えていないわけではなく何かを見ているようではある。俺は「おれたち(のコード)」なんて言われたら身震いするほどの嫌悪を感じるし、即座に「弱者の群れ」「ムラ社会化」「政治化」みたいなワードから負の面を想像するけど、そうやって覆うことで俺が見ることのできないところに何かを見ているようではある。■俺の視点。論理的な対話ができない、間違え続ける矛盾が「おれたち」を主張する「チーム」は雑談グループ以上のものにはなれないと見ている。判断を誤るし、有効な手を打てないだろう。有害無害を問わない何かではない、有効な手を。合意形成のプロセスも、知恵を集めるような議論も機能しないのだから、それなのに「おれたち」を語る者が他人に干渉し、また独善で物事を進めるのだから、船が山を登るようなことになるだろう。いや、山を登ってしまえるのはある意味個々が遺憾なく力を発揮した結果だからかつての姿かもしれない。まあいい。そういう、俺が呼吸できない混沌とした場でも労を惜しまない者、能力を発揮する者が内外にいるみたいだから、2割くらいの確率で命脈を保つ目があるかもしれない。知らんけど。俺は信じてないけど。■引っ込みがつかないように書いておく。もう口出ししない。自分が面倒くさい人間であることは嫌気が差すくらい知ってる。日記にも個人的なこと以外は書かない。つまり、不当な中傷が目に入ったら反論せずにはいられないから。でもそれだけ。GitHub のウォッチも解除した。俺は他の暇つぶしと自分だけのおもちゃを見つけた方がいい。■■■