ABC 154 F Many Many Paths 図解解説
まず，f(r, c) を表形式で図示します．数字が大きすぎて省略されてしまっている部分がありますが，無視してください．
ところで，この値は パスカルの三角形 (のちょっと内側) と一致しています．ゆえに，f(r, c) = f(r-1, c) + f(r, c-1) と表せます．・・・①
さて，今したいのは，この表中の任意の長方形について，その和を求めることです．長方形の和は次のように，左上を直角とする 3 つの直角二等辺三角形の足し引きで表すことが出来ます．
よって，表中の任意の三角形について，その和が求められれば良いことがわかりました．
ここで，ある三角形についてその周りの値を適当に文字で置き，三角形内の各値を求めると①より次のようになります．なお，周りの値は f(r, c) = (r+c)!/(r!c!) であることを用いて求めます．
更に，a だけに着目すると，こうなります．
すると，a の係数がまたもパスカルの三角形になっています．(まあそれはそうです．)
もちろん，他の文字，例えば b に注目しても係数がパスカルの三角形になっています．
ところで，パスカルの三角形の i 段目の和は 2i-1 になります．(二項定理を使って証明できます．) よって，1 ～ i 段目の和は 2i -1 です．
したがって，今着目している三角形の場合，その和は a×(24-1) + b×(23-1) + c×(22-1) + d×(21-1) + x×(24-1) + y×(23-1) + z×(22-1) + s×(21-1) となります．
まとめ
- 長方形領域を 3 つの三角形の足し引きに分ける．
- ある三角形に着目して，その周りを f(r, c) = (r+c)!/(r!c!) により求める．(階乗と 逆元 を前計算しておく．)
- 周りの 1 マスずつについて，パスカルの三角形の段の和をかけつつ ans に加算していく．
- 以上で各三角形内の和が求められ，したがってもとの長方形内の和も求められる．
JOI 2008/2009 予選 6 「ビンゴ」 解法
後輩への解説用に作ったものをブログにも上げておきます．誰かの役に立ちますように．いろいろ独断と偏見が含まれているので，上級者の方は温かい目でご覧ください．
原本：https://drive.google.com/open?id=1pa_I0VqJWKSWOIY6jMg8Cky8BY649gej
STEP1 普通に DP
添え字として，今どのマスを見ているか，1 つ前のマスの値は何であったか，1 つ前のマスまでの合計値はいくつか，というデータを持つ．遷移として，1 つ前のマスの値より大きいものを全探索する．時間計算量は O(N2M2S)．
サンプルコード
int N, M, S; // now := N*Nマス中のどこか // bef := 1つ前のマスの値+1 (今回はbef以上) // sum := 1つ前のマスまでの合計値 int memo[50][2001][3001]; int solve(int now, int bef, int sum){ if(sum > S) return 0; if(now == N*N){ if(sum == S) return 1; else return 0; } if(memo[now][bef][sum] != -1) return memo[now][bef][sum]; int ans = 0; for(int i=bef; i<=M; i++){ ans += solve(now+1, i+1, sum+i); } return memo[now][bef][sum] = ans % MOD; } int main(){ cin >> N >> M >> S; for(int i=0; i<N*N; i++){ for(int j=0; j<=M; j++){ for(int k=0; k<=S; k++){ memo[i][j][k] = -1; } } } cout << solve(0, 1, 0) << endl; return 0; }
STEP2 遷移をまとめる
DP の時間計算量を落とすためにできることは，添え字を減らすか，solve 関数の中のループを無くすかのどちらかである．ここでは solve 関数の中のループを無くせる．具体的に考えてみる．
ある関数呼び出し solve(i, j, k) が次に呼び出すのは solve(i+1, j, k+j), solve(i+1, j+1, k+j+1), solve(i+1, j+2, k+j+2), …, solve(i+1, M, k+M) である．また，ある関数呼び出し solve(i, j+1, k) が次に呼び出すのは，solve(i+1, j+1, k+j+1), solve(i+1, j+2, k+j+2), …, solve(i+1, M, k+M) である．下線部において，呼び出す遷移先が共通しているから，うまくまとめることが出来る．今回の場合，例えば関数呼び出し solve(i, j, k) が次に呼び出す関数を，solve(i+1, j, k+j), solve(i, j+1, k) とすればよい．
時間計算量は O(N2MS)．
サンプルコード
int N, M, S; // now := N*Nマス中のどこか // bef := 1つ前のマスの値+1 (今回はbef以上) // sum := 1つ前のマスまでの合計値 int memo[50][2001][3001]; int solve(int now, int bef, int sum){ if(sum > S) return 0; if(now == N*N){ if(sum == S) return 1; else return 0; } if(bef > M) return 0; if(memo[now][bef][sum] != -1) return memo[now][bef][sum]; int ans = solve(now+1, bef+1, sum+bef) + solve(now, bef+1, sum); return memo[now][bef][sum] = ans % MOD; } int main(){ cin >> N >> M >> S; for(int i=0; i<N*N; i++){ for(int j=0; j<=M; j++){ for(int k=0; k<=S; k++){ memo[i][j][k] = -1; } } } cout << solve(0, 1, 0) << endl; return 0; }
STEP3 配列を使いまわす
この問題の本質的な改善は STEP2 だが，まだ使用メモリ量が多い．メモ化再帰ではなく for ループを用いる形に DP を書き換えることで，配列を使いまわすことが可能な場合がある．書き換えの際には，再帰の末端の方から先に処理を行うことを意識する．今回の場合，now と bef は小さくなるようループを回さなければならない．sum はどちらでもよい．空間計算量は O(MS)．
「配列を使いまわす」とは，配列の特定の添え字の要素数を 2 にして，呼び出し時には %2 とし，同じメモリに別の意味を持たせながら繰り返し使う典型テクニックである．
サンプルコード
int N, M, S; int dp[2][2002][3001]; int main(){ cin >> N >> M >> S; // now := N*Nマス中のどこか // bef := 1つ前のマスの値+1 (今回はbef以上) // sum := 1つ前のマスまでの合計値 for(int now=N*N; now>=0; now--){ for(int bef=M+1; bef>=0; bef--){ for(int sum=0; sum<=S; sum++){ if(now == N*N){ if(sum == S) dp[now%2][bef][sum] = 1; else dp[now%2][bef][sum] = 0; continue; } if(bef > M){ dp[now%2][bef][sum] = 0; continue; } int ans = (sum+bef <= S ? dp[(now+1)%2][bef+1][sum+bef] : 0) + dp[now%2][bef+1][sum]; dp[now%2][bef][sum] = ans % MOD; } } } cout << dp[0][1][0] << endl; return 0; }
大手前プロコン 2019 やってみた
大手前プロコン 2019 とは
大阪城の真ん前にある府立大手前高校では 2 年前から SSH (スーパーサイエンスハイスクール)の行事としてプログラミング学習会を開催してきました。今年度は 8 月 1 日、2 日に初心者・未経験者対象の講習を実施し、3 日には大手前プロコン 2019 オンサイトを実施しました。
今年の大手前プロコンは初心者も楽しめるようたくさん部分点を用意したり、かつ春合宿erにも苦戦してもらえるよう難しい問題を用意したり、writer の皆様とたくさん打ち合わせをして開催したものでした。各問題にもたくさんの思い入れがあるので、ここに書き記していこうと思います。
問題 A 寝坊だ！ピ太郎！ (writer : kotamanegi さん)
ほぼ原案通りの出題でした。せっかく大手前プロコンに来てくれた人に 1 完はして帰ってほしいということでした。
原案では、Yes / No を出力する問題だったんですが、どうせなら文字列を扱えなくても解けるようにしてしまおうと思って、0 / 1 を出力する問題に変更しました。我ながら優しい。
問題 B 駒 (writer : yamunaku さん)
原案は無限に伸びた数直線上で行ってたんですが、左端の駒より左に集めるのは意味がない、みたいな考察が少し大変かと思って、マス上での問題への変更をお願いしました。
小課題 1 の提案はきたむーで、ループも回さず解けるので A しか解けなかった人には是非拾ってほしい部分点でした。
小課題 2, 3 の提案は yamunaku さんで、「集める」を意識させる小課題をご用意くださいました。
満点解法はやや難しかったようです。
問題 C カード並べ 2 (writer : olphe さん)
僕がいじったのはもともと数列だけだったのを、カードの設定を付け加えたぐらいです。問題特有の性質を考える必要があって、ほどほどに難しいですが、実装は楽です。
小課題の中では 2 が一番解きやすいと思うので、是非取ってほしかったです。
上級者は数列の数え方に被りがあってもいい場合も考えてみて下さい。問題文中の例だと、{1 2 1 2 1 2 1 2} に {1 2 1 2} が 3 回出てきていると考えるわけですね。
問題 D FizzBuzz (writer : Hoget さん)
この問題は今回のセットの中で最も好きです。本当に予選 4 で出てきそうな問題。数学的な知識を背景にしつつ、DP という情報科学的なテクニックも使う。大好きです。
小課題を考えるのがかなり大変だったんですが、N=M が出てきた後に、全部同じ文字列にすることを確か僕が提案しました。これら小課題によって、3、5 の倍数の判定法をきちんと意識させ、満点解法に近づいてもらいたかったです。
なお、mod は 3 で十分です！！！！！15 じゃないよ！！！！！低速な言語でも通るように制限を緩くしたので mod 15 にしても C++ とかなら通りますが、mod 3 で解く人をもう少したくさん見たかったです・・・。
問題 E 最悪の教頭 (writer : WA_TLE さん)
元ネタは最悪の記者 3 (JOI 2017/2018 春合宿 Day 2) です。問題文をちょっとだけいじるはずが、いろいろ辻褄の合わない点が出てきて、細々改善を重ねてきていたんですが、コンテスト中にも新たな不備が発覚してしまいました。申し訳ないです。
この問題はひらめき一発、実装はわずか数行、といった感じでした。僕はひらめきませんでした。丁寧に考察してあげると、わかると思います。たぶん。
小課題はやるだけなので、是非取って欲しかったですね。
この問題難易度について、本選1 ～ 2 問目相当と記載していたんですが、もう少し難しかったかもしれないですね。
問題 F 天秤とコイン (writer : drafear さん)
典型テクの合わせ技みたいな問題です。これはかなり論理的に解けると思っていて、DP を知っているのに解けなかった人は、是非僕が書いた公式解説を読んで欲しいです。
小課題はすべて drafear さんの提案なんですが、僕は部分点解法が全くわかりませんでした。満点解法はわかるのに。そういうこともあるので、是非各小課題についても改めて考えてみて欲しいです。
なお、僕は提案から 3 週間ぐらいずっと、左側の更に積まれているコインの途中を抜き取って右に移してもいいと誤読していたので、ずっと頭を抱えていました。
問題 G 空をかけるピ太郎 (writer : gotoloop さん)
ストーリー部分は僕が後から勝手につけました。「空」を「そら」と読むのか「くう」と読むのか、自分でもよくわからないので、英語名で読んでやってください。ストーリーの元ネタは時をかけるビ太郎 (JOI 2018/2019 春合宿 Day 3) です。
この問題の小課題 1 はスーパー簡単、何なら 1 問目より簡単なので、是非取って欲しかったです。(ここまでわざわざ見なかった人に加え、問題文の読解ができなかった人もいたようです)
小課題 2、3 は確か僕が提案して、(遅延)セグ木で殴るつもりだったんですが、imos をしたり、範囲を merge したり、いろいろな解き方が見られたようです。
満点解法は原案をもらって 5 分ぐらいで思いついたので、かなり簡単だと思っていたんですが、実装面で詰まっている人が多かったようです。僕はこの問題の実装は全然重くなと思っているんですが、個人差ですね。多分 JOI で春合宿の対策をした人は、全然重くないと感じると思います。
問題 H 美味しい飴 (writer : Pulmn さん)
小課題 1 : やるだけ(といっても DP)
小課題 2 : 差分を使って DP を頑張る(鍛えればできるようになるらしい)
小課題 3 : 天才解法が降ってくれば簡単
みたいな感じです。かなり難しくなってきたという感じです。難しいのでコメントできません。
問題 I ピーターランドの道路整備 (writer : hos さん)
問題名が長いです。ごめんなさい。
めっちゃ難しいです。小課題 1、2 は簡単なので取りましょう。満点解法は丁寧に考察すればいい感じに式変形出来て、実装を頑張ります。
コンテスト時間の不足は明らかなんですが、JOI 春とは違ってライブラリの使用が OK なので、何とかなるかなと思ってました。あと数分足りなかった方が 2 人いらっしゃった感じです。
問題の難易度について
大手前プロコン公式として見解ではなく、きたむー個人の意見なのでご注意ください。
JOI 非公式難易度だと、1-3-4-6-7-7-9-11-12。
具体的な基準では、
- JOI 1 次予選突破 : 120 点以上
- JOI 2 次予選突破 : 340 点以上
- JOI 本選突破 : 560 点以上
- JOI 春合宿突破(IOIer になる) : 740 点以上
ぐらいだと思います。参考にしてください。
JOI に出る人へ
部分点もっと取ってよ！！！
JOI はどれだけ部分点を取れるかを競っているコンテストです。わずか数点の差で泣くこともあるのです。
JOI 出場予定で部分点を全然取りにいかなかった人は先が暗いです。部分点を取る練習をしてください。特に春合宿で一切部分点を取らないと 0 点になりえます。1 完出来てない人はそこそこいます。
某 IOIer は難問を解くときには誤読防止のためにまず最小部分点を数分で通すと言っていました。そういう使い方もあります。部分点とうまく付き合える人が JOI では明らかに有利なのです。
今回、writer の皆さんには、「JOI の模擬試験を作りたい」みたいなことを言ってきました。大手前プロコンはそういうコンテストです。writer の半分以上が JOI で活躍していた人です。もはや JOI なんです。しっかり解きなおしをして、本番に備えて欲しいと思います。
APIO2018 日本語問題文(オリジナル翻訳)
1 New home
原本
Wu-Fu Street is an incredibly straight street that can be described as a one-dimensional number line,and each building’s location on the street can be represented with just one number. Xiao-Ming the Time Traveler knows that there are n stores of k store-types that had opened, has opened, or will open on the street. The i-th store can be described with four integers: xi, ti, ai, bi, representing the store’s location,the store’s type, the year when it starts its business, and the year when it is closed. Xiao-Ming the Time Traveler wants to choose a certain year and a certain location on Wu-Fu Street to live in. He has narrowed down his preference list to q location-year pairs. The i-th pair can be described with two integers: li, yi, representing the location and the year of the pair. Now he wants to evaluate the lifequality of these pairs. He defines the inconvenience index of a location-year pair to be the inaccessibility of the most inaccessible store-type of that pair. The inaccessibility of a location-year pair to store-type tis defined as the distance from the location to the nearest type-t store that is open in the year. We say the i-th store is open in the year y if ai ≤ y ≤ bi. Note that in some years, Wu-Fu Street may not have all the k store-types on it. In that case, the inconvenience index is defined as −1. Your task is to help Xiao-Ming find out the inconvenience index of each location-year pair.
問題文
通りに見立てた数直線上にn個の店がある。各店の位置(x座標)はx_i、タイプはt_iであり、a_i年からb_i年までオープンしている。店のタイプはk種類である。
タイムトラベラーは自分が住む場所と時間の候補のペアをq個用意した。各ペアの場所はl_i、年はy_iである。
各候補の生活の質は次のように定義される。
1. その年に営業していない店のタイプが存在するとき、-1
2. すべてのタイプの店が営業しているとき、その場所から一番近い各タイプの店との距離の最大値
各候補について、生活の質を答えよ。
制約
- 1 <= n,q <= 3*105
- 1 <= t_i <= k <= n
- 1 <= x_i, a_i, b_i, l_i, t_i <= 108
2 Circle selection
3 Duathlon
原本
The Byteburg’s street network consists of n intersections linked by m two-way street segments. Recently, the Byteburg was chosen to host the upcoming duathlon championship. This competition consists of two legs: a running leg, followed by a cycling leg. The route for the competition should be constructed in the following way. First, three distinct intersections s, c, and f should be chosen for start, change and finish stations. Then the route for the competition should be built. The route should start in s, go through c and end in f. For safety reasons, the route should visit each intersection at most once. Before planning the route, the mayor wants to calculate the number of ways to choose intersections s, c, and f in such a way that it is possible to build the route for them. Help him to calculate this number.
問題文
n個の交差点のm個の道路からなる街がある。各道路は交差点v_iとu_iを結ぶ。Duathlonはトライアスロンの簡易版みたいなもので、マラソンの後にサイクリングをする競技である。
市長は競技のルートを考えている。各ルートはスタート地点s、競技変更地点c、終了地点fからなる。安全のため各交差点は1度しか通ることができない。
市長はルートを考えるにあたって、ルートを構築することが可能な(s,c,f)の組の個数を求めることにした。
制約
- 1 <= n <= 105
- 1 <= m <= 2*105
APIO2016 Gap 解法
1か月後のAPIOに向けてOJ-OIで精進中。APIO2016は珍しく日本語の問題文があるものの、英語でも解説が見当たらなかったので、解法を書き残しておきます。
3 Gap
インタラクティブ問題でした。小課題1と2でMの値の数え方が違うので、それぞれ別々の実装をします。
小課題1
両端からだんだん狭めていけばよく、ceil(N/2)回で求められます。これは瞬殺です。
小課題2
こっちは少し苦戦しました。とりあえず両端を求めて、m、Mとでもおきます。このとき、答えは絶対に(M-m)/N以上になります。うまく均等にしても(M-m)/Nなので、位置にばらつきが出ればこれ以上になります。
よって、区間(m,M)をN個に分割したとき、差が最大になる組は必ずこの分割をまたぎます。図を書きましょう。
よって、両端を求めるのにN+1回、残りのN個の区間を見ていくのに、あとN-2要素含まれているから、N-2+N回
全部でだいたい3N回で、この問題が解けました。
