naoya_t@hatenablog

いわゆるチラシノウラであります

〈ABC埋め〉C問題+D問題集中アタック

ABC単独開催回のC問題・D問題を解いておく

ABC 089

C - March (300)

頭文字がM,A,R,C,Hな人数をそれぞれ数えて
5C3のパターンをnext_permutationで回しながら3つずつの積を加算していったもの
→AC 5'31
https://beta.atcoder.jp/contests/abc089/submissions/2695717

解説解では5C3のパターンをP[10],Q[10],R[10]に入れてたけどこれは自分だとバグりそう…

D - Practical Skill Test (400)

それぞれの数字が書かれている座標を調べて配列に入れておいてシミュレーション
→TLE(1) 8'42
https://beta.atcoder.jp/contests/abc089/submissions/2699609
ああ、D=1だと間に合わないか
累積和を取っておくしかないな
→AC 18'31+penalty
https://beta.atcoder.jp/contests/abc089/submissions/2699625

解説解も同様

ABC 088

C - Takahashi's Information (300)

  • 行どうしの差(3C2通り)を取って3要素が同じであることを調べる
  • 列どうしの差(3C2通り)を取って3要素が同じであることを調べる

→AC 5'36
https://beta.atcoder.jp/contests/abc088/submissions/2695748

解説解ではa_1=0を仮定して考えてるけど、確かにそれでconsistencyを調べたほうが楽か。

D - Grid Repainting (400)

  • 左上から右下までの最短距離dを求める。たどり着けない場合は-1(それ忘れててWA(1)した)
  • どんな経路を選ぼうが、通過に必要なのはd+1コマ
  • H×W - (d+1) - (#のコマ)が答え

→AC 11'36+penalty
https://beta.atcoder.jp/contests/abc088/submissions/2699653

解説解も同様

ABC 084

C - Special Trains (300)

シミュレーションするだけなんだけど
題意が捉えられてなくて手間取った
→AC 10'29
https://beta.atcoder.jp/contests/abc084/submissions/2695785

解説解も同様だけど(t+Fj-(t%Fj) みたいにやるのスマートだな

D - 2017-like Number (400)

  • エラトステネスの篩で1e5までの素数をあらかじめ求めておく(setに入れておく)
  • 3〜99999の奇数について「2017に似た数」かどうかを調べておいて、個数の累積和を求めておく
  • クエリがO(1)で処理できるのでめでたしめでたし。

→AC 6'07
https://beta.atcoder.jp/contests/abc084/submissions/2699665


ABC 075

C - Bridge (300)

橋候補として1本ずつ選び、それ以外の辺を繋いだグラフが連結かどうかを調べる。
(WFしてノード0からそれ以外にたどり着けるか見ている。O(N^4)。)
→AC 8'06
https://beta.atcoder.jp/contests/abc075/submissions/2695825

解説より

グラフの連結判定には、深さ優先探索(DFS)、幅優先探索(BFS)、Union find、ワーシャルフロイド法などが使えます。今回の問題の制約であれば、ここで挙げたアルゴリズムのどれを使っても、十分に間に合います。

WFが先に浮かんでUnionFindは考えもしなかった…

D - Axis-Parallel Rectangle (400)

点があるx座標は高々50種類。その中から2つ選んで長方形の幅とする。50C2=1225通り。
その範囲(inclusive)にある点についてy座標を列挙し、その中からK個(以上)選んだ時の幅の最小値を求めるのも高々50C2=1225通り。
1225^2通り調べるだけで行ける。O(N^4)。
→AC 13'38
https://beta.atcoder.jp/contests/abc075/submissions/2703222

解説解ではy座標も50個全列挙して、形を作ってからその中の点の数を数えているのでO(N^5)。

ABC 064

C - Colorful Leaderboard (300)

  • なるほどAtCoderでは3200以上になると好きな色が選べるのか
  • 0〜3199について、400ごとのbinに入ってるか入ってないか見てmincountとmaxcountをインクリメントして
  • 3200〜については、maxcountにその数だけ追加。mincountについては3199までが存在しなければ++, 存在すれば影響なし。

→AC 4'34
https://beta.atcoder.jp/contests/abc064/submissions/2695864

解説解も同様

D - Insertion (400)

  • sを前からスキャンして、足りない開き括弧の数、閉じていない開き括弧の数を数える
  • 開き括弧を可能な限り前に追加(その場で開いてもよいがどうせバランスされるのなら可能な限り前でよい)
  • 閉じ括弧を可能な限り後ろに追加(その場で閉じてもよいがどうせバランスされるのなら可能な限り後ろでよい)

→AC 5'05
https://beta.atcoder.jp/contests/abc064/submissions/2703164

解説読んだけど頭に入ってこない…

ABC 061

C - Big Array (300)

  • (a[i],b[i])を昇順ソート(O(NlogN))
  • b[i] の方の累積和を取った配列からK-1番目がどこに入るか (upper_boundで)探す
  • その直前のa[i]

→AC 11'22
https://beta.atcoder.jp/contests/abc061/submissions/2695904

解説解より

a_iの範囲は[1,1e5]だしバケツソートで、b_iを足して累積してK番目、とすればO(N+maxAi)。なるほど。

D - Score Attack (400)

ノード1から始めて、priority_queueに次のノードと距離を放り込んで拡散していって、訪問済みで前より増えてればinf
→WA(4),

  • 最初TLEが出てた→priority_queueじゃなくてqueueに変更→でもWAが4ケース消えず
WA消せずに心が折れたので解説読む

スコアの正負を逆にすれば最短経路問題…なんだってー
負のコストの辺があるのでダイクストラ不可、N=1000なのでWFは厳しい、のでベルマンフォード法で。負閉路を検出したらinf。

分かったので自分で書いてみる。

  • 全M辺を使った更新(緩和) × N-1回ループ、でノードNには到達できる&距離が分かる
  • 負閉路を検出するだけなら、全M辺を使った更新でどこかがより短く出来るかを見ればよい
    • 全M辺を使った更新 × N回ループ、で、検出した負閉路からノードNにたどり着く道があるかを見る。あるならノードNへの距離はいくらでも小さくできる
    • N回ループなのは、最初の1回で負閉路は検出できて、そこから高々N-1回でノードNに(そういう経路が存在するなら)たどり着くから。

→AC
https://beta.atcoder.jp/contests/abc061/submissions/2703101

ABC 057

C - Digits in Multiplication (300)

  • 9,99,999,...で割って商を見ていって最小値を探る、とかやってた(割り切れないといけないから意味なし
  • √Nまでの素数を求めてNを割っていって、とかやってたのも意味なし
  • Aを[1,√N] で全探索、でいいんじゃん(間に合うし)

→AC 21'14
https://beta.atcoder.jp/contests/abc057/submissions/2695964

解説解も同様

D - Maximum Average Sets (400)

  • 降順ソートして、と思ったんだけどあとでlower_bound,upper_bound使いたいので昇順でソートしたやつを後ろから見る
  • A個から始めてB個まで、合計(と平均を出すための分母)を更新していく。ここまでの平均を下回るなら打ち切る。(浮動小数点数ではなく 分子1×分母2 と 分子2×分母1 の比較をしている)打ち切り前の最長をα個とする(A≦α≦B)
  • 打ち切り前の最後の数に着目。この数が「w:全体でいくつ含まれるか」「p:α個の中にいくつ含まれるか」を調べ、\sum_{k=1}^p wCk を求める。

→ WA(2) 半分ぐらいWA
long doubleにしたけど変わらない

時間切れにつき解説みる

解説解もほぼ同様、なんだけど

下限が1じゃないケースがあるからk=1からのsummationじゃ駄目じゃん

10 1 3
1 1 1 1 1 1 1 1 1 1

→1.00000000, 175
これはOK (175=10C1+10C2+10C3)

10 2 3
1 1 1 1 1 1 1 1 1 1

→1.00000000, 175
これは165 (=10C2+10C3) にならないといけない

summationを直して
→AC
https://beta.atcoder.jp/contests/abc057/submissions/2702222

ABC 054

C - One-stroke Path (300)

  • 高々N=8だし、next_permutationで全パターン(8!)やっても大丈夫
  • 答えが合わない→始点1固定だった

→AC 8'16
https://beta.atcoder.jp/contests/abc054/submissions/2696006

解説より

DFSでバックトラックしながら経路を列挙する解法が紹介されている。bitDPでO(2^N N^2)となる解法ってこの場合高速なのか?

D - Mixing Experiment (400)

DPで調達可能なa,bの量をすべて求めて、Ma:Mbになるところを見て最小コスト(あるいは-1)を返す
→AC 9'44
https://beta.atcoder.jp/contests/abc054/submissions/2701928

解説より

解説解も同様

なお、比の等式と半分全列挙を用いた時間計算量 O(2^{\frac{N}{2}}N) となる解法が存在します。(詳細は略)

↑これはどうやるんだろう

ABC 051

C - Back and Forth (300)

  • W=tx-sx, H=ty-syとして
    • 1周目:↑H →W ↓H ←W
    • 2周目:←1 ↑H+1 →W+1 ↓H+1 ←W+1 ↑1

交差できないのでこれ以上は短くできなさそう
→AC 8'11
https://beta.atcoder.jp/contests/abc051/submissions/2696045

解説より

点s,tそれぞれ in-degree = out-degree = 2 なので、上下左右をフルに使わないといけない、ということはs,tの上下左右にそれぞれ1行った点は通らないといけない。なるほど。

D - Candidates of No Shortest Paths (400)

各辺(u,v)について、WFで求めたu,v間の最短距離より長ければその辺は使われない
→AC 4'58
https://beta.atcoder.jp/contests/abc051/submissions/2701852

解説解も同様