脳log[2021-09-19～]

2021年09月19日 (日)

最終更新: 2021-09-23T19:26+0900

♪ [AtCoder] AtCoder Regular Contest 126

昨日の ABC に続いて今日は ARC があった。

昨日と同じく ABC の３完(+2WA)。24 時終了でもう 27 時になりそうだけどまだ結果が出ない……(水色に戻れたの？どうなの？)

A 問題 Make 10

脳内で組み合わせを全探索して優先順位を付けて貪欲法で>提出 #25984785。

B 問題 Cross-free Matching

LIS が見えていなかったせいで配列に対して insert/delete_at を繰り返す効率の悪い実装になったけど、通るは通った>提出 #25988002 (911 ms)。

LIS ではないこの解答の形は「Shortest Path on a Line」と「蛍光灯」で書いていた>20200826p02。

LIS にすると倍以上速くなってこう>提出 #26015260 (440 ms)。

C 問題 Maximize GCD

最初にサンプルの３にだけ答えを返すように if で処理を分けた。そうすると残りのケースで K の高すぎる上限を気にかける必要がない。

次に GCD について。砂で隙間を埋めるように１ずつの操作ができるとなると、GCD が取り得る値について A 数列の素因数から推測できることは何もないような気がしてくる。じゃあ探索しますか？

考えてる途中でなぜか +1 の他に -1 の操作もできるつもりになっていて WA>提出 #25992664。
-1 の操作に対応した部分を削除して AC>提出 #25993948 (1248 ms)。
C 問題も B 問題同様、制約と入力がガチガチに厳しくないのに助けられている。余分な log を削って 943 ms>提出 #26017330。

どうもね、N 回のループの中身を対数時間の処理にするということが、N^2 のループに対する高速化だという意識が強すぎて、N 回のループで前処理をして N 回の本番ループを定数時間で済ませる方が速いという感覚が持てない。N が２×N になってもオーダーは変わらないけど、ループを２本に増やすことに無意識の抵抗があるらしい。

D 問題 Pure Straight

残っていた 20 分で愚直解だけ>提出 #25995534。

RE と TLE の背後に WA が隠れている可能性がないではないが、「Shift and Inversions」でやったようにうまい遷移と、それと省略を見つけて高速化すればいいのかなと。

ツッコミを入れる

2021年09月18日 (土) [AtCoder] 精進。ARC065-D「連結」(青 diff)。出力部の直前４行の集計部分がキモ>提出 #25899408。必要なのは数だけであって、具体的な組み合わせを明らかにする時間的余裕は制約により与えられていない。結果だけ見ればシンプルだけどけっこう考え込んだよ。■■■[AtCoder] 今日はサイシードプログラミングコンテスト2021 (ABC219)だった。ABC の３完(+2WA)で大爆死の回。DP っぽい D 問題「Strange Lunchbox」が解けなかった。Ruby での AC はコンテスト終了直後の時点でゼロだ。わからん。E 問題「Moat」は盤面が 4×4 なんだからどうとでも処理できる。マス目ごとに堀の内部か外部かを決めて総当たりしても高々 65536 通り。そこから堀の内部が一塊になっていないものを除外する。つまり、堀の内部が連結ではない場合と、堀の内部の内部に堀の外部が島になっている場合を除外する。盤面が小さいから横着して添字をベタ書きした。でも時間内に書ききれなかった。終了後に AC>提出 #25962480。うーん。■D 問題もできた>提出 #25964674。うん、緑 diff なのもうなずける普通の DP だった。同じ形を書いたことがあるし、すらすら書けてバグも明らかなものがひとつだけ(pop と shift の取り違え)。だけど時間に追われると DP は普通に解けない。■F 問題の「Cleaning Robot」が面白そう。橙 diff だけど。K の制約が突き抜けていて予め無駄な努力を拒絶する親切仕様。ネタバレが許されないタイプの問題だと思う。自分でネタを掴みたい。■@2021-09-30 メモ。まず１サイクル巡回して通過点と原点との関係を角度(GCD(X,Y) で割った X 座標と Y 座標)ごとに絶対値(GCD(X,Y))で記録する。１サイクルごとに原点がどこに移動するかも記録する。重複(後追いと交差)を省いて K 回分数え上げる。どうやって？

ツッコミを入れる

2021年09月17日 (金) [AtCoder] 精進。ARC063-D「高橋君と見えざる手」(水 diff)。ちょっと似た問題が思いつかない不思議な問題。入力のうち T は未使用>提出 #25884205。出力部分を `p [Hi,Lo].min` としたけど、「Ai は相異なる」という制約を見落としていた。それなら Hi と Lo の数は必ず一致する。だから簡単になってこう>提出 #25884286。ああ、このメモしながらスキャンするだけの水 diff には覚えがある。AtCoder じゃんけんだ>20210830。今の ARC だと A 問題(茶 diff)でもこれより難しいよ。これとか>「Many Formulae」。メモしながら一度スキャンするだけなのは同じなんだけど>提出 #23369338。

ツッコミを入れる

2021年09月16日 (木) 「信号無視で検挙も不起訴→「ブルー」の免許で更新されたとしてゴールド求め提訴：バイク速報」■これ、まとめ内でも理解してないコメントがいくつもあって、自分も知らなかったのだけど、サインしないで裁判沙汰にして不起訴(起訴猶予)になったけど点数は引かれてました、っていう経緯みたい。勝ったと思ってたら負けてた、みたいな。それはわからんで。■「起訴猶予とは？不起訴・無罪との違い | 弁護士法人泉総合法律事務所」不起訴になる理由に３種類あるらしく、嫌疑なしと嫌疑不十分と起訴猶予。この件は起訴猶予。起訴猶予とは「犯罪を犯したことを裁判で証明できるが、被害が軽微である、示談ができて被害者も許してくれた、社会的制裁を既に受けている、深く反省しているなどの諸事情を総合考慮して、今回は起訴を見送るという判断」らしく、これだけ読めばお目こぼししてもらえてラッキーだったねという印象だけど、ラッキーだったとは考えられない理由が２つある。１つ目は、そもそも信号無視程度の違反は罰金案件ではないから不起訴という結果はプラスの結果ではないのではないか、ということ。２つ目は、「犯罪を犯したことを裁判で証明できる」というのは検察官の見込みであって裁判を経た裁判官の判断ではないということ。だから起訴猶予でも嫌疑なしでも不起訴は不起訴であり罪はまだ存在しない。■さて、反則金で済ませられるところを裁判沙汰にして罰金案件にして、おそらく二重に課せられることはないだろうからこの時点で反則金の支払いは免除されてると思うが、不起訴の結果で罰金の支払いも回避できたけど、なぜか違反の事実は消えず点数が加算(減算)されていた。これをどう考えればいいか。合理的な説明できる？裁判所にいったんエスカレーションした案件で点数だけが反則金(罰金)とは別口で処理されてるように見えるんだけど、これは矛盾では？矛盾ではないというなら存在する違反に目をつぶった検察官の恣意か、存在しない違反に対して点数を引いた警察の恣意か、どちらかを権力の乱用・私物化として問題視するほかないと思う。実際問題、起訴猶予を選んで公判を開かない、(まかり間違っても)前科を付けないという検察官の判断は裁量の範囲で妥当なものだと思う。そして警察は、(理由や思惑によらず忖度せず)不起訴という事実を以て行政処分をあきらめるのが筋の通し方だろう。だって起訴猶予でも不起訴を、推定有罪扱いはできないでしょう。コメントによれば不起訴で点数を戻す警察もあるらしいし、それが当然だと思う。京都府警の主張では行政処分は警察の管轄ということらしいけど、反則金制度が運転者に二重の処罰を受けさせるために存在しているとでも？(そうなの？) まさか司法判断を虚仮にする自虐趣味はないと思うが、地裁判決が狂ってることはまれによくあるので、京都地裁の判断を期待して待ちたい。

ツッコミを入れる

2021年09月15日 (水) [AtCoder] 精進。ARC073-D「Simple Knapsack」(水 diff)。タイトルに騙されて制約も見ずに DP 用の配列を大きさ W で確保しようとしたら、サイズ１ギガの配列は大きすぎると Ruby に怒られた。Simple とは……。難しく考えて再帰関数で 64 ms の提出(#25855795)を作ったのだけど、これって DP からの退行では？ Ruby のバージョン違いによるオーバーヘッドの差があるからそのままの数字を比較できないけど、連想配列で普通に DP をしても 30 ms で済んでいる>#11970957。そしてこちらのこの方は自分と同じく DFS を採用してらっしゃる>#25853638 (今日の提出)。AtCoder Problems で Ruby による最近の提出一覧を見て今日の一問を選んだのです。中身までは見てなかったので似てるのは問題から導かれる必然であり偶然の結果です。違うところは、ある重さのアイテムの採用数を一定レベルより下げても、他の重さのアイテムの採用数が上限に達して増やせなくなるポイントがあるので、その均衡点を見極めてループを打ち切っているところ。それが難しく考え過ぎだっていうんだけど、想定解が 400^3 のループで Ruby 勢を虐殺した ABC-D の恨みが記憶に新しいせいなんだよなあ。

ツッコミを入れる

2021年09月14日 (火) [AtCoder] 精進。ABC022-D「Big Bang」(青 diff)。２つの点集合を平行移動して回転させて縮尺の比を求める問題。最近あった座標問題２題「Congruence Points」「ほくろ」とは違って、個々の点の座標を一致させる必要はない。座標変換の具体的なパラメータを探索することが許されている制約でもない(2≦N≦10^5)。直径だけわかれば十分。しかし、どうやって？テキトーに並べてテキトーにいくつか距離を計って最大値を選んだら通りましたよ>提出 #25850608。提出一覧から１つ２つ他の人のを覗いたら、重心からの距離の最大値を使っているみたいだった。重心は Congruence Points でもキーになっていたのに、また気が付かなかった。これはいけない。頭の悪さを晒しているぜ。役に立たないときに限って重心を持ち出している>20210406p01。■ところで今気が付いたけど、この回の ABC って 100 分でなく 120 分だ。途中までそうだったんだろうか。今は４問が６問になって、さらに難しい２問が追加されて、全８問で 100 分だよ。

ツッコミを入れる

2021年09月12日 (日) [AtCoder] 精進。ちょっと前の ABC215-E「Chain Contestant」(水 diff)。当日にこう書いている>「今日の感じだと E 問題 F 問題が解ける世界線はそう遠くないと思えるんだけど、つまりは、解けなかったってことなんだな。E 問題で TLE 解が作れただけ」。実際、日を改めれば解けるんだよ>提出 #25816607。それに、166 ms でだいぶイケてると思う>Ruby によるすべての提出。これを本番でだね……。■調子に乗って考え方を書いておこう。現在の状態をどうクラス分けできるか。これまでに出たコンテストの集合と最後に出たコンテストの種類のペアで分けられる。それだけが区別できれば十分。それが `D = Array.new(11){[0]*(1<<10)}` の部分。幅 10 のビットフラグが 10+1 個分。コンテストの種類は 10 なんだけど、余分な +1 を 10 個の合計の記録用に確保した(`Ds = D[-1]`)。というのは、最後に出たコンテストの区別は現在のコンテストと同じか異なるかという二値で十分なのに、異なるものが９個に分かれてると集計が面倒だから。あとはコンテストの回を追って、参加した場合参加しなかった場合を数えていくだけ。■これは自分が DP を知らなかった昔に DP と知らずに書いたのと同じ形>20120214p01.02。Project Euler の 191 問目だった。

ツッコミを入れる

2021年09月11日 (土) [AtCoder] 今日は ABC218 の日だった。本番で青 diff 通したいねえ。F 問題「Blocked Roads」がそう。N の３乗が通らないだろうとは制約から読み取っていたけど、普通に BFS を繰り返すだけで通ったのが拍子抜け>提出 #25793701。なんだよー(まじめに書くと、繰り返しの上限が辺の数 M(≦N*(N-1)/2) ではなく最短経路の辺の数(≦N-1)だということが見抜ければ意外ではない)。だからと言って惜しかったとは感じないし悔しくもないけど。■ RE と WA を繰り返した最初の方針でも AC まで行けた>提出 #25812833。ちょっとした沼にはまっていたんだな。E 問題を通してから終了までのおよそ１時間のあいだ。

ツッコミを入れる

2021年09月10日 (金) 朝日新聞デジタル「300億年で1秒しかずれない極めて正確な光格子時計を開発した。従来の原子時計をはるかに超え、1秒の定義に採用される可能性もある。重力が大きいほど時間の進み方が遅くなるという相対性理論の効果を利用して、十数メートルの高低差まで検出できる。」すごい！スケールが不明で何がすごいのか全然わからない！(十数メートルの高低差が認識できない人類おる？)■それはそれとして、ちょっと前に『精密への果てなき道シリンダーからナノメートルＥＵＶチップへ』という本を読んで、世界を計る解像度の向上は文明の発展度合いを示すわかりやすい尺度になるなあと思ったのだった。まる。知識と発展の源泉であるよ。

ツッコミを入れる

2021年09月09日 (木) [AtCoder] 精進。ABC036-D「塗り絵」。すごく難しかった>提出 #25696587。解答の形も式もほとんど 20210624 で解いた競プロ典型90問の「073 - We Need Both a and b（★5）」と同じ。というかあちらがこちらと同じ。だけどやっぱり難しかった。解説なしで解けたのだけが進歩か。これが昔の ABC の D 問題でギリギリ青色だってんだから、解かれすぎでは？自分が苦手にしてるだけか。典型の方も★５つで中程度の評価だもんな。

ツッコミを入れる

2021年09月08日 (水) [AtCoder] 精進。この前の ABC217-F「Make Pair」。マイメロ(？)が「これ、ほぼ先週のFと同じってマイメロのママが言ってたよ https://t.co/31te6MkVI2」といって競プロ典型90問の「019 - Pick Two（★6）」をポイントしていたので、自分の提出(#22879312)を参考にして取り組んだ。2 WA、3 TLE のち AC>#25683515。おかしい、一度解いた問題が身になっていない。そんで、再帰関数で制限時間ぎりぎりだけど、DP 化するとだいぶ速いみたい。できませんけども。

ツッコミを入れる

2021年09月07日 (火) 「マジックナンバー使うな? どんどん使え! - Qiita」■これって逆張りに行っているようでやってることの実質はマジックナンバーの定数化と同じだよね。`x0.10m` を `x税率` にするのも `消費税額(x)` にするのも、名前を付けているという点で同じ。名付ける対象がデータか手続きかという違いはあるし、それを定数で定義するか関数で定義するかという違いもあるけど、static メソッドでアクセスするシングルトンオブジェクトがグローバル変数と同じなのと同じ程度には同じ。■２つあるブコメにもそれぞれ一理はあって、「変更があるものは定数化した方がいい気がします.....」は、それはそう。ただし設定項目の一部であったりしてプログラムとは別のサイクルで変化する場合や、変更が複数箇所に及ぶ場合に当てはまる話であって、同じソースコード上にある現状であれば、定数定義を１か所変更することになるか関数定義を１か所変更することになるかという違いは、どうでもよくない？「例がよくない。例示している消費税率はソースの至る所に存在するようになり、定数化しておくと法律が変わり修正が必要なときに修正漏れを抑えることができる。1度しか使わない値を定数化など何でもするはよくない。」というのも、それはそう。当たり前のことをこの記事に対してコメントするのはなぜか。たぶん記事の中の `消費税額` 関数を否定はしていなくて、だけど `0.10m` というマジックナンバーを利用する場所が絶対に `消費税額` 関数１つにとどまらないだろうことを見越して「例が良くない」と言っているのだと思う。

ツッコミを入れる

2021年09月06日 (月) アルノサージュ(PS3)クリアした。アルトネリコ１もそうだったけど、けっこう特異なヒロインを造形するよね(見た目じゃなくて)。好き。

ツッコミを入れる