最終更新: 2021-11-04T10:11+0900
精進ですよ。おとといあった ABC の F 問題。
コンテスト時間中は木の中心についての理解がぼんやりで解答に至らなかった。そもそも木の中心などというものを考えたことがなく、でもサンプルの２のような円形の木で制限時間内に答えを数えきるためには、木の中心を中心とした組み合わせを考えるしかなかった。
木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を２度呼び出して答えとしたことがあった。後にそれが運任せではなく確かな手段らしいことを知った。証明は知らない。
木において辺とは頂点集合を左右に分けるものだということを知っている。どの辺でもいいので１本選んで真ん中に横向きに置いて形を整えるとアレイ(亜鈴)型になるイメージ。コンテスト中には思い出せなかった。そのせいで問題の木を具体的にイメージする力が弱かった。このことは今朝のトイレで考えるでもなくふと思い浮かんだ。
たとえば直径が偶数の時、直径の中心には頂点が１つある。問題は直径を与える頂点ペアが複数あるときに中心が複数あるかどうか。中心が仮に２つあるなら、２つの中心の中点が本来の中心であるべきであり、直径だと思っていたもの、２つの中心だと思っていたものは直径でも中心でもなかったことになる。だから中心は１つ。
たとえば直径が奇数の時。直径の中心には１本の辺がある。この辺は中心に位置する唯一の辺だろうか。仮に直径の中心に位置する辺が２つあるなら、２つの辺の中点が本来の……(略)。だから中心は１つ。
色の塗り方だけど、中心から最も遠く半径と同じだけ離れている点の集合を、中心から直接出るどの頂点の先にあるかで分類する(中心が辺なら辺が結ぶ２つの頂点を考える)。同じ頂点の先にぶら下がっている２点を同時に塗ってしまうと、そのあいだの距離は必ず直径よりも短くなる。直径より長くなることはありえないし、仮に直径と等しくなることがあるなら、真の中心はどこだ？という話になる。そんなものはない。
ここまでを今朝のうちに納得してから実装したのに、直径が偶数のケースで中心の求め方を間違えたり(提出 #26352819)、線形時間の集計を繰り返して TLE になったり(提出 #26353052)、無駄に長さ N の配列確保を繰り返して TLE になったり(提出 #26353383)、いっぱい間違えた。
配列アクセスとハッシュ表アクセスだと配列の方が断然速いのだけど、初期化が１度で済まないなら、ハッシュ表の初期化コストの低さが効いてくるみたい。
８問目の黄 diff AC。これより上は橙が１問だけだから、かなりのレア度なんだ。
ちなみに 水 diff だった E 問題 LEQ は、まだ TLE を回避する計算方法がわかっていない。
さっき書いた。
木の直径については知っている。(中略)。証明は知らない。
木の中心を念頭に置いて考えると直径を求めるアルゴリズムはこういうことだ。中心は、頂点の場合も辺の場合もあるけど、頂点集合を左右のどちらか(もしくは中心から直接出る辺のどれか)に振り分ける。任意の１点を始点に選んで最も遠い頂点を求める１回目の探索は、中心を挟んで異なる側にある、中心から最も遠い点を求めている。２回目の探索も同じ。同じ側に属する点が最遠点として選ばれることがないのは、中心に寄り道するパスを想定して比較材料にするとわかる。２回の探索で見つかったどちらの頂点も中心からは半径分だけ離れているから、そしてお互いに異なる側にあるから、合わせて直径になる。
さっき書いた。
木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を２度呼び出して答えとしたことがあった。
エディタのログから「.max_by」を GREP したら該当するファイルが(たったの) 15 見つかったので、順番に調べてみた。「ある問題」とは ARC022-C「ロミオとジュリエット」だった。これが青 diff なんだからチョロい！(嘘です。調子乗りました)
ボーナス込みの得点合計÷問題数 でソートして効率のいい方から総当たり(打ち切りあり。残りスコアの合計からと得点効率から計算する最小値更新の見込みから)。問題の解き方は問題群単位で全部解くか１問も解かないかスコアを満たせるだけ解くかの３パターンしかない。制約がたいへん控えめなので解法もバラエティに富んでいる印象>Ruby によるすべての提出。と思ったらほとんどがビット全探索で DFS が少々、といった感じ。DP はダメだったか。たしかに、全部解くか残スコア分だけ解くかの２択に対して p 回繰り返すループは、それが無理な制約ではないにしても無駄が多い。A space-separated list of URLs. When the link is followed, the browser will send POST requests with the body PING to the URLs. Typically for tracking.」 もちろん User-Agent たる Firefox はユーザーが望まない動作を行わないオプションを用意してくれるものと信じている。■まじであった。「Firefox 3 で対応が追加、但し既定では有効化されていない (browser.send_pings の設定で隠蔽)。」 けっこう古くからあったみたい。古すぎて、今でもこの設定が参照されているかは要確認だけど。
最終更新: 2021-12-21T16:21+0900
昨日あった ABC。今回は全体に易化傾向で、D 問題がやるだけの茶 diff。F 問題でも水 diff。実は F 問題より E 問題の方が解かれていないけど、そちらも水 diff の範囲。ABC は５完６完を狙いたいところなんだけど、ABCD を 17 分４完(+うっかり余りをとり忘れて 1 WA)でレートは微減。あなたは残りの 83 分間何をしていたのですか？
こちらが先に解けた。やり方はすぐにわかる。１か所だけ素直に求めて、あとは辺の左右にあるノード数の差を見ながら差分を更新する。すぐに実装できたかというとそうはいかない。どういう処理をどういう順番で並べると答えが次々生み出されてくるのか、とっかかりが掴めなかった。結局、根を１つ決めると木に深さという概念が生まれて、根の深さを０にしておくと全頂点の深さの和が根にとっての答えになった。これがとっかかりになって最後まで書けた。
木の問題は深さと距離と子孫がそれぞれ Depth, Distance, Descendant なもんだから、いつも D が識別子として不足して困る。それに直径(Diameter)も追加で(ちなみにアクセントは i でも e でもなくて a らしいですよ)。
83 分間合わないサンプル２を合わそうとしていました。明らかに同じような計算がノードごとに繰り返されるので、累積和の累積和を表引きして TLE を避けるのだと思っていた。ところが実際は一番内部の式が定数になったので(たとえば 2^a × 2^{N-a} が a の値によらないようなこと)、愚直解だと思っていたものがそのまま答えだった。
しかしその愚直解を合わせるのにも一生分の時間がかかるように思われた。死ぬ前に解けて良かった。３つくらい勘違いポイントがあった。組み合わせを半分(それとも２倍？)扱いしなければいけないのはどういうケースか(同じ深さの２頂点を組み合わせて距離 D を作る場合ではない)、それは頂点何個分か(N,D に足し引きして求まる数ではないし冪(数)でもない)。
余りをとる数え上げ問題は正答までの距離が計れなくて途方に暮れがち。
愚直解っていうのは、深さごとに、頂点がいくつあるか、頂点１つが相対的深さ D の頂点をいくつ持っているか、相対的深さ 1 の頂点と D-1 の頂点をいくつ持っているか、相対的深さ 2 と D-2 ならいくつか……を数えて掛け合わせて足し合わせること。
E 問題も F 問題も青 diff でいいじゃないかというくらい苦労したけど、振り返ればどちらも考察は要求されていない(「すぐにわかる」「愚直解」)。ある意味やるだけの問題だった。やるだけ(できるとは言っていない)。
最終更新: 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。
犯罪を犯したことを裁判で証明できるが、被害が軽微である、示談ができて被害者も許してくれた、社会的制裁を既に受けている、深く反省しているなどの諸事情を総合考慮して、今回は起訴を見送るという判断」らしく、これだけ読めばお目こぼししてもらえてラッキーだったねという印象だけど、ラッキーだったとは考えられない理由が２つある。１つ目は、そもそも信号無視程度の違反は罰金案件ではないから不起訴という結果はプラスの結果ではないのではないか、ということ。２つ目は、「
犯罪を犯したことを裁判で証明できる」というのは検察官の見込みであって裁判を経た裁判官の判断ではないということ。だから起訴猶予でも嫌疑なしでも不起訴は不起訴であり罪はまだ存在しない。■さて、反則金で済ませられるところを裁判沙汰にして罰金案件にして、おそらく二重に課せられることはないだろうからこの時点で反則金の支払いは免除されてると思うが、不起訴の結果で罰金の支払いも回避できたけど、なぜか違反の事実は消えず点数が加算(減算)されていた。これをどう考えればいいか。合理的な説明できる？ 裁判所にいったんエスカレーションした案件で点数だけが反則金(罰金)とは別口で処理されてるように見えるんだけど、これは矛盾では？ 矛盾ではないというなら存在する違反に目をつぶった検察官の恣意か、存在しない違反に対して点数を引いた警察の恣意か、どちらかを権力の乱用・私物化として問題視するほかないと思う。実際問題、起訴猶予を選んで公判を開かない、(まかり間違っても)前科を付けないという検察官の判断は裁量の範囲で妥当なものだと思う。そして警察は、(理由や思惑によらず忖度せず)不起訴という事実を以て行政処分をあきらめるのが筋の通し方だろう。だって起訴猶予でも不起訴を、推定有罪扱いはできないでしょう。コメントによれば不起訴で点数を戻す警察もあるらしいし、それが当然だと思う。京都府警の主張では行政処分は警察の管轄ということらしいけど、反則金制度が運転者に二重の処罰を受けさせるために存在しているとでも？(そうなの？) まさか司法判断を虚仮にする自虐趣味はないと思うが、地裁判決が狂ってることはまれによくあるので、京都地裁の判断を期待して待ちたい。