NPCA のアドバイザーをしておりました。
問題の修正等多くて申し訳ありませんでした。
次回からは改善していきたいと思います。(関わるかどうかは知りませんが・・・)
Div1の解説と統計を書きたいと思います。
黒い板
１問目から難しいです。
貪欲っぽい臭いがしますが、第一感は愚直に近い方から塗れるだけ塗るシミュレーションでしょうか？
やってみると分かりますが、これだとサンプルすら通りません。
発想を逆転させます。
つまり、最も遠いところから塗れるだけ塗っていくのが正しい貪欲です。
しかし、これを愚直に実装すると以下のようなtestcase7でTLEするので、黒板の数がxである教室を遠い方から取り出せるようなstackを使って実装します。
100000 3 1 ... 1 2 ... 2
あ、答えはintに収まるとは限らないので注意が必要です。(本意の罠ではないので問題文中に書いといた方が良かったかも)
と思っていたのですが、
5 3 2 2 2 1 1
とかで間違った答えを出してしまいますね・・・m(_ _)m
正しいアルゴリズムはどうなるんだろうか。
宿題
想定はDPです。
問題はDPのやり方で、
dp[i][j] = i個目の休み時間までに基本問題をj個解いた時に解ける応用問題の最大数
とするとTLEするようになっています。なので、
dp[i][j] = 基本問題をi個、応用問題をj個解くときの最短時間
を計算します。
計算しながら解ける問題の最大値を更新していきます。
ただこれも愚直に実装するとTLEするので、次の十分な時間のある休み時間をO(1)かO(log N)くらいで計算できるようにしておくと良いです。
どうも入力に不備があったらしく、rejudgeで２人がACになりました。
プール掃除
最大値とか最小値とか出てきていかにも二分探索ですね。
最小値で二分探索して、M個以下にグループ分けできるかどうかを判断すると良いです。
世界史ネットワーキングサービス
謎のWAが出てしまって申し訳なかったです。原因なんだったんだろう？
segtreeとか使うと良さそうな感じの問題ですが、実はいりません。(というか使う方が難しい？)
ある年までに生まれた人数と死んだ人数の２つの累積和配列born,dieを作っておくと、
各偉人についての出力は、born[偉人の死んだ年]-die[偉人の生まれた年-1]-1、となります。
約数スマッシュ
f(x) = 1~xの約数の個数の総和
という関数を作ると、答えはf(m)-f(n-1)となります。
問題は関数の作り方ですが、
long long f(long long x){ if(x <= 1) return x; long long sum = 0, i; for(i = 1; i*i <= x; i++) sum += x/i; i--; return sum*2-i*i; }
こんな感じです。
この関数は
xy = Xの曲線より下にある、第一象限にある格子点の数になるということを導いて、あとは対称性でO(sqrt(X))にしました。
というようにして導けるらしいです。
リニア植物
場合分けがあって、１発ACは厳しそう。
まずは高さを昇順、同じなら成長率を降順でソートしておきます。(順番はやり方によって変わりそう)
それを順番に調べながら、最も高くなりうるものをstackに入れていく感じです。
高さも成長率も同じ植物とかに気をつけましょう。
あみだくじ
JOI的良問？
僕の解とcatupper氏の想定解がちょっと違うので両方紹介します。
僕の解から
入力される数列が 3,2,4,1 だとして説明する。
1234のように昇順に並び替えるための反転数は、各数字の左にある自分より大きな数の個数の和です
だからこの問題は、3241,3245,3645,7645 を昇順に並び替えるための反転数の最小値を求める問題となります。
各数字の左にある自分より大きな数の個数を書いてみると、
3241 3245 3645 7645
(0103)(0100)(0011)(0122)
となります。
これを3241から順に7645までO(log N)で更新して行くのですが、更新の仕方は
・1->5 となるとき5は全数中最大なのでそこは0
・それより右の数全てのところに1を足す
となり、これはBITで実現できます。
想定解は、数式になるので実装が楽です。
ある列を1~Nにするというのを考えるのではなくて、1~Nをある列にするという状態に組み直して、1~Nをずらすのではなく「ある列」の方をずらす。
すると、最も左にある数をxとして、それを最も右にずらした時に反転数はn-2x+1増える。
3241でシミュレーションすると、
3241 -> 1234は、1234 -> 4213と同じで、反転数は４。
4213をひとつずらして2134にしたとき、1234->2134の反転数は4+(n-2x+1)= 4 + (4 - 8 + 1) = 1
まわし読み
どうも定数倍の差でTLEがおきるらしい・・・
想定解法は、
「時間通りに渡せる関係のグラフを作っておき、そのグラフの最小パス被覆を求める。」
で、速い２部マッチングを書くと通るらしい。
最小費用流にも出来るけど、定数項がヤバくて通らないっぽい。
この辺りはtesterの詰めが甘かったですね・・・すみません。。
統計
First Acceptance
Div2
1 : odan
2 : sh19910711
3 : sh19910711
4 : hogeover30
5 : IH19980412(HIR180)
6 : IH19980412(HIR180)
7 : yutaka1999
8 : yutaka1999
Div1
1 : komiya
2 : climpet
3 : kawatea
4 : kohyatoh
5 : yukim
6 : kawatea
7 : Kinokkory
8 : ima1000
submissionベースのAccept/Submit
Div2
1 : 44/84
2 : 39/73
3 : 24/67
4 : 35/42
5 : 31/62
6 : 17/62
7 : 30/43
8 : 21/67
Div1
1 : 17/64
2 : 4/27
3 : 20/36
4 : 30/49
5 : 27/42
6 : 3/8
7 : 8/17
8 : 0/25
人数ベースのAccept/Submit
Div2
1 : 43/45
2 : 39/41
3 : 24/33
4 : 35/36
5 : 31/34
6 : 17/23
7 : 30/33
8 : 21/28
Div1
1 : 17/25
2 : 2/6
3 : 20/21
4 : 27/31
5 : 27/29
6 : 3/4
7 : 8/12
8 : 0/4
