naoya_t@hatenablog

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

〈ABC埋め〉C問題集中アタック (089 - 051)

出場していない回のC問題を解く。

C問題は解けないことはないんだけど、解説を読むと「もっと簡単に書ける」みたいな気づきがたまにある。

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]に入れてたけどこれは自分だとバグりそう…

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を調べたほうが楽か。


ABC 084 C - Special Trains (300)

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

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

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は考えもしなかった…

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

解説解も同様


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)。なるほど。

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

解説解も同様

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)となる解法ってこの場合高速なのか?

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行った点は通らないといけない。なるほど。