ARC142

3完。最近のARCはAがつまらない。実力は測れるかもしれないが、何のためのARCだよ。BCは面白かった。レーティングとしては、早解き回で微減は実質勝ち。

A - Reverse and Minimize

K=240は0通り(最小値が240とするとそこから2回操作して24となり矛盾)(書いてみてこんなのに背理法要る?って思うしコンテスト中もかなり考えづらかった)。なのでまず10の倍数を処理する。次にKの反転を求め(to_string, reverse, stoll)、KとKの反転に0を付けていって(10倍していって)N以下の間カウントする。反転しても同じときは片方だけ。

提出してWA。332も0通りなのを見落としていた(最小値が332とするとそこからもう1回操作して233になって最小値でなくなり矛盾)。注意力コンテストなのはいいんだけど、これ解けて何の意味があるんですかと思う問題でされてもなあ。

B - Unbalanced Squares

角と辺は周囲のマスが奇数個なので考える必要がない。順番に並べると、ちょうど半々になってしまいまずい。それがダメとなると、確実に条件を満たせるような配置はかなり難しそうだ。左3個だけ小さくなるような配置を探っても、右だけでなく上下も大きくないといけないとなると規則性のある配置がなさそう。規則的に置くと半々になるし、規則的でないものはプログラムにできないしで困る。1行ずつ考えてみる。上の行から順に0 5 1 6 2 7 3 8 4としてみると、端以外のどの行から見ても上下どちらも小さいかどちらも大きいかのどちらかになっている。過半数である6個が自分より小さい(大きい)のだから条件を満たしている。さっきの数にNを掛けてそれをベースに横位置を足して1を足して出力。

C - Tree Queries

まず、0-indexedの頂点番号2個を渡すとその距離を返してくれる関数を書く(-1が来たらその関数内でちゃんとプログラムを終了させる)。頂点1を根とする図、番号が1でも2でもない頂点を根とする図などを描く。色々な距離を観察していると、最短経路上にある頂点からの距離の和が求める距離になると気づく(言われてみれば当たり前だが)。そういう頂点がある場合、単に(N-2)*2回質問して距離の和が最小のものが答えになる。問題は、最短経路上に他の頂点が存在しない場合(答えが1の場合)。そういうときは、頂点1までの距離と頂点2までの距離の差が常に1になる。しかし逆は成り立たない。N=3のときは質問に使える頂点が少ないので場合分けが要るかもしれない。N=4を考えると、パスグラフで3 1 2 4と並んでいるのと1 3 4 2となっているのを見分ける必要がある(1,2を含めた質問のみでは不可能)。そこで、(N-2)*2回の質問の結果を頂点毎にN-2個保存して距離の和で(それが同じなら頂点1との距離で)ソートする。最小値が偶数ならそれが答え。そうでないとき、N=3なら答えは1(少なくとも3は答えじゃない)。そうでないとき、質問の結果は2個以上あるので最初の2つを比較して、距離の和が異なるなら答えは1(距離の和は3以上なので答えが1でないなら少なくとも最短経路上に2個の頂点があるはず)。そうでないとき、その2頂点の距離を質問して1でないなら答えは1(ソートしてあるので最短経路上にあるなら隣同士)。そうでないときはその距離の和が答え(距離が1ということは辺で直接結ばれていて、答えが1とすると頂点1か頂点2と直接結ばれる2頂点が結ばれてると閉路になってしまう)。

提出してRE。ソートの比較部分を手癖でミスしていた。

DEFは全部読んだが、結局座っているだけに。自分は浅瀬でパチャパチャやってるだけという実感が得られて生きる気力をなくす。ベタな予想通りの崖になるの逆に意外だった。EFはこの見た目でクソ難しいらしいのすごい。

ABC256

何もできなかった。EFGを並列に考えていたが何もわからん。順位表を見てEだけはねじ通した。

A - 2^N

シフト。

B - Batters

後ろから残塁を求める方針もちらつくが、素直にやる。途中で、ビットで管理すると進塁がシフトで済むから楽だと気づきそうする。popcountではみ出したのを数えたけど、そんなことせずこれこそ残塁を調べればよかったか。

C - Filling 3x3 array

1を引いて、非負整数を書き込むことにする。すると和は最大で27なので、そこに仕切りを2個入れて1行で406通り。それを3行決めて406^3通りを全探索はちょっと実行時間が不安。いくつ決めれば全部決まるか考えてみると、例えば左上の4つだ。これを27^4通り調べるのは間に合う。残りを引き算で決めて、右下隅だけはもう片方の和が合ってるかを確認。最後に、全体で負の数がないかチェック。楽な書き方あったかなあ。

D - Union of Interval

お、これは典型。存在は認識して未履修なので、俺にできるかなとドキドキする。Lでソートしてみる。左から見ていくと、次のやつと離れてるなら今の区間は他のどの区間ともくっつかない。そうでないとき、次の区間とくっつけてもソートされた状況に変わりがない。区間が決まったらその都度出力していく。最後に今の区間を出力して終わり。意外と簡単だった。

(解説を見て)なんでLRが小さいんだろうと思ってたらいもす法が使えるのか!

E - Takahashi's Anguish

ソートするのかなとか。ループしたら少なくとも1個はコストがかかるけど他の人との兼ね合いで2個になることもあるのかなとか。捉えどころがない。

連結成分毎に考えると、頂点数と辺数が同じ。つまりループを一つだけ含む。ループに注目すると、その中で最小のコストは払う必要がある。ループに含まれない部分は前に持ってくれば(先にキャンディを渡せば)コスト0。他の連結成分とは干渉しないので、そのコストが達成できる。実装が難しくて、とりあえず今回やったのは、各頂点から辺を辿っていき訪問済みに当たったら改めてそこから辿ってループを検出する(ループ内のC_iの最小値を答えの変数に足す)。しかし、訪問済みに当たったときそれが本当にループかはわからないと途中で気づいたので、最初の頂点番号を探索の世代として訪問済みフラグとは別に持ち、今の探索で訪問済みになった場所ならループ、そうでなければそこにループはないと判断した。

F - Cumulative Cumulative Cumulative Sum

A_iが変動したときのDへの寄与を考えると、D_iに1倍、D_(i+1)に2倍というふうにD_Nまで続いていく。これも捉えどころがなくて困っていたが、まあ遅延セグ木に乗る気もしてきて。クエリxに対しては先頭からxまでの和を返す。足すときは、xから最後まで(増分に1, 2, 3,...を掛けて足す)。コンテスト終了後に提出したがWA。

G - Black and White Stones

各辺で等しいという白石の個数を固定すると、頂点に白石があると隣の2辺で白石が1個ずつ減る。各辺1個のときは特殊で連続した頂点に置けなくなるがこれだけでもけっこう難しそう。DPっぽくはあるけどなあ。

春アニメ第10話

やる気ないし今週はアニメでも見るか。

まちカドまぞく 2丁目 #9

桃、自然に笑顔出してくるな。いいぞ。

「魔力の蛇口が常に全開」超サイヤ人みたいな。小倉さんが桜さんのメモ帳を持っているというヤバ状況になってた。KIRARAタブレットいいね。シャミ子が、桃のおなかに触ろうとするなど、ちょっとした描写の積み重ねで以前より余裕があるように見える。

かぐや様と同クールというのが微妙なのよな(小原古賀)。

このヒーラー、めんどくさい #9

いいリズムの掛け合いが次々に。面白いアニメか?もうちょっと落ち着いて欲しい。OPで見慣れたメデューサが存外かわいい。

盾の勇者の成り上がり Season 2 #9

やっと面白くなってきたなあ。日本人だったキズナがああいうかわいい服着てるのいい。ED、今度は尚文のところにフィーロがいてラフタリアがいない状態、これも効果的で、2期のEDとして素晴らしい働きだ。

かぐや様は告らせたい 3期

最初怖すぎる(別物すぎて確かにこれはアバンに置けない)。今回の藤原書記幼くて過去編かと思った。萌葉かわいい。「ややサイコパス」って書いてあったけど普通に見える。

八十亀ちゃんかんさつにっき 4さつめ #9

実写をやめろ。ララちゃんと笹津がよかった。

本好きの下剋上 #35

前回の流れのまま激しい展開だが、なんかゆっくりだ。

かぎなど #21

なんもわからん。

ABC255

6完。今週は苦しみながらも色々やれてよかった気がする。そこへ突然現れるABCは、久しぶりに感じられた(普通に1週間ぶりだけど)。

A - You should output ARC, though this is ABC.

簡単だけどさすがに実装量が多く1分以上はかかった。

B - Light It Up

Bで二分探索うそだろ!?なんとか頑張ってBらしい解法を探る。明かりを持っていない人の視点で考えると、その人が照らされるためにはRが一番近くの明かりを持った人までの距離以上である必要がある。最小値の最大値が答えで、実装がけっこう大変。Kは0でもNでもないので最小値や最大値を求めるときに気を使う必要はない。

C - ±1 Operation 1

一番近い数までの距離。まず、数列の要素の絶対値は2*10^18以下に収まるのでlong longで大丈夫。数列の最小値以下のときと最大値以上のときを場合分けして処理。そうでないときはDが0でないので割り算できる(書きながら気づいたというのもあって、0でないとわかっていても明示的には書いてないのでドキドキするね)。割って掛けてX以下の最大の要素を求めるときに、Dが負の場合をケアしようとして、Aが数列の最小値と限らないことにようやく気づく。これは数列の頭とお尻を入れ替えればいい。あとはX以下の最大の要素とその次の要素の近いほうの距離を出力すればいい。

D - ±1 Operation 2

C問題と同じ設定だが、制約も内容もかなり解きやすそう。Aはソートしてもいいのでソートすると、X以上とそれ以外に分けて累積和のアレだ。ソートして累積和を求めておき、各クエリに対しては二分探索で初めてX以上となる位置を求め、あとは図を描いて引き算で2箇所ぶん求める。

E - Lucky Numbers

何言ってんのかわかんないが、Aとしてありえるのは自明な解からジグザグに伸ばしていったものたちだけだ。それがXに当たるの検出する?最大値になるときはどれかは当たってるから各A_iがX_jに一致するのを全探索?A_iがX_jに当たったときの伸ばした量はわかるので、伸ばした量として現れるもの(A_iとX_jの差をインデックスの偶奇で符号を変えて)の個数を数えればいい。同じ伸ばし量で同じA_iが複数のX_jに一致することはないことに注意(コンテスト中の思考って特殊で、これをどう捉えていたか思い出せない)。

実装が楽なunordered_mapを使った(楽じゃないのはソートしてランレングス)けど、logみたいの(Mとunordered_map、どっちもlogではないけど)が2つ付くことを忘れていた(1つだと思ったから躊躇わずunordered_mapを使った)。実行時間が538msと思ったより長くて気づいた。実行時間制限が4秒なのもあとから気づいた。

F - Pre-order and In-order

帰りがけと思ってたら通りがけ順だった。そういうのがあるのか。方針として、オイラーツアーで上からからぶあっと考えるか、正面からパズルを解いていくか、前者を有力視していたけど普通に正面から行けたわ。まず、Pの先頭が根。Iの中でそれが現れる位置でIを前後に分け、前が根の左の子、後が根の右の子。Iの前の部分がPでも根に続く連続した区間で集合として同じになっている必要がある。そうやって分割統治みたいにしていく。実装としては、集合として同じかのチェックにハッシュを使い、前と後で小さいほうだけを比較する(これでlogくらいに収まるやろとかテキトーに考えてた)(集合として等しい状態で関数を呼ぶことを保証する)。根がIのどこに現れるかは逆引きテーブルを作っておく。Iの逆引きした位置から開始位置を引いて前側の個数を求める必要があるなど、混乱要素が多い。

これ集合として等しいか毎回チェックする必要ないかあ。その場合、根が区間内のIにあることは保証されないけど。なんか今回EFで時間をかけてしまった気がする。

GHは読んだだけ。Hはやたらスケールが大きくて面白そうだった。