/ 最近 .rdf 追記 設定 本棚

脳log[2020-05-20~]



2020年05月20日 (水)

最終更新: 2020-05-26T21:01+0900

[AtCoder] AtCoder Beginner Contest 168F 問題 . (Single Dot)

解説PDFが奮ってる。これが全文。

x 座標・y 座標それぞれを重複を除いてソートし,十分なサイズの2 次元グリッド上に各線分を刻 み込んでからBFS すれば,O(NM) 時間となって十分間に合います.

座標値(-10^9 以上 10^9 以下の整数)でなく座標値の序列(N個以下とM個以下)でグリッドを作るって発想が出てこないんだよなあ。

さらにこんな工夫も。「F問題は座標圧縮してグリッドグラフ上のBFSにしたいんだけど、こんな感じで、線の幅(=0)のマス目を仮想的に作ってあげると、面積は4倍になるけど、線がマス目の塗りつぶしで表現できるかららくちんになるよ。 pic.twitter.com/ZpX0hxGQjC

そんなこと知らずに、重なってる線分を連結して、交点を列挙して、閉路(多角形)を見つけ出して、包含関係を判定して、多角形の面積の引き算で求めようとしてた。しかも閉路の列挙に関するバグが取り切れなくて完成しない。完成しても間違いなく TLE(Time Limit Exceeded) だし。

 C 問題が理由で「余弦定理」がトレンド入りしていたらしい。

名前が出てこないと検索も何もできないよね、この前の「逆元」「モジュラ逆数」みたいなもので(20191118p01)。自分は弧度法への変換だけして Ruby の Complex クラスに投げた(polar, 引き算, abs)。組み込みクラスなので使ってあげよう。

 F 問題。最初の提出 #13402510 (WA)

方針を教えてもらっても実装できるかどうかは別問題なわけで……。座標のグリッド化に際して線分の端点を切り詰め忘れて大量の WA。

 3番目の提出 #13404210 (TLE)

2番目の提出はデバッグ出力を消し忘れて全部 WA だった。デバッグ出力を標準エラーに出すようにするといろいろ捗るらしいが。

線分の切り詰めバグを修正したら WA だったものがすべて AC か TLE になった。メモリ使用量が百数十MBを超えるテストケースがすべて TLE になっており、AC ケースのメモリ使用量は概ねそれ以下。無限ループ内でメモリリークでもないと思うから、単純に時間が足りないだけだと思いたい。

 現在 Ruby で AC してる人が一人だけいる!

555 ms!>「すべての提出 - AtCoder Beginner Contest 168

 やったぜ! #13406078 (AC / 2489 ms / 50112 KB)

diff をとらんとわからんくらいの微修正で全部 AC。バグはなかった。

TLE になった手法はこのときの成功体験を再現しようとしたものだった>20191006p01。たぶん今回は問題の規模が大きすぎて裏目に出たんだろう。

Ruby で2人目の AC なのは嬉しいけど、こちらは 2489 ms もかかってるんだよなあ。ソースコードも長いし、メモリも余計に使ってる。早期に INF を判定して終了すれば一部のケースで速くなるかもだけど、最悪ケースの改善にはならないんだよなあ。事前にデータを作り込むんでなく、インテリジェントなアクセス関数を通して仮想的なデータにアクセスする手法ならレイテンシは下がりそう。スループットも下がりそうではあるが。そんなこんなより面積4倍のオーバーヘッドが効いてるんかなあ。

 面積4倍を解消しても…… 提出 #13413181 (AC / 1460 ms / 22892 KB)

555 ms は驚異のタイムだよなあ。移動可能判定を検索でやってるのがまずダメなんだけど(メモリ使用量は減った)。

Python の AC 提出一覧がこちら>「すべての提出 - AtCoder Beginner Contest 168」 ほぼ一人の独壇場なんだけど、タイムの縮みかたがエグい。2488 ms から始まって 131 ms に至る。

[AtCoder 参加感想] 2020/05/18:ABC 168 | maspyのHP

 面積4倍でも

さっきの提出は一から書き直して面積4倍確保を解消したけど、面積4倍のグリッドを作ったままでもグリッド線上を飛び越えて移動するようにすればデメリットは解消する。牛がグリッド線上にいる場合にだけ注意すれば。

 Ruby で 555 ms の人のスクリプトを読んだ。

特別な工夫は見つけられなかったけど、必要のないことはやってない印象。bsearch_index の使い分けが見事。

翻って自分のスクリプト。o を埋めたり、Infinity を埋めたり、座標丸め関数を4方向分用意したり、各グリッドの面積をすべて事前計算して記憶したり、省けるなら省きたいところに文字数と処理時間とメモリを費やしている。未熟で不安があるから冗舌になる。『テスト駆動開発』(ケント ベック)の表現を借りれば「ステップを刻む」「歩幅は変えられる」。今の自分は細かく刻まなければ進めないということ。

 提出 #13454965 (AC / 474 ms / 43092 KB)

ぱくりです。写経。見比べて書いたわけではないけど、アイデアが同じなら同じになるでしょう。後で見たら PyPy3 で速い提出も同じ道具立てだった。

接続してる線分をまとめたり、交点のない線分を取り除いてからグリッドを作りたい気持ちがあるけど、見込まれる処理の重さに比して改善する度合いが入力依存でゼロになるとあって、何かのついでで棚ぼた的に交点一覧とグリッド座標化された線分一覧が手に入らないかなと夢想してる。


2020年05月19日 (火) 適度な脱力感で読みやすい(しかし芯は骨太だ) SQL のランゲージサーバーを作った記録。ハイライトはここ>「私がパースしてほしいほとんどのタイミングで、パースエラーが出力されました。ほどなくして原因がわかりました。SQLで補完が必要なタイミングだと、大体クエリがSQLの構文としては正しくない状態になっているからです。


2020年05月18日 (月) 部屋にある。「「水だけ」なのに汚れが落ちる?不思議の水【アルカリ電解水】の真相に迫る | かずのすけの化粧品評論と美容化学についてのぼやき」■商品について理解したいのに、肝心なことが書かれていなくて、むしろ隠されていて、悪質な印象操作を感じさせる商品パッケージである。全然素性がはっきりしないのでリンクしたブログが代わりに断言してくれるのがありがたい。■強アルカリだから油汚れに強くて、アルマイトはてきめんに剥げて汚くなるので注意が必要で(違う商品だけど自転車のスプロケを洗ってたら黒のホイールが……)、ガラスに使うときはすぐに拭き取った方がいいのかな、という感じ。■実はあまり使い道がない。一番油で汚れるコンロのガラス天板は沸かしたお湯の残りをかけて拭き取ることをこまめにしてたらいつでもピカピカだし。


2020年05月17日 (日) いつも買ってるトマトだ。「生産品のご紹介/うれし野アグリ株式会社」■部位による味の違いはわからんけど、甘みが強く、水っぽいものがない。どれも宝石のごとく真っ赤で、大事にされてるなあと感じる。枝の匂いが好き。■最近は苺の季節でもあるけど、あれのパッケージングもひと手間かかってるなあと感心する。一段目と二段目に微妙にだけど差があるんよね。見栄えのいい娘が上の段で営業担当。送り出す親心?


2020年05月16日 (土) 弁護士費用特約のススメ。加害者にならない人にこそ必要。「交通事故の賠償金には3つの基準があるということをみなさまにはぜひ知っておいていただきたい。 その3つとは、「自賠責基準」「任意保険基準」「裁判所基準」だ。左から右に向けて金額が高くなる傾向にあり、特に慰謝料についてはこの3つのどれで計算を行うかによって金額が大きく変わってくる。


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 の記事がきっかけにすぎなかったとしても、十分に踏まえられていない感じが気になった。