最終更新: 2020-05-29T19:43+0900
数弱さんには厳しい回だった。E 問題は読む時間さえなかったので今日の日記は D 問題。次の整数式を考察するだけ。
x*A/B - x/B*A
A を掛けてから B で整数除算するか、B で整数除算してから A を掛けるかという違いで生じる値の差について。その最大。
違います。B を周期として第一項と第二項が一致します。A がその周期に与える影響はよくわかりません。
ちなみに B の上限は 10^{12} のため周期全体をテストすることはできません。>提出 #12633357
たぶんその通り。だけど説明を端折った N との関係がわかんなかったのと、A と B の因数によって第一項と第二項で周期 B の位相がずれていくんじゃないかという気がしたので探索した。>提出 #12640433。でも錯覚。位相がずれるなら「B を周期として第一項と第二項が一致します」が嘘じゃんねえ。
Ruby で提出している他の人は、提出の早さも実行速度も優秀だった。>すべての提出 - AtCoder Beginner Contest 165
実は 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 問題でも30分近く詰まっていた。A 数列の総当たりでいこうと決めるまでに制約条件を総当たりしようとしていて、他の制約にまったく制約されない孤立した制約条件の扱いをうだうだ考えていた。
再帰をループにするとかの効率を考えずにちゃっちゃと書いただけなので、提出へのリンクはなし。
上手い人のゲームプレイ動画と AtCoder の解説 PDF のあいだの共通点。多様性のなさ。へたくその動画の方がバラエティに富んでいて見ていて面白くさえある。間違え方というのは本当に千差万別で、ありとあらゆる機会を逃さずに、そう来るかと予想もできない脱線をする。たったひとつのゴールに向かう限られたルートに収斂していくということがない。
当人にとっては面白くもなんともないので、B 問題、C 問題に詰まらないような世界線に乗っていきたい。
chokudai(高橋 直大)🌸🍆 Verified Account @chokudai
とはいえ、高度な問題を解く時に、「floorが出てきたら整数部と小数部に分離して式変形！」って結構大切な考え方なので、Dみたいなのを出さないと、後半問題で突然そういう数学力が応用状態で問われることになるので、そのあたりの塩梅がむずかしいよね。
x が固定小数点数で小数部が５桁なら、x - x/100000*100000 が小数部分になる。……という話ではない？ D 問題を解くときの話？
以前にもはっとさせられたことがあった。
kを使った場合のコストは、k-1以下のすべてを使ったコストより高い
これって要は 100000 > 11111 (２進数) と同じことなんだけど、自分のような人間は「この一連の操作のコストは（書き換えた要素の数によらず）2^k である」という問題文を読んだだけではたどり着けなくて、上のように事実として示されて２進数で考えてみて初めて了解できることだったりする。
「一を聞いて十を知る(20200508)」ってこういうことだと思う。賢い人は「いやそれって同じことだから一の内に入るのでは？」と思うかもしれないけど、全然違うのである。
そして自分が AGC022C 700点問題 にまるで歯が立たない理由には、列挙された要素の数とそれらを煮詰める段階の深さに関係があると思ってる。「理解が及ぶ広さ、深さ、早さに優れ(20200508)」という風に書いたけども、そうでない自分は頭の中で抱えきれないし、整理して外に出して部分ごとに解決することもできない。
アストロノーカやテラリアですでに知ってるんだけど、ツリー状にねずみ算式に倍々に増えていく要求リソースの全体を把握すること、並列に進行する精製過程をストールさせないように需給を絶えず調整すること、このサプライチェーンの階層がある程度以上になると(たぶん３くらい)完全にお手上げになってしまう。そういう能力がない。
「たぶん３くらい
」 深さが３、二分木なら葉の数８までしか脳内で扱えないんです。
ちょっと検索したら「銀の格言」としてこんなのが列挙されてる。
つまりはこういうことなんでしょう？
chokudai(高橋 直大)🌸🍆 Verified Account @chokudai
「この問題だったらこうするだろ」って感じに無意識にやってることってめちゃめちゃ多くて、その「無意識」を言語化して列挙するだけでもめちゃめちゃ有効だと思うのよねえ。
chokudai(高橋 直大)🌸🍆 Verified Account @chokudai
「chokudaiのアルゴリズム格言1000」とか作って、こういうのをひたすら列挙しまくると、格言の組み合わせだけで良い感じに解ける問題がたくさんできそうだな、と思っていて、アルゴリズム名とは別レイヤーで浸透させたいな、ってちょっと思ってる。
「解説なんかだと、正しいルート以外はすっ飛ばされちゃう」というのがまさしく今日書いたことで(20200502p01.04)、解説PDFよりも「競技プログラミングの強みと「典型力」について - chokudaiのブログ」という思考の跡が見えるブログ記事の方が自分には有用となる理由。アルゴリズム格言に期待する理由。
この記事を書かれた方（ギフテッドの人）には、もしかして、自分の話を相手に理解してもらえなかった経験はあっても、相手の話が自分には理解できなかった経験が無かったりするんだろうか？」■quora に書いた人はたしかに「
でも実際に起きていることは、上のような「なんで何回も説明しないとだめなの」「なんで伝わってくれないの」というようなコミュニケーション不全による高IQ側の孤独さです。なぜ伝わらないのか、何がいけないのかと頭を抱えて涙している、そういうシーンです。」と、わかっている立場から書いているけど、同時に「
そもそも自分の日本語が間違っているかもしれない、自分のアイディアが頓珍漢なものかもしれないという恐怖感」が訪れるとも書いているし、また、「
馬鹿なことを言っているのは自分じゃないのか、人と満足に交われないのは自分の性格が悪いのではないか、と悩み苦しみ」と、弱い立場からも書いている。孤独な人間は自分の正しさを確かめるために他者を利用できない。自分で自分が信じられなくなったら狂人へまっさかさまだ。「一般人」に囲まれたときそういう恐怖の内にある。だから「相手の話が自分には理解できなかった経験が無かったりする」というのは想定される像から外れると思うのだ。quora の方で「
高慢ちきな高IQが「お前たち低能とは話が合わない」と吐き捨てるように告げるシーン」は実像に合わないと否定されているのだが、そのイメージに近づきすぎていやしないかと思うのだ。■『心を読みすぎる 心の理論を支えるワーキングメモリの心理学』(前原 由喜夫) という本を読んだ。「心を読みすぎる」というワードでは伝わらないと思うんだけど、この言葉に込められた意味は、他人の考えが自分にはよくわかっている、と考えているときこそ他人が見えていない、見えていないから(自己を投影しているだけだから)そう思えてしまう、というようなことだ。「ワーキングメモリ」というワードが quora の記事と共通している。quora の記事を書いた人は明らかに単純バカではないから、他人のことを理解しているなどと安直に思い込んで安心することはできないのではないか。だから確かめたいし歩み寄る努力をするんだけど、「一般人」の側があまりにも簡単に、「気持ち悪い」という言葉や「何言ってるの……？」という不審な目でもって、「意味不明な話をしている気味の悪いやつを排斥」してしまうのではないか。■伝える努力をしたくても、理解しよう受け止めようという姿勢を「一般人」の側が持てなければコミュニケーションは成立しない。「
「やばい、相手の言ってることがまるで自分には理解できない。どんなに説明されてもチンプンカンプンだ」という感覚」。やばいと感じているうちは大丈夫。「
「相手の言ってる事がまるで分からない」時、僕は、すごく惨めな気分になるし、相手に対する申し訳なさや負い目を感じます。」 この気持ちがあるなら大丈夫。でも一方が諦めて排斥して開き直ったら、どうしようもない。そういうことを quora の記事は書いているのではないか。■だから quora の記事がきっかけにすぎなかったとしても、十分に踏まえられていない感じが気になった。
最終更新: 2020-10-29T15:09+0900
解説 PDF で考え違いを教えてもらおうと思ったら解説動画しかなくて、うんまあ、じゃあいいや。(追記) 13日の現在はPDFもあるみたい。
これを読んでも間違っているとされている定義のどこに問題があるのかわからんのだよね。果たしてそれで解けるものか。>「競プロでよくある「バランスのとれた括弧列」の定義が壊れがちな話 - notブログ」
正規表現の ? を * に変えたことで、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 を連結する順番によって結果が変わる。)))( と )((( の２つの s があるとき、連結のしかたによって )))((( が残る場合と )( が残る場合に分かれる。)( を残した方が 'Yes' と答えられる確率が高くなる。
)( 型の文字列が１つだけのときに必ず No と答えてしまいそう。今現在 Ruby で一番速い提出は 498 ms だ。>すべての提出 - AtCoder Beginner Contest 167
再帰ありの正規表現(※矛盾した表現)を使ってる時点で勝ち目はない。左括弧の数が負になれないのに気をつけながら、左括弧と右括弧を対消滅させながら、左括弧と右括弧がいくつ残るかを数えればいいんだろうけども。
しかたない、省メモリを売りにしていこう。>すべての提出 - AtCoder Beginner Contest 167
ソートを必要としてないあたりで(※)ちょっとは有利を得てもよさそうなもんなんだけど、トップの提出はソート対象を )( 型に限るなどしてる。※ループ内で２要素のソートもあかんか？
( 型の文字列を最優先に、)( 型のうち ( 優位のものを優先的に、最後に ) 型を、という感じで連結していくのがストレートな解答らしい。
３つの型の文字列を統一的にソートすることもできるし、)( 型だけソートしてもいい。
自分はどれもソートしてないんだけど、)( 型の中から１番目と２番目に条件のいい文字列をピックアップするための比較演算()( 型の文字列１つにつき１～２回)が重くてソートした方が速い。
(ゴルフ勢を除けば)わりと短くてそこそこ省メモリで今のところ Ruby で一番速い。すべては正規表現エンジンとそれを使う gsub のちから。
やってる内容は最初の AC と変わらない。入力をがばっとひとまとめに処理するようにしたのと、最小２要素を取り出すのに一度全体を配列に蓄えてから min メソッドを使うようにしただけ。
対象者に正しく支給するには、世帯情報をまとめる住民基本台帳ネットワークの情報と申請時に入力された情報との照合が必要だ。世帯情報は自治体だけが持っているため、申請内容が正しいかどうか、職員が1件ずつ確認している。」 結局給付に必要な情報は自治体がほぼすべて持っている。「誰の給付金をどこの口座へ」という最後のピースだけに集中したい。■申請者のミスに対しては……。「
給付金は世帯ごとに世帯主が申請するルールだが、別世帯の祖父母の分まで合わせて申し込む間違いなどが目立つという。」「
手続き完了を知らせるメールが、「迷惑メール」に分類されて申請者が気付かず、区に問い合わせるといった別のトラブルも続き、職員が対応に忙殺されている。」 ポータルサイトとアプリがあるんだよね？ 自分で自分の間違いに気づけるよう情報を提供する仕組みがあって、基本は自助で、問い合わせがあってもそこへの誘導で済ませたい。でもすっごく難しそうではある>「マイナポータルで特別定額給付金の申請（と思ったら違ってぴったりサービス）」。個人の電子証明書をもっと手軽に活用できるインフラが整っていれば。「私は(電子証明書)です。(PIN を入力)。給付金を申請します」「私は(電子証明書)です。(PIN を入力)。現在のステータスを教えてください」で済ませたい。■@hosakanobuto「「電子申請」と聞けば、オンラインショップやチケット予約等のイメージで、まさか「電子申請」が届いてから自治体職員が、情報連結のない「住民基本台帳」を照合して一人一人確認作業をしているとは想像がつかないだろう。電子手続きは入口だけ。あとは「目視して確認」する必要があるとは信じがたい。」 理想と現実は主客が転倒しているようだ。理想では振り込み準備完了までの手続きがデジタルで完結していて、その作業を申請者本人にやらせるためにポータルサイトがあって、PC やスマホなどアクセス手段を持たない人の作業を代行するために郵送という抜け道が用意されていて、という風であってほしい。■ポータルサイト(１つ)が、自治体(複数)が持つ世帯情報を盗み見ることができてはいけないという制約がある？ 認証・認可の仕組みを使って申請者がポータルに権限を与えられないの？ でも自治体(複数)の側にアクセスを受け付けるインフラがないか。オフラインだったり専用ネットワークだったりするか。個々の自治体がデジタルでの処理能力を持つしかない。それでエントリーだけインターネットに開放する。だからポータルサイトが単なる認証代行になってる。でも今回のように特例的な制度をどう自動化する？ 人海戦術もひとつの選択だとして、自動化したときにポータルとどうやって連携できる？ 「住民基本台帳は門外不出だから手続きの内容や進捗をインターネット経由で見せることはできません」？ 「国民のプライバシーに配慮した結果だからしかたありません」？ まあ、お漏らしに対するゼロリスク願望はある。何か起これば自分が何かを得るために望んで受け入れたことではないと責める気持ちが予想できる。■マイナポータルを見てみたら「
行政機関などが保有するあなたの情報(世帯情報・税・社会保障等)を確認することができます。」って書いてあるね。インターネットで見られる。給付金については「
本サービスで特別定額給付金のオンライン申請が可能となりました。準備のととのった市町村より順次受付を開始しています。」という文言がある。これだと手作業で大変なところもある、みたいな話にも思えてくるけど、そう思いたいけど、自動化を阻むような気の狂った運用ルールがあっても驚きはしない。昔も今も人が安い国なのだ。■■■@2020-05-18 首長さんが自分とこの事例を踏まえて対応方針の大まかな分類と実作業手順などを。「なぜ10万円給付に時間がかかるのか｜東修平（四條畷市長）｜note」■現在の仕組みはデジタルデータを印刷した書類をやりとりする方法に最適化されている(業者がまるっと引き受けている)、みたいな感じ。マイナポータルから引き渡されるデータはユーザー入力部分が多くバリデーションの手間が余計にかかるだけみたい。自治体側の最適化っていうのがデジタル化によるものではなく業者を利用することによるものだっていうのが、過渡的であり解消されてほしいボトルネックである気がするなあ。デジタルデータを活用できるのがシステムを構築した業者だけであり、その業者は紙ベースのプロセスを支援する存在であるらしいから。でもこれって自治体側が仕事のやり方を変えると決めて、業者と共同作業でシステムとプロセスを構築していくのでないと、現在の形から抜け出すことはできないのではないか。
最終更新: 2020-05-26T21:01+0900
解説PDFが奮ってる。これが全文。
x 座標・y 座標それぞれを重複を除いてソートし，十分なサイズの2 次元グリッド上に各線分を刻 み込んでからBFS すれば，O(NM) 時間となって十分間に合います．
座標値(-10^9 以上 10^9 以下の整数)でなく座標値の序列(N個以下とM個以下)でグリッドを作るって発想が出てこないんだよなあ。
そんなこと知らずに、重なってる線分を連結して、交点を列挙して、閉路(多角形)を見つけ出して、包含関係を判定して、多角形の面積の引き算で求めようとしてた。しかも閉路の列挙に関するバグが取り切れなくて完成しない。完成しても間違いなく TLE(Time Limit Exceeded) だし。
名前が出てこないと検索も何もできないよね、この前の「逆元」「モジュラ逆数」みたいなもので(20191118p01)。自分は弧度法への変換だけして Ruby の Complex クラスに投げた(polar, 引き算, abs)。組み込みクラスなので使ってあげよう。
方針を教えてもらっても実装できるかどうかは別問題なわけで……。座標のグリッド化に際して線分の端点を切り詰め忘れて大量の WA。
２番目の提出はデバッグ出力を消し忘れて全部 WA だった。デバッグ出力を標準エラーに出すようにするといろいろ捗るらしいが。
線分の切り詰めバグを修正したら WA だったものがすべて AC か TLE になった。メモリ使用量が百数十MBを超えるテストケースがすべて TLE になっており、AC ケースのメモリ使用量は概ねそれ以下。無限ループ内でメモリリークでもないと思うから、単純に時間が足りないだけだと思いたい。
555 ms！>「すべての提出 - AtCoder Beginner Contest 168」
diff をとらんとわからんくらいの微修正で全部 AC。バグはなかった。
TLE になった手法はこのときの成功体験を再現しようとしたものだった>20191006p01。たぶん今回は問題の規模が大きすぎて裏目に出たんだろう。
Ruby で２人目の AC なのは嬉しいけど、こちらは 2489 ms もかかってるんだよなあ。ソースコードも長いし、メモリも余計に使ってる。早期に INF を判定して終了すれば一部のケースで速くなるかもだけど、最悪ケースの改善にはならないんだよなあ。事前にデータを作り込むんでなく、インテリジェントなアクセス関数を通して仮想的なデータにアクセスする手法ならレイテンシは下がりそう。スループットも下がりそうではあるが。そんなこんなより面積４倍のオーバーヘッドが効いてるんかなあ。
555 ms は驚異のタイムだよなあ。移動可能判定を検索でやってるのがまずダメなんだけど(メモリ使用量は減った)。
Python の AC 提出一覧がこちら>「すべての提出 - AtCoder Beginner Contest 168」 ほぼ一人の独壇場なんだけど、タイムの縮みかたがエグい。2488 ms から始まって 131 ms に至る。
「[AtCoder 参加感想] 2020/05/18:ABC 168 | maspyのHP」
さっきの提出は一から書き直して面積４倍確保を解消したけど、面積４倍のグリッドを作ったままでもグリッド線上を飛び越えて移動するようにすればデメリットは解消する。牛がグリッド線上にいる場合にだけ注意すれば。
特別な工夫は見つけられなかったけど、必要のないことはやってない印象。bsearch_index の使い分けが見事。
翻って自分のスクリプト。o を埋めたり、Infinity を埋めたり、座標丸め関数を４方向分用意したり、各グリッドの面積をすべて事前計算して記憶したり、省けるなら省きたいところに文字数と処理時間とメモリを費やしている。未熟で不安があるから冗舌になる。『テスト駆動開発』(ケント ベック)の表現を借りれば「ステップを刻む」「歩幅は変えられる」。今の自分は細かく刻まなければ進めないということ。
ぱくりです。写経。見比べて書いたわけではないけど、アイデアが同じなら同じになるでしょう。後で見たら PyPy3 で速い提出も同じ道具立てだった。
接続してる線分をまとめたり、交点のない線分を取り除いてからグリッドを作りたい気持ちがあるけど、見込まれる処理の重さに比して改善する度合いが入力依存でゼロになるとあって、何かのついでで棚ぼた的に交点一覧とグリッド座標化された線分一覧が手に入らないかなと夢想してる。
f(x) = f(x+B) ではなく「B を周期として第一項と第二項が一致します」という、感覚に基づいたふわっとした理解になる。精確さに欠けるし、残念なおつむで把握しきれる具体的で単純小規模の対象しか扱えない。
最終更新: 2020-05-31T18:32+0900
こんな非道な仕打ちがあるだろうか。
AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC AC WA AC AC AC AC AC AC AC AC AC AC AC AC AC
最初の提出(#13737796)が MLE と WA であって、コンテスト終了30秒前で MLE の解消はできたのだけど、ひとつだけの WA が WA のまま残ってしまったと。
600点問題は解ける解けないの山が最初にあって、どちらかといえば時間をかけてもほとんど解けないのだけど、それだけに恨めしい。
N の制約「0≤N≤10^5」 0 以上
どうしても完全丸ぱくりになるので提出する気がなくなったけど、N=0 の場合を特別扱いせずに対応できるようにループの中身を半分ずらしたり、配列 B を後ろから前から往復して値を埋め込んでいる処理を２種類の累計値を管理するだけで済ませたりできる。そうすると最後の答えを出すのに sum メソッドもいらない。