時間を使い切ってのノンペナ全完さすがに嬉しい。
A - 信号機/Trafic Light
ややこしいので、言われた通りに書く。
解説見たらシンプルに書けるんだね。意味を考えればそりゃそうだ。
B - クレジット/Credits
2桁以下の場合は0が答え。そうでないときは末尾の2文字を削ればいい。
C - 偏ったサイコロ/Biased Dice
6^3通り全部の確率を求めて足していけばいい。
D - 採点 / Marking
こういう形式の問題、解法の正しさを確信しづらくて見ただけで不安になる(今回の場合だと、グラフが与えられるとは限らないのが不安)。まあ、2つの条件を満たすかチェックするだけではありそう。1つめの条件によってN頂点M辺のグラフであることが保証されそうなので、あとはそれが単純グラフかをチェックすればいい。
E - 棒倒しゲーム/Hitting Stick Game
これもふわふわしていて嫌。スコアの列が与えられたらゲームの進行が一意に定まるので、シミュレーションしていけばいい。ちょうどRラウンドを終え、次のラウンドが始まっていなければよい(サンプルに頼る)。
F - 薬剤師 / Pharmacist
問題文は長いが、頑張って読めばシンプル。ただ、難しい。人が持っているアレルゲンの数の総和が2*10^5以下であることに注目する。あるアレルゲンを持つ薬は高々N個なので、全探索できる。あとは、使える薬の中で効き目が最大のもののインデックスを求める。
あー、自分は特定のアレルゲンを持つ薬のリストをvectorに入れてたけど、解説のやり方スマートだな。でかい情報を持っていても必要な情報が高速に得られることもある。この問題ほんとに難しい。
G - Wildcards
Tとしてあり得るものが実は少ないので、全探索してunordered_mapでカウントとかできる。高速化したいならソートしてもよかったな。
H - 3種の硬貨/Three Types of Coins
トイレに行った。ヤバめのナップサックかと思ったけど、銅貨をj枚使ったときの最大価値で普通にDPできるんだね。いや銀貨の価値が高いけど枚数制限があるのは銅貨って、いじわるすぎる設定だと思って翻弄されたよ。各硬貨の枚数を12bitずつ持つかとか思ってたけど銀貨はもっと多く使うことがあるし銅貨の枚数はDPの状態で持ってるから要らなかった(ここで使う言葉、「状態」でいい?)。DPテーブルは全部10^9で初期化していい(銅貨を最初に何枚か捨ててもいいとしても答えは変わらない)。
I - 毎日のリンゴ / Buying Apple Everyday
floor_sum使ったことほぼないけど、露骨で簡単な練習問題を用意してくれてありがとう。
あ、観察して正面から解く方法もあるのか。正直すまなかった。
J - スプリンクラー/Sprinkler
横辺が円と交点を持つ場合、縦辺が円と交点を持つ場合、4通りくらいに場合分けすればよさそうだと思う。簡単そうだけど、いざやるとなるとけっこうきつい。割合を答える問題なので、円の半径は1、長方形は縦長でない、H,Wは辺の長さの半分、としておく。場合分けのやり方でかなり迷った。まず、長方形が円を完全に含む場合をやっておく。そうでないとき横辺(を左右に伸ばした直線)と円の交点があるので、円の中心からその交点へ線を引いてその角度をasinで求める。角度がわかれば扇形の面積もわかるしcosで座標もわかる。ここで3つに場合分け。円が完全に長方形を含む場合は簡単。Wが1以上だったら交点は1個だけで、三角形と扇形の面積の和。どっちも2で割る(どっちも三角形みがある)。そうでないときは交点が2つある。こっちも角度を求めて、三角形と扇形と三角形の面積の和。
はー、はみ出たぶんを縦横別々に求めることができるのか。
K - 連結チェック/Checking Connectivity
削除はUnionFindで逆からやればいいし、追加が10個以下なら10回やればいい。大まかな方針はすぐ見えるが、まあ実装はかなりきつい。クエリ先読みして、全部の辺をsort, uniqueしてlower_boundでどの辺かを特定して存在するかどうかを管理する。クエリを順方向に見ていって、追加クエリが来たらその直前から遡る。最後にダミーの追加クエリを入れておくことで全部処理できる。
L - 展覧会 / Exhibition
できるわけないって思ったけど、最短経路問題にできないかと思ってからしばらく考えていたら単純なDPになってしまった。これ解けるんだあ。全体で何個展示するかmod 3で固定すれば、両側に対応できる。これまでに何個展示したか3通りを左から更新していく。N+1個の位置について、9通りの左右の状態に対しどれだけ加点するか前計算しておく(というか加点はそのように持つ)。
M - シリーズ / series
とりあえずソートして考えてみるとDPできそう。区間更新と思わせて、1点更新区間minでいけるやつだ。端からの区間minしか要らないので、せっかくなのでBITを使う。1冊ずつ買うのも区間として一緒に扱う。0からNへの最短経路問題だと思うことにする。Lでソートして、LとLより右の(例えば、5巻まで持っているなら3巻まで持っているは言えるので)好きな場所からRへ行く。Rを更新するときの意味は、ここより左は全部このコストで行けるというもの。BITの向きを逆に使う必要があることに気づいて大変だった。
あー、戻る辺を置けばダイクストラ法でできるのか。
N - 上からと横から/From Above and From the Side
ここまで順番に解いてきたが、本格的に難しくなってきたのでNをOを交互に考えていた。
要するにcを押し込んではみ出たやつをSに追加していくという処理。更新したところだけ情報を持つとしても縦横ぐちゃぐちゃになるので無理そう。平方分割みたいな発想で、短い側を愚直にやるというのもぐちゃぐちゃになりそう。
横長だったら転置して縦長とする。縦方向はどれだけrotateしたかを持っておく。横方向は愚直。ターゲットがどこに移動したかはわかるので実は操作ができる。
ひょえ~、dequeでそんなずるができるのか。結局やってることは自分とそんな変わらなそうだけど。
O - 2個のボール/Pick Two Numbers
自分の知らない畳み込みかなあという印象だった。popcountは置いといてOR畳み込みくらいはできないかなあと、Library CheckerのConvolutionを見に行くと、なんとANDを自分がAC済みだった。自分のコードを見ても何もわからないので、関数名のfztでググると高速ゼータ変換で、しばらくわからなかったが、なるほどこれは累積和だ。ビットで見て含まれるものの合計を計算して、掛け算する(ANDがそれに含まれるものの通り数がわかる)。そうして逆変換すれば元の問題の答えになっている。すご。ORに書き換えるのも簡単そうだけど、時間もないのでAND畳み込みを利用してOR畳み込みをする。popcountの扱いがまた難しかったが、もうpopcountでN+1個に分けてそれぞれ高速ゼータ変換してしまう。N^2通りくらい掛け算して足す。logを3個付けるのはさすがにまずいが、線形性とやらで足してから逆変換すればlogは2個で済む。まず3個のコードを書いてサンプルが合わなかったが、2個に直したらなぜか通ったので提出してAC。
(追記)サンプル合わなかったのは、+=とすべきところを=にしてたからだった。