ABC168

5完。今週無精進で心配だったけど、めちゃくちゃ楽しい問題ばかりでめちゃくちゃ楽しかった。

A - ∴ (Therefore)

3種類のサンプルがあるので、そちらのコピペミスは検出される。一の位が3は普通にif文書くとして、問題は0,1,6,8を書き間違えないかだ。結局、慎重にif文書いてACしたけど、できれば0,1,6,8をコピペしたいよね。ただそうするとコード量が無駄に増える。0,1,6,8をコピペして、そこからキーボードの数字を使わず n == 0 || n == 1 || n == 6 || n == 8 に書き換えればよかったかなあ(n %= 10; してある)。

B - ... (Triple Dots)

ちょうどK文字のケースはそのまま出力することに注意して書く。少し考えて s.resize(k); s += "..."; とした(文字列に対するresize珍しくて緊張した)。

C - : (Colon)

時計を傾けたり裏返しにしたりしても答えには影響しない。あとは座標求めて距離を計算するだけ。例えば長針(あ、長いとは限らないから分針という表現なのね)のx座標は B * cos(2π / 60 * M)。と思ったらサンプルが合わない。「各針は常に一定の角速度で回ることに注意してください」の意味がずっとわからなかったが、はい。よく考えたらそんな動きする時針あったら怖いわ(秒針はそういう動きするのも多い)。

D - .. (Double Dots)

ダイクストラ法の経路復元だと思ってyosupo judgeの自分の提出を取ってくる。しかしよく見ると「最小の移動回数」だ。えー絶対「最小コスト」とかそういう文字列が書いてあったよー(幻覚でしたね)。ということでBFSを貼る。BFS中に、その場所へどこから来たかを記録していく。

E - ∙ (Bullet)

(A, B)という座標にいるとして内積が0同士は一緒に選べない。しかし、入力は10^18までありえるため掛け算できない(いざとなれば__int128_tが使えるとは思ったけど)。

先に面倒なところを潰しておく。1匹以上とあるが、0匹以上とすることで1通り増えたものを求めることにする。また、(0, 0)に1匹以上いたら、それらは単独でしか使えない(3匹いたら3通り増やしてその3匹は除く)。

さて、ここからはベクトルとして考えてちょうど90度のペアを除く方法を考えればいい。ベクトルの向きを90度の違いを無視して分類できれば(分類したらその中で同じ向きと90度違いはすぐわかりそうなので)よさそうだが、それが難しい。入力は整数なので、同じ向きということは、ある(整数の)ベクトルの3倍と5倍みたいな関係になっていそう。つまり、GCDをとって割れば正規化できるのでは?あとは偏角ソートとか要らなくて単に同じものを数えるだけ(適当な基準でソートすればO(NlogN)で数えられる)。a/b=c/d(どっちも既約分数)と仮定するとa=bc/dなのでbc/dが整数であるためにはb/dが整数である必要がある。同様にd/bも整数でないといけないので、やはりGCDで割って符号も合わせればそれでよさそうだ。具体的には、y座標は非負かつ、x座標が負ならy座標は正、とする。さらに、x座標が正かどうかで2種類に分ける(x座標が0以下のものは90度回転させてから格納する)(片方の種類しか使えない)。これを、最初の分類内で各種類が何個あるか数えて、各種類がk個とl個あったら2^k+2^l-1を掛けていくのを分類した個数分やる(0個選んだときは、どちらの種類を選んだか区別できないので1引く)。実装にかなりの時間を使ってしまったが、なんとか一発AC。

F - . (Single Dot)

Eを考えながら問題文だけは読んであった。難しそうだが、座標圧縮すれば線分を2次元配列上に描けるのでは?2倍すれば隙間ができるし。2*2のグリッドを描いて、4点と4つの辺と真ん中の空洞1つ、その9個が3*3の正方形に収まってて、これを広くすると元のグリッドの4倍の面積で表現できる。じゃあ座標圧縮をしてBFSしよう(面積がまた難しいと思ったが、座標がどっちも奇数のときだけカウントとかでできそう)。残り20分で、まあ無理だけど書く。なんと時間内にとりあえず最後まで書きあがった!しかし手元で実行してREなので終了。しかも、座標圧縮したぶんを考慮して面積しなければいけないことに気づいてなかった。

全体として、難易度は低めだが、ちゃんとした理解と実装力が要求される、という問題が多かったと思う。楽しかった!