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