最終更新: 2021-09-30T13:08+0900
制約上の上限が 16 桁だっていうから、f の値の上限も 16。たとえば f(x) = 5 のとき、x は 11111 であるかプリフィックスが 111110 であるかのどちらか。f の値ごとに N 以下の範囲にそういう x が何個あるかを数える。桁数を固定すれば数えやすい。提出 #26096008
競プロ典型90問「025 - Digit Product Equation（★7）」の簡単バージョン。
頭の中がぐちゃぐちゃで解けなかった。終了直前の提出がこれ>提出 #26101512 (1 WA)。
とってもくやしいことに、１文字書き換えたら通りましたとさ>提出 #26105189 (AC)。２行目の N==1 を L==1 にしただけ。なんだよもー。もーもーもー。
一応考えたことを。最小化したい最大値の先頭の桁は２で決まっている。その後ろに０から N-1 までの N 個の数を３進数で表記したものをくっつける。これが２から始まる N 個の数。０から始まる N 個の数と１から始まる N 個の数は、桁ごとの制約を満たすようにテキトーに決める。これだけ。なんで書けへんの？ 他の人の提出を見ると tr で 0,1,2 をローテーションするのが簡単そうだった。簡単にできることをすごく難しく考えていた。
驚いたことに、このふがいない有様でレートは上昇しているのである(☞)。どれだけ低いレートに甘んじているかわかろうというもの。
最終更新: 2021-09-23T19:26+0900
昨日の ABC に続いて今日は ARC があった。
昨日と同じく ABC の３完(+2WA)。24 時終了でもう 27 時になりそうだけどまだ結果が出ない……(水色に戻れたの？どうなの？)
脳内で組み合わせを全探索して優先順位を付けて貪欲法で>提出 #25984785。
LIS が見えていなかったせいで配列に対して insert/delete_at を繰り返す効率の悪い実装になったけど、通るは通った>提出 #25988002 (911 ms)。
LIS ではないこの解答の形は「Shortest Path on a Line」と「蛍光灯」で書いていた>20200826p02。
LIS にすると倍以上速くなってこう>提出 #26015260 (440 ms)。
最初にサンプルの３にだけ答えを返すように if で処理を分けた。そうすると残りのケースで K の高すぎる上限を気にかける必要がない。
次に GCD について。砂で隙間を埋めるように１ずつの操作ができるとなると、GCD が取り得る値について A 数列の素因数から推測できることは何もないような気がしてくる。じゃあ探索しますか？
どうもね、N 回のループの中身を対数時間の処理にするということが、N^2 のループに対する高速化だという意識が強すぎて、N 回のループで前処理をして N 回の本番ループを定数時間で済ませる方が速いという感覚が持てない。N が２×N になってもオーダーは変わらないけど、ループを２本に増やすことに無意識の抵抗があるらしい。
残っていた 20 分で愚直解だけ>提出 #25995534。
RE と TLE の背後に WA が隠れている可能性がないではないが、「Shift and Inversions」でやったようにうまい遷移と、それと省略を見つけて高速化すればいいのかなと。
p [Hi,Lo].min としたけど、「Ai は相異なる」という制約を見落としていた。それなら Hi と Lo の数は必ず一致する。だから簡単になってこう>提出 #25884286。ああ、このメモしながらスキャンするだけの水 diff には覚えがある。AtCoder じゃんけんだ>20210830。今の ARC だと A 問題(茶 diff)でもこれより難しいよ。これとか>「Many Formulae」。メモしながら一度スキャンするだけなのは同じなんだけど>提出 #23369338。
犯罪を犯したことを裁判で証明できるが、被害が軽微である、示談ができて被害者も許してくれた、社会的制裁を既に受けている、深く反省しているなどの諸事情を総合考慮して、今回は起訴を見送るという判断」らしく、これだけ読めばお目こぼししてもらえてラッキーだったねという印象だけど、ラッキーだったとは考えられない理由が２つある。１つ目は、そもそも信号無視程度の違反は罰金案件ではないから不起訴という結果はプラスの結果ではないのではないか、ということ。２つ目は、「
犯罪を犯したことを裁判で証明できる」というのは検察官の見込みであって裁判を経た裁判官の判断ではないということ。だから起訴猶予でも嫌疑なしでも不起訴は不起訴であり罪はまだ存在しない。■さて、反則金で済ませられるところを裁判沙汰にして罰金案件にして、おそらく二重に課せられることはないだろうからこの時点で反則金の支払いは免除されてると思うが、不起訴の結果で罰金の支払いも回避できたけど、なぜか違反の事実は消えず点数が加算(減算)されていた。これをどう考えればいいか。合理的な説明できる？ 裁判所にいったんエスカレーションした案件で点数だけが反則金(罰金)とは別口で処理されてるように見えるんだけど、これは矛盾では？ 矛盾ではないというなら存在する違反に目をつぶった検察官の恣意か、存在しない違反に対して点数を引いた警察の恣意か、どちらかを権力の乱用・私物化として問題視するほかないと思う。実際問題、起訴猶予を選んで公判を開かない、(まかり間違っても)前科を付けないという検察官の判断は裁量の範囲で妥当なものだと思う。そして警察は、(理由や思惑によらず忖度せず)不起訴という事実を以て行政処分をあきらめるのが筋の通し方だろう。だって起訴猶予でも不起訴を、推定有罪扱いはできないでしょう。コメントによれば不起訴で点数を戻す警察もあるらしいし、それが当然だと思う。京都府警の主張では行政処分は警察の管轄ということらしいけど、反則金制度が運転者に二重の処罰を受けさせるために存在しているとでも？(そうなの？) まさか司法判断を虚仮にする自虐趣味はないと思うが、地裁判決が狂ってることはまれによくあるので、京都地裁の判断を期待して待ちたい。
D = Array.new(11){[0]*(1<<10)} の部分。幅 10 のビットフラグが 10+1 個分。コンテストの種類は 10 なんだけど、余分な +1 を 10 個の合計の記録用に確保した(Ds = D[-1])。というのは、最後に出たコンテストの区別は現在のコンテストと同じか異なるかという二値で十分なのに、異なるものが９個に分かれてると集計が面倒だから。あとはコンテストの回を追って、参加した場合参加しなかった場合を数えていくだけ。■これは自分が DP を知らなかった昔に DP と知らずに書いたのと同じ形>20120214p01.02。Project Euler の 191 問目だった。