naoya_t@hatenablog

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

AtCoder Beginner Contest 106

8/18(土) 21:00-22:40

今日もD→C→B→Aの順に解きました

D - AtCoder Express 2

N=500というのが肝心
二次元配列T[N+1][N+1]を用意して、
T[a][b]区間 [a, b] を表すとしよう。
そうすると区間 [a, b]を含む区間はこのテーブルにおいて [a,b] を左下角、[0,N] を右上角とする長方形領域で表すことができる。
++T[a][b] しておいて二次元いもすしたらよさそう(行は逆方向なので注意)
M個の区間を登録するのにO(M) + 二次元いもすでO(N^2)
で、このテーブルが用意できれば各クエリにはO(1)で答えられるので合計でO(N^2+M+Q)。余裕っしょ。
→AC 20'42''
https://beta.atcoder.jp/contests/abc106/submissions/3032549

★別解(Fenwick Treeを使ってみる)

  • 列車の運行区間を右端(R[i])でソートしておく(O(MlogM))
  • クエリを右端(Q[i])でグループ化して、右端の小さい順に見ていく。(O(QlogQ))
  • Nが収まるFenwick Treeを1つ用意。(N+1とかだと死ぬので512で)
    • 今見ているクエリ右端Qと同じか左にR[i]が来る全列車の運行区間の左端(L[i])をFenwick Treeに追加(+1)
      • この時点でFenwick Treeに入ってるのは R <= Q な列車のみ。なので、P が与えられたとき [P, Q] の間の個数を数えれば良い。
      • ここの計算量は列車数がMで追加がO(logN)なのでO(MlogN)
    • 右端が同じ(=Q)グループに属する全クエリ [Pi, Q] について、Fenwick Tree の区間 [ Pi, Q ] の合計を求め、それぞれのクエリの答えとする
      • クエリ数がQで、区間合計計算がO(logN)なのでO(QlogN)
  • 元のクエリ番号順に表示
  • 計算量は合わせて O(M(logM+logN)+Q(logQ+logN)) かな
    • これならNが結構大きな値でも大丈夫。(NのバリエーションはO(M+Q)なので座圧すれば行けるはず)

→AC
https://beta.atcoder.jp/contests/abc106/submissions/3040981

追記】こんなのあった(thanks to satanicさんのツイート)
hama-du-competitive.hatenablog.com
↑ここの解法1 と同じかな。
図解があってわかりやすく、他の解き方も載っていて非常に参考になる。

C - To Infinity

5000兆=5e15
それぞれの数字が s_i^{5\cdot10^{15}} 個ずつ並ぶ。

  • s_i=1なら1個である。
  • s_i\ge 2なら、\log_{10} 2^{5\cdot10^{15}}≒0.30103 \cdot 5\cdot10^{15} = 1.50515 \cdot 10^{15}なので 10^{1.50515\cdot 10^{15}}個以上並ぶ。

sを左から見ていって、1のところはk--して、そこでk=0になったら1が答え。
1以外が来たらその数字が答え。(kは高々10^{18}なので、2以上の数字で必ず止まる)
→AC 27'39''
https://beta.atcoder.jp/contests/abc106/submissions/3033512

B - 105

愚直解(O(N^2)
→AC 29'59''
https://beta.atcoder.jp/contests/abc106/submissions/3033821

A - Garden

道を隅に寄せて(A-1)(B-1)
python
→AC 31'36''
https://beta.atcoder.jp/contests/abc106/submissions/3034019