ABC270

6完。調子はよかった。Fまで早解きできる得意セットだったみたい。Gに時間を残せたのに難しくてまるっきり足りない。Gで相当頭が疲れた。悔しいけど勉強になるのでよかったね。

tokuminiさんと隣の順位。見直ししなければ勝ってたなあとか言える非常にレアな状況。

A - 1-2-4 Test

「少なくとも一方」を読むのに少し時間がかかった。点数はビット被りがないので、ORだ。何と何が対応しているからみたいな思考がけっこう深くて大変だった。1分切れてよかった。

B - Hammer

けっこう難しいけどこのくらいなら俺でもわかるよ。まず、壁の位置を固定したい。Yが負ならX,Y,Zそれぞれに-1を掛ける。「普通に行けるけどハンマーを使ってショートカットできる」みたいなことはないので、XとYを比較してハンマーが要らないなら単にXまでの距離、そうでないならZとYを比較してハンマーが取れるならZまでの距離とZからXまでの距離の和、そうでないなら到達できない。いいテンポで解けた。

C - Simple path

さすがにやるだけ。どう実装するのが楽だったんだろうね。普通にXからDFSしてYを見つけたらそこからは他を探索せず戻るたびに頂点をpushしていき最後にreverseして出力とした。あー普通にスタックトレース(と呼ぶのはおかしいか)持つのでもよかったな。

D - Stones

A_1=1という制約にギョッとするが、それによって石を取り切ることが常に可能なのが自明になっている(あまり意識してなかったが零和じゃなかったら大変なことになりそう)。Nが小さいので簡単にDPできる。i個の石からスタートしたときの先手のスコアでDP。自分より小さいところは全部求まっているとして、全部の合法手に対してスコアを求める。i個の中からA_j個の石を取って残りs個になった相手のスコアがdp[s]で、じゃあ自分のスコアはA_j+(i-A_j-dp[s])とかやってたけどこれは要するにi-dp[s]で、i個の中から相手に取られるのがdp[s]個だからそりゃそうだ。

E - Apple Baskets on Circle

右隣というのがわかりづらい。高橋君が円の内側にいてかごが時計回りに並んでいるイメージで落ち着いたけど、これは外側にいて反時計回りでもいいし仮に上から見てたら円の奥と手前で左右が逆になってしまう。まあ、円はすぐに切り開いて線にしてしまうのだけど。

かなり怖い見た目だが、そこまでではなかった。最初に山の上だけ切り取るような図を描いていたが、それは間違ったイメージで実際には逆さにした山の上だけを切り取る。二分探索できる。数が大きいのでシミュレーションは間に合わないが、終わるギリギリまでシミュレーションを進めてもらう。1周単位で考える。一番多く取ったかごからX個取ったときに、全体で何個取ったかを求めて、それがK以下になる最大のXを求める(K以下にならない最小のXを求めて1を引く)。X周した状態が求まったら普通にシミュレーション(必ず1周で終わる)。

F - Transportation

まあ最小全域木。空港と港がわからないが、2種類あるってことは1種類ならそこそこ簡単ってことか?と思い、港はないものとしてまず考えてみる。超頂点を追加するような考え方でできたらいいけどできないよなとか思いながら考えると、できる。空港に対応する頂点を1個追加して、空港を建設することはそこと双方向に結ぶ道路を作るのと同じことに「空港を使うと仮定すると」なる。港もあわせて4通りやればいい。UnionFindで、使う頂点数から1引いた数だけ結合したら終わり(使わない頂点と結ぶ辺は無視する)。全域木ができてなくても最小コストを更新していてサンプルに助けられた。

G - Sequence in mod P

「Baby-step giant-step」の名前がなかなか思い出せなかった。brother big young などの単語で競プロ関係をググっていたが、giantを思いついてそこからすぐわかった。イメージはかなりぼやけているけどたぶん実装経験もあるし行けそう。(int)sqrt(P)回操作した値を知るのが難しいと思ったが、行列累乗で行ける(不思議な感じする)。S=GやA=0は場合分けするとして、他はP-1の周期を持つ気がするから甘えも利きそう(終了後気づいたがサンプルにA=1という反例あり)。逆元が難しそうなのでゴールからBaby-stepで当たるのを探す。それは必要条件でしかないので行列累乗で実際にその回数でその値になるか確認する。アイデア自体はシンプルなのに難しくて時間がどんどん過ぎる。とりあえず5分前に書きあがって、これが正解だとは思っていないがサンプルくらいは通ると思って実行したら全くできてない。このやり方だと周期が1個前だったりとかするんだな。周期は全てP-1と言えるだろうか。そもそも、A=3,B=P-2,S=1みたいなのもあると気づいてなかった。

ABC269

6完。今朝から体調悪かったけどコンテスト前には普通に戻って、コンテスト中はいいパフォーマンスが出せた。順位は普通だったが。

A - Anyway Takahashi

式をコピペすると、×はわかってたけど−も半角じゃないので直す必要があった。Takahashiもコピペしてきて、ギリギリ1分切り(えらい)。

B - Rectangle Detection

けっこう難しいと思うけど、こういうのはABCのBとしていいと思う。順番に1行ずつ見ていって、最初の'#'と最後の'#'で位置をメモすればいい。最初というのは、メモする変数を答えとしてありえない数で初期化しておくことで最初かどうかを判定する。最後は、'#'が来るたびに上書きするだけでいい。

C - Submask

計算量が3^Nになる例のコードを(内側だけ)貼る。

D - Do use hexagon grid

六角形怖いけど、何と隣接するか書いてあるので六角形のことは忘れていい。Nが小さいので2003*2003のサイズでUnionFindできる(16MB一気に確保するだけなら高速で、その後の処理も大して遅くならない)。マスを塗ったかのフラグも持つ。答えの変数をNで初期化し、あとは隣接する位置が塗ってあればつなげようとして、未結合のものを結合するたびに答えの変数をデクリメントする。

E - Last Rook

ABCDがB問題と同じ形式で良い。10^6通りの答えが考えられるのに質問は20回と少ない。これは二分探索が見えやすい。内容的には簡単だが、実装はちゃんとやる必要がある。行と列で別々にやる。最初[0, N)に答えがある状態から始まって、前半分でクエリを出して幅よりルークの個数が少ないなら前半分にある。区間の長さは1回の質問で、今の区間の長さ以上の最小の2冪の半分以下になるので大丈夫。区間の長さが1より大きい間続ける。区間の長さが1ならそこにルークがある。手でテストして、N=1は(制約外だけど)大丈夫。N=5でやったとき、行と列で質問を変えてなかった(ABとCDを入れ替える)ことに気づき直す。運よくAC。

F - Numbered Checker

嫌な見た目。書かれている数の偶奇ではなかったので一安心。横方向の和は等差数列なので求まるが、その和を縦方向に見ても等差数列になっているので、これは一応簡単。しかし実装が怖い。Gを少し考えて、解けないので戻ってきた。横方向にここからここまでの和を求める関数を書く。半開区間ではなく閉区間を使う。最初の位置は、奇数なら1進める。最後の位置は、奇数なら1戻す。そしたらそこに書かれている数はそのまま求まるので、最初と最後の数の和と0でない数の個数から和が求まる(0でない数が0個のときも正しく求まる)。この関数を使って、一番上の行、その次の行、一番下の行、その前の行の和を求める。ここからは、AとBの偶奇が一致するかで場合分け。等差数列になるのでまた同様の計算をする。こちらも、個数が0でも正しく求まる。コード量は多いものの、意外とシンプルに書けた。

G - Reversible Cards 2

min(A_i, B_i)は必ず足されるので引いておく(引いた数の和は持っておく)。少なくとも片方が0になる。とりあえず愚直DPでサンプル通すところまではやった。平方分割して半分全列挙みたいにできないかなとか思ってた。裏表の差が全部1なら簡単なので、数が小さいとき上手くできないかなと思ったけど、小さいとはいえナップサックだからなあ。100以下とかでは厳しそう。あとはマージしてくやつかなあ。Gにあと10分多く残したかったと最初は思っていたが、全然だった。

(追記)思い切ってB_i-A_iだけ使えばいいね。そして、その値がO(sqrt(M))種類しかないというのはなるほど。これは気づきたいねえ。DP部分は、自分の愚直は配っていたが、貰うようにすればin-placeでできた。短時間で書き切ることを目指していたとはいえ、こんな基本的なDPで気づかないのは力不足。しばらく考えるとSWAGで貰うDPもできそうではあるが実装は重そう。解説にあった2冪と半端に分割する方法がすごくて、実装も負荷が少なそうなのでこれで実装した。B_i-A_iが負のときの和とAの和を使うのだが、かなり混乱した。

夏アニメ第8話

時期的に8話ではないと思ってるから「#8」も省略していない。

オーバーロードIV #10

いやあ。この兄妹は優秀なのに置かれた状況が悪すぎる。どう言えばいいんだ面白かったけどそういう表現じゃないだろ。らしさが出ている。

ラブライブ!スーパースター!! 2期 #8

妹が学校に来るのドキッとする。夏美が仲間になって丸くなってかわいくなった。生徒会に入ったのは789の一人。東京大会進出。ええと、1期では東京大会2位だっけ。こういう速い展開の中で前回のような話をしてくれるの嬉しいね。

リコリス・リコイル #11

千束と聞いてもどっちかわからんことある。たきなは青いイメージあって確定するけど。クルミはロリじゃねえって言ってんだろ!

たきなの電話に「出ない」ってところに、感情が入っている。OPの蹴られる千束が本当に嬉しそう。解散する寂しさ、何だっけな(ワッハマンしか思い浮かばん)。え、閉店のことも知らないほどたきなは千束に会ってなかったか?DAに行ってるからか。全部忘れてる。こういう展開になると制服が強みではなく弱々しさを感じさせる。いや今制服に気づくなよ(高校名が不明な女子高生の制服とか存在できるわけないだろ)。街中に敵がいたのもびっくりだがちゃんと反応してて強い。千束の能力は初見殺しだよな。機能的なカバン。真島こんなに強かったのか。すごい全部この最後のシーンに乗せてきたな。しかし、視聴者の気持ちとしてはたきなが邪魔者になってしまう。せっかく真島が勝てそうだったのに(真島を応援しているわけではなく、展開的に(いや応援はしてるけど))。スマホが何だったのかわからない。最初ED曲だと気づかなくて、いやこの聞きなれた曲で気づかせないの、ここの演出本当にいい。

異世界薬局 #9

え、最初に過去っぽい話はあったけどすっかり忘れてた。

ダンジョンに出会いを求めるのは間違っているだろうかIV #8

リューさんの作画を見る回にしかならんだろこれは。内容はよくわかんないし。

ARC148

ABDの3完。昨日と展開は似ている。今日は頭の悪さばかりを感じた。昨日よりは調子が悪かったと思う。

A - mod M

答えは1か2(M=2とすれば2種類以下になる)。種類数を最小にするMを選んだとき、Mで割ったあまりは全部同じということで、どんなペアも差がmod Mで0になると気づく。最小のA_iをとって全部からそれを引いてみる。GCDが2以上なら、Mとしてそれを選べば答えは1。そうでないときは2か?ここからかなり考えて証明できず、もし間違っていてもペナで時間を買ったほうがいいと判断し提出、WA。

GCDが1なのに答えが1のことがあるってことだ。少し考えて、GCDが0のケースを思いつく。GCDとしての0って全ての素因数を持ったクソデカ数だからこれは気づきにくい。今考えると、GCDが1かどうかで考えればよかったな。

改めて考える。そもそもA全体に同じ数を足しても状況は変化しない(Mで割ったあまりも同じだけ動く)。つまりAのうち少なくとも一つが0だとしてよくて、その0は何で割ったあまりも0だから他の要素もMで割り切れる必要がある、よってMはAの公約数である必要がある。

B - dp

解法がDPなのか気になるが、まあ先頭から決めていきたくなる。最初の文字をdにできるか、できるならその上で次の文字をdにできるか。初めてpが現れたとき、選ぶ区間はそこを含んでいる必要がある。操作後、できるだけdを連続させたいが、ここで区間の先頭をそのpより前にすると、操作後のdの連続数が余計に必要になってしまう(pがもっと連続して終わる区間を選ぶ必要があるがそんなものがあれば元の位置からそこまでを区間として選んでる)。よって、感覚ではわからないのだが、区間の先頭はそのpとしてよい。計算量が、制約は2乗っぽく見えるけど、考えていると1乗や3乗ばかりがありそうでつらかった。

わからなくてCと交互にやっていたが、Cがわからないので戻ってきた。区間の終わりはpが一番多く並んだ場所が候補になる。pの連続数でインデックスをvectorvectorに入れていく。一番連続数が大きい候補を全探索。これで2乗になった。提出してWA。どう見ても正しいのでつらかった。時間がかかっているので、これ以上無駄な時間を過ごさないように順位表を見た。区間内が全部pでありかつ区間の直後がdであるケースを見落としていた。このときは操作後のdの連続数が区間末尾のpの連続数より大きくなる。ていうか区間の先頭は最初のpの位置で決まったのだから、単に全探索すればよかった。そのように実装してWA。区間の終わりの位置をN未満までしか見てなかったが、半開区間なのでNも含めなくてはいけなかった。これでAC。ズタボロ。

C - Lights Out on Tree

Q=1なら簡単で、上から、操作しなければならない場所を操作していくだけ。Mが小さいときにどうやって高速化できるかという問題。M=1なら、そこを操作して、子を操作して戻すだけ。ただ、100個とかあるときにどうなっているか。どの部分木に入ってるかもわからんし。自分も直接の子の一つも点灯してるなら状況が変わりそう。他の子孫の点灯してるやつが、その中に入っているかどうかで話が変わってくる。解けそうにない。

(追記)点灯している1個を消す操作は、自分と自分の子に対するもの。直接の子でない子孫が点灯していた場合、祖先が2回操作されるから影響がない。え。なんで気づかないというか、なんとなくのイメージで探ることもしてなかったってこと?親子で点灯していた場合、親から見ると子の操作が1個減って、子から見ると自分への操作が1個減る。実装は、入力通りに親を記録しておいて、子をカウント。クエリは、予め長さNの-1で初期化したvectorを用意しておいて、頂点番号のところにクエリ番号を入れる(こうすればlogは付かない)。親が頂点集合に入っていたら2を引く。

D - mod M Game

AB遅解きでCが解けそうにないので、Dに賭けましょう(改めてCを考えてみたい気持ちもあったが)。順位表で誰が解けてるか見てやや相性悪そうとは思ったが通してる人数自体は多い。Nが偶数のときを考えようとしていたが、とりあえず入力受け取るところまで書くかと思い書いていると、そもそも2*N個だったことにようやく気づく(実装は証明のような頭の使い方をするのでこういうのに気づきやすい)。

Bobが勝つケースを考えると、サンプル2のように全部の数が偶数個ずつあればAliceと同じものを選んでいけば勝てる。さすがにこれで正解というわけではないだろう。他にBobが勝つケースがないか探してみる。特に、合計が同じにならないケース。M=5で考えて無理そうだったので、modがわかりやすいM=10で考えていると、7 2 8 3という差が5のペアが2つあるケースを思いつく。これはBobが勝てる。毎回modの差を5だけ変化させることができるのでそれが偶数回なら勝ち。じゃあMの約数で同様のことができる?特に、Mが奇数のときにBobの勝ち筋がある?少し試すと、約数が2より大きいときはAliceに回避されてしまう。2以外の約数は同様の方法では使えない。もう時間もないので、これ以外にBobの勝ち筋はないとして実装する。同じ数で合わせるのとM/2違いのペアで合わせるのと2種類あるけど、少し試して同じ数で合わせるのを優先して問題なさそう。mapで各数が何個あるか調べ、個数をmod 2にする。Mが偶数ならM/2未満のものについて自分よりM/2大きいものがあれば両方0にする(ペアを取り除いたので高々1個しかない)。mapの表面しかいじってないからイテレータは壊れないはず。実現したいことは固まってるのにコードに落とすのけっこうむずくてドキドキしてた。こういう実装力はARCの本質という気がする。最後、何も残ってなくてM/2ペアを作った個数が偶数ならBobの勝ち。そうでないときはたぶんAliceの勝ち。AC。

こんなずっこい取り方して黄パフォに届かないのやべえな。

F - 998244353 → 1000000007

(追記)モンゴメリ乗算というヒントを得て簡単そうだと思いやってみたが全然できなかった。まず998244353で割る処理が書けない。解説を見て、あまりを引いたあとでmod 2^64での逆元を掛ければいいと知る。rem命令ってそう使うのね。あと、最上位ビットとかを得る方法があればいいのだが、わからない。解説を見ると、1000000007以上かの判定をする方法が書いてあった(1000000007でなくても使える方法)。1000000007を引いて負になるなら2^64が足されるからmod 998244353での値の振る舞いが変わる。ここでもremを使っている。普通のコンピュータを相手にしてるときは使わない発想なのでこれは相当思いつかない。998244353と1000000007にばかり気を取られてしまうが、2^64もあった。ここの処理はかなりややこしかった。解説を見たところ以外にも、簡単には処理できない問題がいくつも現れていた。モンゴメリ乗算自体は今も全然わかってなくて、C++コンパイラの除算の最適化で使われる方法あるいはACLのmodintで使われている方法が頭にあったうえで解法ツイートを見て大まかな方針が立ったという感じ。

具体的な解法。引き算は符号反転して足せばいい。符号反転は2^64-1(~0ULLと書ける)を掛ければいい。逆元はextgcdを貼るが、数が2^64と大きいので1段目は手で書いて2段目からextgcdに投げる。逆元を掛ければ1になる(当たり前)。方針としては、A*Bを1000000007で割った商を多少誤差があってもいいので求めたい。998244353で割ることはできるので、A*B/998244353*(998244353^2/1000000007)/998244353として求める(除算は切り捨て)。こうして求めた値は、正しい商より大きくなることはない(切り捨てているので)(あんま考えてなかったけど、正確には丸める前の値以下であることが保証され商はそういう整数の中で最大のものだからOK)。どのくらい小さくなりうるかだが、10^9程度同士の積をとるときに高々1ずつ小さいなら2*10^9程度、その後の割り算でこの誤差も割られるので、割り算の1未満の誤差と合わせて3程度、4未満には収まっている(実際にはもっと誤差は小さい)。ということで、その小さいかもしれない商に1000000007を掛けてA*Bから引いたら、1000000007以上であるなら1000000007を引くという処理を4回やる(今気づいたけど誤差は整数なので4未満なら3以下なんだから3回でよかった)。これでAC。実装上は、デバッグできるよう出力と同時に計算も実行し、出力はせずにランダムテストを回すこともできるようにした。

最初は簡単だと思ってたけど、解説を見たうえで1日くらいかかってるので、コンテスト中に通すのはやっぱりバケモン。