![C-問題概要
● [1,2,..,N]を並び替えたものを「単語」という
● 単語のうち辞書順で小さい方から N! / K番目
(1-index)のものを求めよ
● K ≦ N ≦ 10^5](https://image.slidesharecdn.com/arc047-160116141137/85/arc047-26-320.jpg)
![C-X番目の求め方
● 1文字目が1であるような単語はいくつある
か？
– 2文字目以降の並びを考えると(N-1)!通り
● 1文字目が2であるような単語はいくつある
か？
– 同様に(N-1)!通り
● X番目の単語の1文字目は何か？
– 上の考察より、[X / (N-1)!] + 1
– []はガウス記号](https://image.slidesharecdn.com/arc047-160116141137/85/arc047-29-320.jpg)
![C-X番目の求め方
● 1文字目が求まった！→Aとする
● つぎにもとめるべきものは？
[1,2,..., A-1, A+1,...N]を並び替えたものの中で
X % (N-1)!番目の物
● さきほどと同様の計算で求めることが出来る。
● 順番に繰り返せばすべての桁の値が決まる。
● 以降は[X / (N-1)!] + 1ではなくて[X / (N-1)!] +
1番目に小さい値であることに注意](https://image.slidesharecdn.com/arc047-160116141137/85/arc047-30-320.jpg)
![D-考察
● sum[i] := 「X+Y=iとなるマス(X,Y)にクエリ1で
足された値の総和」
● dif[i] := 「X-Y=iとなるマス(X,Y)にクエリ2で足
された値の総和」
という2つの変数を用意する。
● sum[X+Y]とdif[X-Y]がわかればマス(X,Y)の値も
すぐわかる。](https://image.slidesharecdn.com/arc047-160116141137/85/arc047-44-320.jpg)
![D-考察
● sum[X+Y]とdif[X-Y]がわかればマス(X,Y)の値も
すぐわかる
● クエリ1とクエリ2はO(N)で処理できる
● 问题はクエリ3](https://image.slidesharecdn.com/arc047-160116141137/85/arc047-45-320.jpg)
![D-考察
● X-Yを決めた時に、その中で最大の値を持つマ
スは、適切な範囲のsumの最大値 + dif[X-Y]と
なる。
● X-Y=-1ならば
max{sum[1],sum[3], sum[5]}
+dif[-1]
が右線上の最大値である](https://image.slidesharecdn.com/arc047-160116141137/85/arc047-48-320.jpg)
![D-部分点2まとめ
● sum[i]やdif[i]を使ってマスの値を保存する
● クエリ1,2は愚直にO(N)でsumやdifを更新
● クエリ3の時はdif[X-Y]を全通り試して、各X-Y
に対して対応するX+Yに値の範囲をもとめ、セ
グメントツリーで最大値とその個数をもとめ
る。
● O(NlogNQ) 30点獲得](https://image.slidesharecdn.com/arc047-160116141137/85/arc047-50-320.jpg)
![D-考察
● X-Y = -3のとき齿+驰の范囲は摆3闭
● X-Y = -1のときX+Yの範囲は[1,3,5]](https://image.slidesharecdn.com/arc047-160116141137/85/arc047-53-320.jpg)
![D-考察
● X-Y = -3のとき齿+驰の范囲は摆3闭
● X-Y = -1のときX+Yの範囲は[1,3,5]
● X-Y = 1のときX+Yの範囲は[1,3,5]](https://image.slidesharecdn.com/arc047-160116141137/85/arc047-54-320.jpg)
![D-考察
● X-Y = -3のとき齿+驰の范囲は摆3闭
● X-Y = -1のときX+Yの範囲は[1,3,5]
● X-Y = 1のときX+Yの範囲は[1,3,5]
● X-Y = 3のときX+Yの範囲は[3]](https://image.slidesharecdn.com/arc047-160116141137/85/arc047-55-320.jpg)
![D-観察
● 出てきた範囲の種類は
– [3]
– [1,3,5]
● これを8×8で実験した場合だと
– [7]
– [5,7,9]
– [3,5,7,9,11]
– [1,3,5,7,9,11,13]
となる](https://image.slidesharecdn.com/arc047-160116141137/85/arc047-56-320.jpg)
arc047
- 5. A-解法 ● タブの個数を変数で管理しておく。 ● タブを閉じるとき – 変数の値を1减らす
- 6. A-解法 ● タブの個数を変数で管理しておく。 ● タブを閉じるとき – 変数の値を1减らす ● タブを開くとき – タブの個数がL個未満ならば、変数の値を1増やす
- 7. A-解法 ● タブの個数を変数で管理しておく。 ● タブを閉じるとき – 変数の値を1减らす ● タブを開くとき – タブの個数がL個未満ならば、変数の値を1増やす – タブの個数がL個ならば変数の値を1にして、ク ラッシュの回数を1増やす
- 9. B-問題概要 ● 格子点上の点が N 個与えられる。 ● 全ての点からのマンハッタン距離が等しい格子 点上の点Pを1つもとめよ ● N ≦ 10^5 ● -10^9 ≦ 座標の値 ≦ 10^9
- 22. B-考察 ● 1辺の長さについては、X座標の最大値と最小 値の差とY座標の最大値と最小値の差をみて、 大きい方をとればよい。 ● １辺の長さをDとする。与えられたX座標、最 大最小をXmax,Xminで表し、点PのX座標、Y座 標をPx,Pyとすると Xmax-Px, Px -XminのいずれかがD/2と一致す る。 – Y座標も同様 ● よってDの値と全体のX座標、Y座標の最大最小 から点Pの候補が有限個に決まる
- 23. B-考察 ● さきほどの考察は45度回転した後の世界での 計算である。 ● 回転後のXやYの値は、回転前のX+YやX-Yの値 と対応するので、実装するときはその値でプロ グラムを組まなければならない。
- 24. B-解法 ● 与えられた点について(X+Y)の最大値と最小値 の差、（X-Y）座標の最大値と最小値の差を求 め、大きい方をDとする ● 先ほどの考察を使ってPx,Pyの値を有限個にし ぼりこむ ● そのうちすべての点とのマンハッタン距離が等 しい点を挙げれば良い
- 26. C-問題概要 ● [1,2,..,N]を並び替えたものを「単語」という ● 単語のうち辞書順で小さい方から N! / K番目 (1-index)のものを求めよ ● K ≦ N ≦ 10^5
- 29. C-X番目の求め方 ● 1文字目が1であるような単語はいくつある か？ – 2文字目以降の並びを考えると(N-1)!通り ● 1文字目が2であるような単語はいくつある か？ – 同様に(N-1)!通り ● X番目の単語の1文字目は何か？ – 上の考察より、[X / (N-1)!] + 1 – []はガウス記号
- 30. C-X番目の求め方 ● 1文字目が求まった！→Aとする ● つぎにもとめるべきものは？ [1,2,..., A-1, A+1,...N]を並び替えたものの中で X % (N-1)!番目の物 ● さきほどと同様の計算で求めることが出来る。 ● 順番に繰り返せばすべての桁の値が決まる。 ● 以降は[X / (N-1)!] + 1ではなくて[X / (N-1)!] + 1番目に小さい値であることに注意
- 31. C-部分点 ● いまのような計算方法でN!/K番目の値をもとめ る。 ● N ≦ 20なのでN!/Kは64bit整数に収まるので、 様々な言語で扱える。
- 33. C-考察2 ● Nが大きいと N!/Kを陽に持つことは出来な い。 ● やりたい操作は – (N-1)!で割る – その余りを求める
- 34. C-考察2 ● Nが大きいと N!/Kを陽に持つことは出来な い。 ● やりたい操作は – (N-1)!で割る – その余りを求める 実際にやってみる
- 35. C-考察2 ● N!/Kを(N-1)!で割った商は – (N/K)×(N-1)! ÷ (N-1)! の商 – → N÷K の商 ● N!/Kを(N-1)!で割ったあまりは – (N/K)×(N-1)! ÷ (N-1)! のあまり – → 「N÷Kのあまり」÷ K × (N-1)! – これは 整数÷K×(N-1)! の形をしている
- 36. C-考察2 ● このあと2桁目を求めるときに – 整数÷K×(N-1)! を (N-2)!で割った商と余り を求めることになる。商は先ほど同様に簡単に 求めることができ、あまりは – 整数÷K×(N-2)! になる。
- 37. C-考察2まとめ ● 1桁目を求めるときに扱う値が 1÷K×N! ● 2桁目を求めるときに扱う値が 整数÷K×(N-1)! ● 3桁目を求めるときに扱う値が 整数÷K×(N-2)! ● 4桁目を求めるときに扱う値が 整数÷K×(N-3)! :
- 38. C-考察2まとめ ● 1桁目を求めるときに扱う値が 1÷K×N! ● 2桁目を求めるときに扱う値が 整数÷K×(N-1)! ● 3桁目を求めるときに扱う値が 整数÷K×(N-2)! ● 4桁目を求めるときに扱う値が 整数÷K×(N-3)! :
- 39. C-考察2まとめ ● 1桁目を求めるときに扱う値が 1÷K×N! ● 2桁目を求めるときに扱う値が 整数÷K×(N-1)! ● 3桁目を求めるときに扱う値が 整数÷K×(N-2)! ● 4桁目を求めるときに扱う値が 整数÷K×(N-3)! : 赤字の整数だけ保存しておくだけで済む
- 40. C-解法 ● 部分点1と同じ解法を、N!/Kを陽に持たずに計 算する。 ● 保存しておく整数はあまり大きくならないこと が保証される。 – 考察すると 整数÷K ≦ N となることがわかる ● 残っている数字の中でX番目に小さいものをも とめる作業はBIT上の二分探索で実装できる →計算量O(Nlog^2N) 満点獲得
- 42. D-問題概要 ● 全てのマスが0に初期化されたN×Nの方眼紙上 で以下のクエリをQ個処理せよ。 ● 1:A≦ X+Y ≦ Bとなるマス(X,Y)にCを足す ● 2:A≦ X-Y ≦ Bとなるマス(X,Y)にCを足す ● 3:A≦X≦ B,C≦Y≦Dとなるマス(X,Y)の範囲内の 最大値とその個数を求める ● N,Q≦5,000
- 43. D-部分点解法 ● N ≦ 50 ● 指示通りシミュレートする ● 一度のクエリで参照する必要のマスは最大で 2500個程度 ● 充分少ないので間に合う ● O(N^2Q）10点獲得
- 44. D-考察 ● sum[i] := 「X+Y=iとなるマス(X,Y)にクエリ1で 足された値の総和」 ● dif[i] := 「X-Y=iとなるマス(X,Y)にクエリ2で足 された値の総和」 という2つの変数を用意する。 ● sum[X+Y]とdif[X-Y]がわかればマス(X,Y)の値も すぐわかる。
- 47. D-考察 ● X-Yの値を決めてやると、X+Yの値の範囲も決 まり、1個飛ばしの値をとる。 ● X-Y = -1とする X+Yは1～５の奇数をとる
- 48. D-考察 ● X-Yを決めた時に、その中で最大の値を持つマ スは、適切な範囲のsumの最大値 + dif[X-Y]と なる。 ● X-Y=-1ならば max{sum[1],sum[3], sum[5]} +dif[-1] が右線上の最大値である
- 50. D-部分点2まとめ ● sum[i]やdif[i]を使ってマスの値を保存する ● クエリ1,2は愚直にO(N)でsumやdifを更新 ● クエリ3の時はdif[X-Y]を全通り試して、各X-Y に対して対応するX+Yに値の範囲をもとめ、セ グメントツリーで最大値とその個数をもとめ る。 ● O(NlogNQ) 30点獲得
- 51. D-考察 ● クエリの範囲が正方形である時を考える ● 偶奇は別々に考えていいので今回は奇数だけ考 える ● 部分点2で注目した齿+驰の范囲をよく见てみる
- 52. D-考察 ● X-Y = -3のとき齿+驰の范囲は摆3闭
- 53. D-考察 ● X-Y = -3のとき齿+驰の范囲は摆3闭 ● X-Y = -1のときX+Yの範囲は[1,3,5]
- 54. D-考察 ● X-Y = -3のとき齿+驰の范囲は摆3闭 ● X-Y = -1のときX+Yの範囲は[1,3,5] ● X-Y = 1のときX+Yの範囲は[1,3,5]
- 55. D-考察 ● X-Y = -3のとき齿+驰の范囲は摆3闭 ● X-Y = -1のときX+Yの範囲は[1,3,5] ● X-Y = 1のときX+Yの範囲は[1,3,5] ● X-Y = 3のときX+Yの範囲は[3]
- 56. D-観察 ● 出てきた範囲の種類は – [3] – [1,3,5] ● これを8×8で実験した場合だと – [7] – [5,7,9] – [3,5,7,9,11] – [1,3,5,7,9,11,13] となる
- 57. D-考察 ● 良い順番で処理するとX+Yの範囲は増えるだけ になる。 – 値が増えるだけならセグメントツリーをつかわなく ても随時maxをとるだけで最大値がわかる ● 正方形のクエリならば一辺の長さに対する線形 時間で処理することが出来る。
- 59. D-考察 ● クエリの範囲が長方形の時は？ – 正方形に分割してやれば良い。 ● どうやって分割する？ – ユークリッドの互助法の要領でできるだけ大きい正 方形を削り取るように分割していく
- 60. D-考察 ● 例
- 61. D-考察 ● 例
- 62. D-考察 ● 例
- 63. D-考察 ● 例
- 64. D-考察 ● 例
- 65. D-計算量 ● １辺がXの正方形のクエリを処理するのにO(X) の時間がかかる ● タテとヨコの和がSの長方形から先ほどの方法 で1辺がXの正方形を剥ぎとった時、のこる長 方形のタテとヨコの和はS-X以下になる ● よって、全て正方形に分割し終えたときの総計 算量はO(S)＝O(N)となり無事に線形時間で処 理が終わる。
- 66. D-満点まとめ ● 部分点2同様にsumとdifを作る。 ● 正方形のクエリならば線形時間で解ける。 ● 長方形のクエリでも正方形に分割すると線形時 間でとける。 ● O(NQ) 満点