日記0130　ABC190感想

朝起きた。

なんちゃらソリューションズという会社の一日職業体験の予定が10時から17時まで入っている。これを予約？したときは就活してるわ～という感じで充実感があったが当日になってみると鬱イベ以外の何物でもない。つらい。

内容は、完全に敷かれたレールを走っているだけの簡単なものだった。おもんない。40ページぐらいある日本語で書かれた仕様書を読んで、実装するというものだった。これはAtCoder茶色ぐらいあって三角関数がなにものか、という知識さえあればやるだけというレベルだったのでサクサク進めることが出来た。担当しれくれた人は今までこの内容でやってきた人の中で一番早いと言っていた。異世界転生してまたおれなんかやっちゃいました？みたいな気分になった。競プロで現実をわからせられているので惨めな気持ちになるだけだった。

そのあと企業説明会があったけど普通に良さそうな企業だったので選考会に進むことにした。また履歴書タスクが増えた。燃えちまえ。

何をしていたか覚えていないが夜8時ぐらいになった。

ABCにでます。最近不調なので、どうにかしたい。今回も爆死という感じだった。これはもう認めざるを得ないが自己評価が高すぎて何をしても失敗に感じてしまうらしい。口では自分は弱いと言っているが内心ではそこそこ強いほうだと思っているのが痛々しい。誰か何とかしてくれ。

以下ABC190

A. Very Very Primitive Game

場合分け多すぎて憤死した

これcの値でなんかをswapすれば一個だけで行けるなと思って書く。書いたswapが不十分で1WA　アホか？悲しい

B. Magic 3

問題文様の仰せのままに

C. Bowls and Dishes

bit全探索を書く

D. Staircase Sequence

難しすぎる　おれは数字を扱うのは苦手なんやという気分に

制約 $N \leq 10^{12}$ から解法は $O(log N)$ やなという気持ちに。

これは約数だけ初項全探索すれば解けます。と思ったらN=13のときに6,7を発見できないことに気づき、この考察を捨てます。

次に数列の長さを全探索する気持ちになる。 $\sqrt(N)$ よりも長い長さの数列の和はNを超えちゃいそうなのでよさそうな気持ちになるも長さLの数列和がNになるものの判定をどうしたらいいかわからね～～～と思う。冷静になって長さLの時に構築できる条件を手動全列挙すると、Lが奇数のときはN%L==0ならokでLが偶数の時はL/2==N%Lならokということがわかる。

これを適当にrep(i,sqrt(n)+1)で判定して数えるとサンプル3が落ちる。どうすりゃええんじゃという気持ちになってヤケクソをして投げてペナをつけた。こういうのをやめたい　判定はL*(L+1)/2<NのLに対して行えばよい。なんでかわからんがACしたのでヨシ。

E. Magic Ornament

先に順位表をみるとFのほうが解かれている。ので見なかった。

Fを解いた後で冷静になって眺めるとグラフになっていることがわかる。本当は冷静になっていなかったので本番は $c_0,c_1, \dots , c_{k-1}$ の順に回るのかと思って各 $c_i$ からダイクストラした。当然違う。

うなりながら問題を眺めると巡回セールスマン問題の始点に戻ってこなくていい奴ということがわかった。これPASTで解いたことあるな～と思った時点でコンテストが終了した。コンテスト終了後に書いたら20-30分ぐらいでACできたのでDを見た瞬間に捨ててこっち解いてればよかったなと思った。

都合のいい言い訳です。ちくしょう。

F. Shift and Inversions

D終わった時点でたくさん解かれていたのでこっちを解くことにした。こっちのほうが配転が高いので解けた時に強いし。

転倒数はセグ木かフェン木(BIT、fenwick treeのことをセグ木みたいに略す人いないね、なんでだろうか)を使うことで $O(NlogN)$ で解ける。数列 $A$ を二回繰り返した数列を $A'$ として、長さNの区間の転倒数が答えになるので、適当に転倒数を計算してって累積和取れば答えられるかなと思って実装したけどダメだった。