結果
Aのみ 1完 50:22 (+0ペナ) Performance: 1395, Rating: 1321 -> 1329
前回 ABC で冷やしていたが、今回は微増
感想
ARC はもともと苦手意識がある。 A 問題から結構難しいし、B 問題解ける確率は 5 割あるかも怪しい気がしていたので結構レート的に厳しい展開になることが多そうだなあと思っていた。
しかし、前日の ABC は私用で出られないことが決まっていたし競プロモチベが上がっている今 rated で出られるコンテストに出ないというのももったいないと思ったので ARC 173 は出ようと思い、週はじめから少しずつ ARC 過去問を解いて対策していた。
案の状、A から結構苦戦するし B はだいたい難しいし、C に至っては現状解く気すら起きないが、コードを書けない移動中などに延々と脳内 ARC (考察だけ) とかやっていると、そのうちなんだか ARC の問題も面白いかもしれないぞという気がしはじめていた。
A
K 番目の "Neq Number" (桁表示の数字が隣接しない数字) を求める。
Writer が同じ chinerist さんということで、直前に A - Periodic Number を解いていた (デバッグ終わってなかったけど...) ので、なんだか見た瞬間似てるなあと思った。
問題文読んでいきなり、11739090 って Neq Number じゃなくない (1 が連続してる)?? って思って困惑したけど、誰か質問するだろうし、まあとりあえずサンプル合わせにいけばいっかと思って放置 (結局誰も指摘しないの...)。
桁 DP っぽい感じはわかって、その上で "K 番目の Neq Number" より、"M 以下の Neq Number の個数" のほうが桁 DP 的に楽そうだなあと思ったので、"M 以下の Neq Number の個数" を O(log M) で求めて二分探索でいっか、とそこまで大きく迷わず決まる。
桁 DP で考えると基本各桁になにがしか数字が入っていてほしいので、便宜上最上位より上は 0 埋め相当で考えていたが Neq Number 的には最上位に 0 が隣接してても "同じ数字が隣接してる" と見なしてはいけないということに気付かなかったりでしばらくバグらせ、なんだかんだ 50 分かかった。
B
座標平面上の与えられた点を使って三角形をできるだけたくさんつくる。
ぱっと見なんか難しそうだなあという印象。
ただ制約小さめ (N <= 300) なので、N^3 でもいいのかあとわかる。
そこから逆算して N^3 でなんかそれっぽいことできるかなあと思って、全部の i,j,k のペアについて点 k が点 i,j を結んだ直線上にあるか? みたいなのは全部計算できるなあと考えた。
そのあたりの情報使ってあとはなんか貪欲とかで解けるんじゃないかなあと思ったけど、いい感じの貪欲が思い浮かばなくて結局何も書けず。 ちょっとマッチング問題ぽさも感じたけど、グラフ的な考察はあまり役に立たなそう? (むしろ hyper graph な気もする。使えそうな定理あるか知らないけど)
終了後になってから、なんなら乱択山登りでもワンチャン通っちゃうんじゃない? と思って適当に書いてみたら通っちゃってびっくり。これ今回は正当解法なのね... writer の第一想定解ではないっぽいけど。 アルゴだからといってあんまり見込ある解法思いつきそうになかったら、それなりに見込ありそうな乱択考えてみても良いのかなあという学び。
面白い問題だった。
C
数列の左から奇数番目の数が中央値にならないように区間を広げたときの大きさを全部求める。
B がすぐ解けなさそうだったのでとりあえず問題だけ見てみたけれど、やっぱり C は難しそう。 区間だし頑張ればセグ木とか乗るの? とか適当な考察をしてみるも、区間の中身ほとんど全部覚えとかないと区間合併して中央値とか求まらなくない? と思ってやっぱりよくわからないので諦め。
まだ書いていないけど、解説放送聞いて解法のお気持ちは理解したつもりなので、後で勉強がてら書いてみよう。 考察が少し難しいけど、あんまりマニアックな知識がいるわけではないしよくできてるなあと思った。
