ABC148

ratedでこれはさすがにクソゲーすぎる。全完でレーティングが落ちるんじゃ、俺はこのコンテストで何を得たんだよ。

A - Round One

自分はABC075のAでxorを使えたことだけを心の拠りどころとして生きているので、ここでもxorを使おうとしてしまった(a^b(1^2^3==0なので))。1分切ってるから結果オーライだけど、冷静になってみると、6-a-bなどと書いたほうが自然だった。

B - Strings with the Same Length

新たな文字列は作らず、SとTを1文字ずつ出力していく。

C - Snack

最小公倍数を出力するだけ。えっ、マジ!?って何回も確認して時間食った。

D - Brick Break

この「任意の」読みづらいからやめてほしい。「全てのiについて条件を満たすとき」って意味なんだろうけど「どのiでもいいから条件を満たすとき」にも見えてしまう。ここでトイレに行った。直前にも行ったけど出なかった。先週何もなかったので久しぶりのコンテストで緊張していた。トイレの中ですっきり解けたので実装。1,2,3,4みたいななるべく長い部分列を見つけたいので、1から貪欲に探せばよい(同じ数が複数あるときも最も左のものを取ってデメリットがない)。

E - Double Factorial

2つ前を見るということでフィボナッチみたいなイメージを持ってしまったが、よく見るとただの階乗じゃん(!じゃなくて!!のほう)。Nが奇数のときは積も奇数なので10の倍数にはならない。偶数のときは、サンプル1やそれよりNが小さい領域でも5より2のほうが多いので、素因数5の個数がわかればいい。((2n)!!は2^n*n!で2^nに5は入ってないので以下NをN/2で置き換えてN!を考える)1以上N以下の5^kの倍数の個数をk=1から5^kがN以下の範囲で足せばいい。125の倍数だったら3個だけど、5の倍数と25の倍数のときにも足してるので(ということをコンテスト中はあまり深く考えてなかった気もするが)。1以上N以下の5の倍数の個数って単にN/5(切り捨て)でいいんだよね。それはそうなんだけど、意外にも感じる。

F - Playing Tag on Tree

木なので、辺は全部橋。青木君は高橋君に向かって動くだけで追い詰めることができる。高橋君は(青木君を根として各頂点の深さを計算して)深いほうへ逃げるだけ?解けてないけどとりあえず必要そうなところだけ書き始める。書いてる途中で、シミュレーションせずとも深さの値だけでよさそうだと気づく。書き上げて、とりあえず実行してみるが、サンプル3が合わない。ここで気づく。高橋君が一旦浅い場所へ戻ってから別の深い場所へ逃げるケースが漏れてた。証明はすぐできそうになかったのでその実装をやる。かなり時間をかけて汚いコードを書くもサンプル3の出力が変わらない。めっちゃ体温上がってた。こういう、やりたいことはわかってるけどゴチャゴチャしてるの苦手すぎる。ここでググってサンプル3のグラフを可視化。合ってそうだが、ここで気づく。青木君の初期位置を根とする根付き木で考えていたので、uが青木君だと勘違いしていたのだ。そこを直したらサンプル通ったので(もういい時間だし)提出、AC(実装で混乱しててWAにならないのわりと珍しい気もする)。もっといい方針があったと思う。そうすれば証明もできたし証明と実装の時間もかからなかった。これは今の実力だと仕方ない。