ABC308 参加記

6完 33:42 388位

ライブラリをなにも理解していないことをさらしてしまった

A New Scheme

ABCの配点として正しいかどうかってことですね

言われたとおりにif文を書いて判定

(AC 2:35)

B Default Price

いつものBですね

それぞれの色について何円なのか保存しておけば、ループで調べれば解けます

map使った方が直感的なのでそうしたけど

(AC 5:49)

C Standings

これむずいと思う、茶色の僕は知らなかった

C++だとsort関数に比較する関数を渡してあげることができるので、これを定義します

Ai / (Ai + Bi) < Aj / (Aj + Bj)ですが、誤差が怖いので分母を払ってあげて

Ai * (Aj + Bj) < Aj * (Ai + Bi)とすればよいです

これに加えて、indexの比較も同じ関数内に入れておけばOKです

(解説のようなstable_sortではなく、indexの比較をいれたもの)

Submission #43100882 - AtCoder Beginner Contest 308

(AC 11:35)

D Snuke Maze

いつものD

s -> n -> u -> k -> e -> s ... と動いていくことになるので、それぞれ隣り合うものをみて辺を張れるか判定してあげて、張れるなら張ります

そうしてグラフを作ってあげれば、あとは(1,1)からBFSやDFSをして(H,W)に到達できるかみるとよいです

※陽にグラフをつくらなくても、「マスの上を動かしていって動ける＆まだ行ってない場所に行く」を繰り返せばよいです

(AC 19:18)

E MEX

典型：「3つのものは真ん中を固定」

何度も出題されていますが、こういうタイプの数え上げ・和の計算は真ん中を決めるとうまくいくことが多いです

類題

C - Snuke Festival

今回も真ん中のEの位置を決めます

そうすると、「自分より左にあるM」と「自分より右にあるX」しか考えなくてよくなります

これは左右からの累積和を使って簡単に個数をまとめられるのでうれしいです

この問題ではこれに＋αがあります

mexは0,1,2のうちどれがあって、どれがないか？がわかればよいので、「自分より左にあるM」のうち(0の個数、1の個数、2の個数)を求めて、Xについても同様に求めればよいです

あとは各Eについて、Mでどの数字を採用するか・Xでどの数字を採用するかを総当たりして個数を加算してあげれば解けます

(AC 27:43)

F Vouchers

貪欲っぽい問題は正しい貪欲を思いつくのが難しいものも多いですが、「制限の厳しいものから考える」というアプローチが有効なことがそれなりにあります

(この問題に限らず)おきもちとして、いきなりめちゃくちゃ選択肢があるものを考えるのは大変です

なので選択肢が少ないものを考えて、「この厳しい条件ではこうするのがベスト」という方法を見つけてみます

それが全体の問題を解くときに使えないか？と考えると解法が見えることがあります

あらためて今回の問題を考えると、高い商品にはたくさんクーポンを使えるが、安い商品には使えるクーポンが少ないことが分かります

また、安い商品に使えるクーポンは高い商品にも使えるので、使えるクーポンの集合はどんどん増えていくことになります(=あとで使えなくなるから最善ではないけど早めに使わないといけない、ということは起こりません)

よって、安い順にみていって「その時に使えるクーポンのうち最も割引額が大きいものを使う」として問題ありません

これはpriority_queueを使うと実装できます

類題

D - Summer Vacation

(AC 33:42)

G Minimum Xor Pair Query

想定解法が天才だった

これは思いつかなかったのでBinary Trie解法を書きます

まず、xorの典型考察として「桁ごとに考える」というものがあります

xorをできるだけ減らそうとすると、k桁目までいっしょでその部分が0になるとうれしいので、「k桁目まで同じものがある」かどうかを調べたくなります

これはBinary Trieでやっていることと同じなので、Binary Trieを使って解けそうだと思います

もう少し詳しく考えていきます

k桁目まで同じものが2つあるとすると、そのxorは答えの候補になります

Binary Trieでは各ノードに「あてはまる数字の個数」「あてはまる数字どれか1つ」を持つことにします

addクエリでは、そのノードの「あてはまる数字どれか1つ」がないならば、addする値で更新します

また、「該当する数字の個数」が2になったときに、2つの子ノードがあればそれぞれの「あてはまる数字どれか1つ」のxorをmultisetに加えます

もしくは、葉ノードの「該当する数字の個数」が2(=等しい値が存在する)のときに0をmultisetに加えます

3,4...など2より大きいときにもっと小さい値ができる可能性がありますが、それはもっと深いノードで2になるところがある or 葉ノードに2つ以上の値があり0になる、のどちらかなので考えなくてよいです

addクエリは比較的簡単ですが、eraseクエリはちょっと面倒かもしれません

大枠はaddクエリと同じですが、「あてはまる数字どれか1つ」を管理する必要があります

「あてはまる数字どれか1つ」が今消そうとしている数かもしれません

その場合は、子ノードの「あてはまる数字どれか1つ」を適当に選んで更新してあげればよいです

ただし、更新した場合はもともとmultisetにあったxorとは異なる可能性があるので、あらかじめそのノードで加えていたxorの値を取り除いてから、新しい値を加えることになります

とりあえず書いたんですが、文章だとかなり煩雑なので実装も置いておきます

(実装のadhocと書かれている部分がBinary Trieに書き加えた部分です)

atcoder.jp

(AC --:--)

総括

Binary Trieやっと実装がわかってきた

ARC109-E 1D Reversi Builder プチ解説

ARC109-E 1D Reversi Builder の解法が少し既存の解説と違ったので紹介します

備忘録的な感じ

参考リンク

atcoder.jp

drken1215.hatenablog.com

問題概要・考察の初歩は上記のリンクをご覧ください

盤面を固定した結果はけんちょんさんのブログの「正攻法」欄に記載されています

以下の説明は、この「正攻法」の考察がなされていることを前提とします

まず、多項式時間で「正攻法」の数え上げができるか考えてみます

以下の考察は左端が黒・右端が白であることを仮定します

スタートの位置を固定します

ゲーム終了時の黒い石の個数は、左から何個黒が続くか、右から何個白が続くかの2つの情報でわかります

これらをそれぞれ , とします(けんちょんさんの記事と同様)

よって、, , の3つを定めればゲーム終了時の黒い石の個数がわかるので、 で数え上げることができます

ただし、今回の問題ではなので、程度まで高速化する必要があります

ここでを~まで動かしながら計算していくことを考えます

まず、 = のときは ゲーム終了時の黒い石の個数はになります

を決め打って、そのときの値を計算しておきましょう

一番左が黒、右から個が白 = 右から個目は黒になるので、自由に決められる色は(, )個あり、この値をとすると、() × を足し合わせればよいです

それでは、を1つずつ進めていきましょう

を1つずつ進めていくと、では終了時に個黒い石があったのに、では終了時に個しか黒い石がない盤面が出てきます

その一方で、左端を黒に固定しているので、よりもで終了時の黒い石が多くなることはありません

そこで、では終了時に個黒い石があったのに、では終了時に個しか黒い石がない盤面をまとめて数えることを考えます

そのような変化が起こるのは以下の2パターンになります

・ 

・ 

ほとんど考え方は同じなので、 の場合のみ説明します

とおきます (こちらの場合は条件よりは存在できないことに注意)

この条件を満たす盤面の個数を考えます

左から個は黒、左から番目は白、右から個は白、右から番目は黒になることから、自由に決められるのは個になります

※からの距離が以上の場所はすでにきまっていると考えるのがわかりやすいかもしれません

よって、を固定した時、からになるタイミングで、() × だけ終了時の黒い石の個数が減少します

あるについて、とることのできるの範囲は単一の区間になるので、あらかじめ各のときの値を計算し、累積和を求めておくことでからに変わるときの差分を()で計算できるので、全体を()で求めることができます

実装例

atcoder.jp

ABC302 参加記

7完64:09 149位

Eで多少詰まったけどFGをまあまあの速度で通せてセーフ

A Attack

切り上げは (A + B - 1) / Bでできるやつ

Aでforが出るならlong long もでていいよね

(AC 2:54)

B Find snuke

250点はなんだと思ってみると重実装がおいてある

とはいっても、楽することはできて

dx = {-1, 0 , 1}

dy = {-1, 0, 1}

の全組み合わせを、すべてのマスを始点として試せばよいです

8方向書くときには↑のような定義おすすめです(dx = dy = 0は適切に省く)

(AC 8:12)

C Almost Equal

えー、地味にむずくない？と思ったら制約に答えが書いてありました

N ≦ 8なので順列全探索ができます

判定は1文字ずつみて素直にやるだけ

(AC 11:46)

D Impartial Gift

「2つ選びます」「3つ選びます」みたいな選ぶ個数が少ないタイプの問題は、とりあえず1つ選んでしまって、そこから最適なものを考えるとうまくいくことが多いです

今回も1つ決めてしまいましょう

Aiを1つ決めると、最適なのはBi ≦ Ai + D  となるもののうち最大のBiです

(もしそのBiがAi-Dより小さいなら選べないことに注意)

これは二分探索で簡単に求めることができます

Biを1つ決めるものも試して最大値をとればよいです

(AC 19:33)

E Isolation

辺をくっつけて連結成分数 -> Union Findか？と思ったけどただの過学習でした

辺を頻繁につけたり外すのはUnionFindだとあまり得意ではないので、少し違うかなと思って普通に考察します

※1回だけ外すとかだと逆順にみるのが有効なことが多い？

2番目のクエリの辺を削除するというのが大変かな？と思うのですが、もともと辺がないし追加されるのもクエリにつき1辺なので、愚直に削除しても間に合いそうです

では、2番目のクエリの処理の仕方を詰めていきます

普通に隣接リスト(vector<vector<int>> G(N) のような形)で持つことを考えます

頂点iにつながっているものをすべて削除するクエリが与えられるとき、G[i]はすべて削除すればよいです

しかし、iとつながっている先の頂点でもiを削除しないといけません

これを普通にやるとvectorからiを探索して削除しないといけないので、最悪O(N)かかってしまいます

ここでsetを使うと「iを探索して削除」をO(logN)で行えるので、高速になります

よって、つながっている辺をsetで管理することでクエリの各処理がO(logN)で行えるので全体でO(QlogN)になり、十分間に合います

(AC 30:35)

F Merge Set

何で思いついたか説明しづらい...過去問演習の効果としか

同じ数字を含むものはつながっていてほしいという"おきもち"を抱くので、そうできるように考えます

左側に1~Nの番号、右側に1~Mの数字をあてはめた二部グラフを考えます

i番目の集合にjが含まれるなら、左側のi と 右側のj を結びます

(この時点では完全な解法は思いついていないですが、このようなグラフをつくって考察する価値があるだろうという読みでつくっています)

このグラフを使って考察すると、(当たり前ですが)右側の1から1回操作すると左側の「1を含む集合」にたどり着くことができます

同様にグラフを使って考察すると、「iとjを含むための回数」 = 「右側のiから右側のjまでの最短路 / 2 - 1」になることがわかります

(ここはサンプルをもとにいろいろ手を動かしてみるとわかりやすいと思います)

よって、このグラフで最短経路問題を解けばいいのでBFS, Dijkstraなどを使えばよいです 

(AC 38:47)

G Sort from 1 to 4

めちゃめちゃ解かれていたのであせった...

まず広義単調増加となる列は一意に定まるので、それは求めておきます

そもそも、もとの列と広義単調増加の列で値が等しいものは動かすのが無駄なのでそのままにしておきます

そうでないものとして、以下の3パターンが考えられます

(i) 1 <-> 2 のように2点swapで解決する(=1回操作)

(ii) 1 -> 2 -> 3 -> 1のように3点をぐるっと回すと解決する(=2回操作)

(iii) 1 -> 2 -> 3 -> 4 -> 1のように4点をぐるっと回すと解決する(=3回操作)

まず、(i)はして損することがなさそうなので優先することにします

問題は(ii)と(iii)ですが、可能であれば(ii)が優先できたらいいですが、(ii)を優先した結果(iii)が増えるということがあると困ります

順位表をみるとよくわからない貪欲が落ちそうな割には、ペナが少なめです(嘘貪欲で落ちるならAC / Submit = 1 : 2~3になりそうですが、 160/200くらいでした)

こう考えると、適当な貪欲で通りそうなので(ii)を優先することにします

(ii)の中の優先順位もよくわからないんですが、普通に貪欲にしてみます

具体的な実装としては、3重ループで(1,2,3),(1,4,2)など組を列挙してそれがあれば処理するようにします

「組に該当するものがあるかどうか？」は

count[i][j] := 広義単調増加列だとiの位置に、jが存在する個数

をあらかじめ計算しておけばよいです

(i) -> (ii) -> (iii)の順に貪欲に処理していって提出すると通ります(証明AC)

(AC 64:09)

総括

Eの過学習よくないね

ABC301 参加記

5完45:27 125位

Cで詰まった＆Fが3分間に合わなかったのにこの順位なのびっくり

落ちたからやめた人多そう

A Overall Winner

素直にやります

A,Tの数を数えて片方が大きいならそれを出力、等しいなら後ろにないほうでOK

(AC 2:17)

B Fill the Gaps

これも素直にやる

とりあえず最初の数だけ入れておいて、あとは間の数を定義通りループで入れていく

(AC 5:07)

C AtCoder Cards

貪欲の自信がなかった...

とりあえず、"@atcoder" に含まれないもので数が異なるものがあるとどうしようもないのでNoです

あとはこれらをうまくそろえていけばよくて、足りてないものを@で補填していくのが最善になります

が、なぜか本番で最善かわからなかったのでフローで殴りました

スタート、ゴール、S,Tのa~z,@にあたるものを頂点とします

スタート -> Sの各文字：容量=Sにある文字の個数

Sの各文字->Tの各文字：容量=INF

　"atcoder"でない小文字は同じ文字にだけ

　"atcoder"にある小文字は同じ文字+@に

　@は@,atcoderのすべてに

Tの各文字->ゴール：容量=Tにある文字の個数

として流量がNであればよいです

(AC 26:51)

D Bitmask

こっちのほうが簡単では？

まず1のところはどうしようもないので、加算しておきます

あとは?のところを変えていくのですが、1にできるなら変えるのが最善です

難易度C>>>Dと思ったけどそんなことなかった

(AC 29:47)

E Pac-Takahashi

やることわかるけど実装重め

まず問題文に「18個以下」と強調して書いてある＆最短距離的なので、bitDP使うんだろうな～と思います

お菓子を取る順番を決めてしまえば、それぞれの最短距離を求めればいいだけですがこれを愚直にやるとO(K!) [K=お菓子の個数]になります

こういう順列全探索の高速化はbitDPが相性がいいことが知られています

つまり、順番はそこまで大事でなくて「どこを通ったか/通っていないか」が重要なので、その情報をbitで持つことで計算量をO(2^K)に改善できます

それぞれの最短距離を求めればいいだけ、と書いたのですがここをちゃんと考えておきます

もう少しサイズが小さければワーシャルフロイドを使って全ペアの最短距離をO((HW)^3)で計算できますが、今回の制約では厳しいです

重要なのはお菓子のあるマス(+スタート・ゴール)への距離なので、このK+2マスについてわかればよいです

ということで、それぞれのマスを始点として最短経路を計算します(BFS, Dijkstraなど)

それぞれの最短距離がわかれば、あとはbitDP(巡回セールスマン問題と同じ)で解くことができます

(AC 45:27)

F Anti-DDoS

いかにも設定から作られてそうですが、適度な難易度でおもしろかった

「(連続でない)部分列としてTが存在するSの個数」の典型として、

dp[i][j] := Sのi文字目まで見てTのj文字目まで存在する通り数

と定義して計算するというものがあります

例：?を含むSを書き換えて、"atcoder"が含まれるのは何通りか？

今回も考え方としては同じです

dp[i][j] := Sのi文字目まで見て"DDoS"のj文字目まで存在する通り数、とします

3,4文字目のo,Sは小文字・大文字という条件しかないので簡単です

ただし、1,2文字目のDDは「1文字目と2文字目が等しい」という条件がついているので少し難しいです

DDの部分を解決することを考えましょう

愚直に考えるとアルファベットのi文字目があるか？という情報をもってbitDPができそうですが、これは2^26必要で計算量が厳しそうです

そのため具体的に「どの文字があるか？」と持つことは諦めて「文字が何種類あるか？」を持つことを考えます

dp[i][j][k] :=  Sのi文字目まで見て"DDoS"のj文字目まで存在して、今までに出現した大文字の種類数がkである通り数

と定義して計算していきます

もしS[i]=?であれば、今まで出現した文字とかぶるorかぶらないの2パターンを考えます

かぶるときは、どの文字とかぶるかがk通りあるので、

dp[i][2][k] += dp[i][1][k] * k と遷移します

かぶらないときは、同様に考えて

dp[i][1][k+1] += dp[i][1][k] * (26 - k) と遷移します

もしS[i]=大文字であれば、今まで出現した文字とかぶるorかぶらないの2パターンを考えます

少しここが厄介なので状況を整理します

i-1文字目までで、すでに決まっている(=?でない)大文字がA種類

i-1文字目までで、?から大文字に変えた箇所がB個(これはどの大文字ともかぶらない)

とします

S[i]が今までに登場した大文字とかぶる確率を考えます

もし、すでに決まっているA種類のものと同じであれば確率は1です

そうでなければ、B / (26 - A)になります

この確率をかけてdpの遷移をしてあげればよいです

また、かぶらない確率は上の結果から容易に計算できます

最終的にはdp[N][0][k] + dp[N][1][k] + dp[N][2][k] + dp[N][3][k]を出力すればACとなります

(AC 108:37)

総括

Fちゃんと通したかった

ABC297 参加記

7完60:17 + 2ペナ 105位

FGをサクッと片付けたのがえらい、Eでハマったのはダメ...

A Double Click

forやるだけ、言われてみればダブルクリックの時間を快適にするの絶妙な調整だよね

(AC 1:50)

C chess960

元ネタを知らなかったので、1行でチェスするの何が面白いんだと思った

解くのは条件を丁寧に実装するだけ

2重ループ+3重ループで解きました

(AC 5:20)

C PC on the Table

PCTやりたいだけ

左から貪欲に詰めていけば問題ないので、一つ一つ変えていきましょう

(AC 7:33)

D Count Subtractions

直前のARC-Bっぽさを感じさせるけど、解法はちょっと違う

大小関係が入れ替わるまでは操作をまとめて繰り返してあげればよいです

やっていることはユークリッドの互除法とだいたい同じなはず(?)で、高速に終わります

(AC 11:35)

E Kth Takoyaki Set

Twitterで最近流れていた Ai + AjのうちK番目みたいな問題に思いをはせながら解いた

できる可能性がある候補としては現在の値をXとして、X+Ai(1≦i≦N)になるので、これをいい感じに調べていきます

具体的には、あまり大きいと調べる必要がないのでpriority_queueにつっこみながら小さい順に調べていくことにします

今までに出現した値をset, priority_queueで管理しておきます

もし今まで出現した値がK個を超えたら、K番目以上のものは調べる必要はありません

K番目の値以上になるものを加えないようにすると、計算量が抑えられて間に合います

(AC 24:36)

F Minumum Bounding Box 2

期待値を直接計算するのは難しそうなので、総和を求めることにします

解説と方針は違いますが、縦h、横wを固定して「最小長方形が縦h,横wになる通り数」を数え上げることにします

すごくざっくり考えるとh×wマスからK個のマスを選ぶので、二項係数を用いてhwCKになりそうですが、たとえば上一行にひとつもない場合など当てはまらないこともあります

ダメな条件を考えると

・上一行にない

・下一行にない

・左一列にない

・右一列にない

のうちどれか一つでもあるとダメであることが分かります

こうやって整理すると「A,B,C,Dのうち一つでも満たす通り数」を計算する問題になっているので、これは包除原理で解くことができます

bit演算を用いて縦・横の縮め方を管理すれば比較的楽に書けます

実装例

Submission #40507604 - AtCoder Beginner Contest 297

(AC 46:49)

G Constrained Nim 2

各ゲームが独立しているので、それぞれのGrundy数を求めてXORをとるのがよさそうだな～と思います

Grundy数を求めたいので、とりあえず手元で実験してみます

L=3, R=5とすると、Grundy数が0,0,0,1,1,1,2,2,0,0,0,1,1,1,2,2...となって

実験したときの遷移する先も考えると、0がL個、1がL個、2がL個 ...という風になっていくはずで、長さは(L+R)個でループしていることが分かります

変な例外があったら悲しいんですが、とりあえずあってそうなのでGrundy数をAi%(L+R)/Lとして実装します

サンプルが弱くて心配になりますが、投げるとAC

(AC 60:17)

総括

F黄色かと思ったらギリ青色だった

ARC159 参加記

ABD3完 74:43 + 3ペナ 249位

配点がC<Dで、Dが得意だったおかげで救われた

ひさしぶりのARCでレートプラス

A Copy and Paste Graph

問題設定が少し複雑なので、手元で書いてどういう操作をしているかわかりやすくします

たとえばN=3, K=2のときに、A1,1=1の場合を考えます(サンプル1)

A1,1=1ならば、A1,(1+N) = A1,4 = 1のようになるので、できる操作は

「Ai,j=1ならば、Nで割ったあまりがi -> Nで割ったあまりがj　に自由に移動できる」

ということがわかります

よって、「あまりiからあまりjへの最短経路」を求めることができればよく、これはもとのAに対して、0をINFに変換したうえでワ―シャルフロイドをすればよいです

(AC 10:27)

B GCD Subtraction

一瞬愚直でいいかも？と思いますが、そのとき順位表を見るとおおよそ50AC / 400Tryだったので、さすがに愚直を落とすようにしているんだなと思って考察します

大小関係はどちらでもいいので、あらかじめA≦Bとしておきます

まず、現在のgcd=Gとして、A-G, B-Gをしてもgcdが減少することがないということがわかります(常にGの倍数ではあるので)

常にGの倍数であることを利用すると、次に到達できるgcdは絞れそうかな～と思います

ただ、G=1のときなどに候補がすごく多くなってしまうので困ります

もう少し考えると、gcd(A,B) = Gということは A = Gx, B = Gyと表すことができるので、B-A = G(x-y)となり、Gの候補はB-Aの約数でいいことがわかります

ここまでくるとほとんどゴールで、今のgcdをGとすると何回か進めてgcdになる可能性があるものは、B-Aの約数&Ｇで割り切れるもののうち最も到達時間が早いものになります

到達するまでの時間は、(A%d)/gで求めることができます (d = 約数の候補)

ここで算数をさぼろうとしてmodintを使ったら謎のREを踏んでハマりました...

到達時間が分かれば、それまでの回数をまとめて遷移することで操作を高速化することができるので、実行時間に間に合わせることができます

(AC 48:45)

C Permutation Addition

制約が小さいのでなにかうまくできるかな～と思っていたが、何もわからず...

N≦50にとらわれすぎてしまった感があって、ナップサックとかを考えてしまって進捗が無だったので、特に構築だと気にしすぎないようにしないと

(AC --:--)

D LIS 2

Cがきつくて見に来たら、いかにも得意そうな見た目をしているので突撃することに

まず単純な考察として、もし[li,ri]を最後に採用するならば途中で止める必要はなく、最後まで追加するのが最善になります

ここから、dp[i] := i番目の区間でriまで使った時のLISの最大値　と定義したくなります

では、遷移を考えていきます

[1,3] [6,8]のようにかぶっていない場合ではすごく簡単で dp[j] = max(dp[i]) + r - l + 1になります

[6,8] [1,3]のようにかぶっていなくても大小が逆の場合は遷移することができません

[1,3] [2,5]のようにかぶっている場合がすこし面倒です

dp[i] := i番目の区間でriまで使った時のLISの最大値 と定義すると、[1,3]から遷移するとかぶっている[2,3]のところが余分に数えてしまいます

どうすればよいか考えると、おきもちとしては

「3まで伸ばしていたのを5まで延長したい」

より抽象的にすると

「riまで伸ばしていたのをrjまで延長したい」

ということになります

これを解決するために新たなdp配列を定義します

dp2[i] := i番目の区間でriまで使った時のLISの最大値 - ri

とします

こうすると「riまで伸ばしていたのをrjまで延長したい」というおきもちに対処できます

dp2[i] + rjとすると、

「i番目の区間でriまで使った時のLISの最大値」 + rj - ri

となるためです

よって、かぶっている場合の遷移は dp[j] = max(dp2[i]) + rjとすればよいです

これらをまとめると、あらかじめ[li,ri]をriを基準にソートした位置を特定しておき、

自分より左でかぶっていないなら dp[j] = max(dp[i]) + r-l+1

自分より左でかぶっているなら dp[j] = max(dp2[i]) + r

で更新することができます(dp[j]は上の2つのmaxをとります)

(AC 74:43)

総括

C通したかったけどレート増えてうれしい

ABC292 参加記

7完84:02 + 1ペナ 125位

逆転してるExに早めに手を付けたのがよかった、Eは反省

A CAPS LOCK

前回isupperが出てたので、今回はちゃんとtoupperを使った

(AC 0:58)

B Yellow and Red Card

それぞれの人が何枚カードをもらったか管理しておけばいい

レッドカードはイエロー2枚分と考えると実装がちょっとだけ楽？

(AC 2:47)

C Four Variables

Cなのに要求知識高くてびっくりしたら、実は想定ではなかった

AB = KとなるABのペアの数が1≦K≦Nでわかれば、あとはK, N-Kの個数の和を計算すればよくなるので、「AB = KとなるABのペアの数」を求めることにします

これも解き方いろいろあると思うんですが、ぼくは調和級数でやることにしました

A=1~Nで全探索して、B=1~Nの二重ループをします

ただし、AB > Nになれば調べる必要がないので打ち切ると全体でO(NlogN)です

もっとストレートにやるなら、約数列挙そのものなのでO(N√N)でも解けますね

(AC 5:05)

D Unicyclic Components

辺の個数を持ちながらUnionFindをします、こういうの最近も出た気がする

(AC 8:45)

E Transitivity

考察1本のEだった、詰まりすぎ

まず、「a->b, b->cがあったとき、c->a」にできると誤読します(え？)

こうすると、トポロジカルソートの後ろから見るといい気がしますが、なかなか考えがまとまらず時間がたってしまいます...

よくよくみると「c->a」ではなく「a->c」であることに気づいてびっくりします

改めて考えると操作は「aから距離2の頂点cに対して、a->cの辺を張る」と言い換えられます

もう少し考えると、たとえば距離が3の点については、距離が2の点に張った辺を用いることで距離2で到達できて、また辺を張ることができます

こうしていくと、操作は「aから距離2以上の頂点cに対して、a->cの辺を張る」と言い換えられます

これだけでも解けるんですが、「距離1の頂点にはもともと張ってあるだけ」と考えると、aから辺を張るのは「aから距離1以上の頂点」=「aから到達できる頂点」であることがわかります

よって、各頂点から毎回BFSなりDFSなりして到達判定をしてあげればO(NM)で計算できます

自分のところに戻ってくるところに間違って加算してしまって考察があっているのに悩んでしまった...

(AC 41:30)

F Regular Triangle Inside a Rectangle

この位置にある幾何なので、計算式一発ではないんだろうな(もしくはそれはあるけど、想定ではない)と思います

とりあえずよくわからないので「長方形　正三角形　内部」と調べると、正方形の中を三角形を動かしている画像がたくさん見つかります

それらから、三角形の傾け方をいろいろ調べて中にはまればよさそうだなと思って詰めていきます

1つの角を長方形の角に固定し、三角形の傾ける角度をθとします

すると、三角形の辺の長さをLとしたとき

横の長さはLcosθ、縦の長さはLcos(30°-θ)になります

※正三角形の1つの角度は60°であるため、90-60-θ

長方形内に入るためには、A ≧ Lcos(30°-θ)、 B≧Lcosθになる必要があります

ここで 0≦θ≦30°の範囲で、θが大きくなるとcosθは小さくなっていくので、

θはB≧Lcosθを満たす中で最も小さなθ(大きなcosθ)をとりたいです

そうすると条件を満たす可能性がある中でcos(30°-θ)が最小になります

よって、正三角形の1辺の長さLを二分探索する中で、それが達成できるか判定するためにθの二分探索をおこなえばよいです

epsの誤差を適当に1e-5にしたら、出力誤差が1e-9であることを忘れていて精度ミスで1敗

(AC 64:18)

G Count Strictly Increasing Sequences

とりあえず制約が小さいので雑に考えてみます

まず1番大きい桁は明らかに単調非減少になっている必要があるので、0,1,2,3,4,5,6,7,8,9の位置を探索できないかな～と思いますが、40C9ですでにかなり大きな値になってしまうので少し厳しそうです

1個決めるときに前の値が必要になると思うんですが、それを知ろうと思ったら2個前で...となって難しくなってしまい、わかりませんでした

Exもそれなりに解かれているのでそっちに向かいました

(AC --:--)

Ex Rating Estimator

見るだけ見るか～と思って、目を通します

レーティングがBを超える条件はA1~Aiまでの和 / i ≧Bなので、これを変形して

A1~Aiまでの和 ≧B*i

さらに変形して

A1~Aiまでの和 - B*i ≧ 0となります

こうすると、左側の式がはじめて0以上になるindexを求めればいいことが分かります

「クエリが与えられて更新がいる」＆「はじめてtrueになるindex」を処理したいので、遅延セグメント木がうまくできそうです

ここまでいくと後はそんなに難しくなくて、あらかじめ各ノードに -B*iをセットしておいて、それぞれのクエリでは区間addなどを用いて更新してあげればよいです

はじめて0以上になるindexについては、区間maxの遅延セグメント木を用意したうえで(セグメント木上の)二分探索をしてあげればよいです

ちなみに、AtCoderではC++のような高速な言語だと、普通に二分探索してO(N (logN)^2)でも間に合うことが多いです

(AC 84:20)

総括

Ex初ACめでたい