足跡-sokuseki-

りかの日進月歩の記録

Codeforces Round 498(Div.3) C. Three Parts of the Array

競技プログラミング Codeforces

Problem - C - Codeforces

問題概要

長さ N の数列dが与えられる。
この数列dをA,B,Cの3つの連続する区間に分割する。（長さ0の区間が存在しても良い）

Aの長さをa、Aの要素の総和をsum1とする。
同様に、Bの長さをb、Bの要素の総和をsum2、Cの長さをc、Cの要素の総和をsum3とする。
なお、長さ0の区間の要素の総和は0とする。

sum1=sum3であるときのsum1の最大値を求めよ。

制約

1 \le N \le 2 \times 10^5
1 \le d_i \le 10^9

解法

数列dの前からと後ろから累積和を取っておく。
sum3を大きい方から決め打ちして、sum3と等しくなるようなsum1があるか二分探索で求める。あればそれを出力して終了する。
計算量はO(N log N)


Submission #40442600 - Codeforces

Codeforces Round 498(Div.3) B. Polycarp's Practice

Codeforces 競技プログラミング

Problem - B - Codeforces

問題概要

長さ N の数列Aを k 個の連続した区間に分割する。
分割後の各区間の最大値の合計を最大化せよ。

解法

数列Aの要素の大きい方から K 個が、それぞれの区間の最大値となった時が答えである。
よって、そうなるように分割すれば良い。


Submission #40421573 - Codeforces

Codeforces Round 498(Div.3) A Adjacent Replacements

Codeforces 競技プログラミング

Problem - A - Codeforces

問題概要

長さ N の数列Aが与えられる。
次の操作を順番に行う。

  • 数列Aに出現する 1を全て 2に置き換える
  • 数列Aに出現する 2を全て 1に置き換える
  • 数列Aに出現する 3を全て 4に置き換える
  • 数列Aに出現する 4を全て 3に置き換える
  • 数列Aに出現する 5を全て 6に置き換える
  • 数列Aに出現する 6を全て 5に置き換える
  • …
  • 数列Aに出現する 10^9-1を全て 10^9に置き換える
  • 数列Aに出現する 10^9を全て 10^9-1に置き換える

すべての操作が終わった後の数列Aを答えよ。

解法

a_i が奇数だった場合, a_i + 1 になった直後の操作で a_iに戻る。
a_i が偶数の場合は a_i -1 になった後は何も変化しない。
よって, a_i が偶数の場合のみ1を引く。

Submission #40417806 - Codeforces

AGC019 C Fountain Walk

競技プログラミング AtCoder

C - Fountain Walk

問題概要

東西方向と南北方向にそれぞれ 10^8本の道路があり、となりあう道路間の距離は 100 メートルである。すべての東西方向の道路はすべての南北方向の道路と直交し、すべての交差点は、交差する南北方向の通りの番号を x 、東西方向の通りの番号を y として組 ( x , y ) で表される。

N 個の噴水があり、 i 番目の噴水は交差点( X_i, Y_i)に設置されている。
噴水がある交差点には、交差点を中心とした半径 10 メートルの円が噴水の外周として描かれており、その内部に道路はない。

交差点( x_1 , y_1 )から交差点( x_2 , y_2 )に移動するのに歩く最短距離を求めよ。

制約

1 \le N \le 200,000
0 \le x_1, y_1, x_2, y_2 \le 10^8
0 \le X_i, Y_i \le 10^8
i \neq j のとき X_i \neq X_j
i \neq j のとき Y_i \neq Y_j
交差点( x_1 , y_1 ) , ( x_2 , y_2 ) は異なり、どちらも噴水は設置されていない

解法

交差点で曲がるときは、噴水のある交差点で曲がる方が歩く距離は短くすむ。
交差点で曲がらない場合は噴水がない方が距離は短くすむ。

よって、( x_1 , y_1 ) から ( x_2 , y_2 )に向かうときに、できるだけ噴水のある交差点を通りながら曲がりたい気持ちになる。
このとき、経由する噴水の数を最大化すると最短距離となるので、噴水の最大の数を求めたい。

簡単のため、( x_1 , y_1 ) が左下、 ( x_2 , y_2 )が右上にあるとすると、右方向と上方向の移動だけ考えればよい。
よって最短距離に関係のある噴水は、( x_1 , y_1 ) を左下、 ( x_2 , y_2 )を右上とする長方形領域に含まれる噴水のみである。

長方形の左下から右上に移動する際に経由できる噴水に最大数は、噴水の座標の集合をx座標でソートして、y座標でLISを求めてあげるとよい。（制約よりx座標やy座標が等しくなる噴水は存在しないので、特別な処理はいらない）
よって、噴水がない場合の( x_1 , y_1 ) から ( x_2 , y_2 ) への最短距離から、LIS の数だけ噴水を経由する距離を引いてあげ得ると答えがでる。（ x_1 = x_2 または y_1 = y_2 で、長方形領域（実際は直線）に噴水が含まれる場合に注意する）

LISを求めるのは O(N log N) でできるので、全体の計算量は O(N log N) となる。



Submission #2866777 - AtCoder Grand Contest 019

AGC026 B rng_10s

競技プログラミング AtCoder

問題概要

はじめジュースの在庫が A 本ある。
毎日 B 本購入され、購入後 C 本以下になると夜に D 本補充する。
永遠にジュースを B 本購入され続けるか。
クエリは T 個。

制約

T \le 300
1 \le A, B, C, D \le 10^{18}

解法

まず、 A < B の場合は、初日に B 本購入できないので、必ず No になる。
また、そうでなくても、 D < B の場合は、補充数が購入数に追いつかないのでいつか B 本購入できなくなるので、 No になる。
逆に、上の2つを満たさない場合で C \geq B-1 の場合、常に補充が間に合うので永遠に B 本購入でき、 Yes となる。

この3つの場合を除くと、残りは A \geq B かつ D \geq B かつ C < B-1 の場合である。

このときジュースを B 本買えなくなるのは、前日購入後にジュースが C 本より多くて補充されずに、かつ当日 B 本未満だったときのみである。（ D < B より補充されていないことがわかる）
つまり、ジュースの残数が C+1 以上 B-1 以下になってしまうと No となる。

y 日後までに x 回補充されたときにジュースの残数が C+1 以上 B-1 以下になったとすると
C+1 \le A + Dx - By \le B-1
が成り立つ。 mod B をとると
C+1 \le A + Dx \le B-1
となる。
式変形すると、 mod B において、 Dx が [ C+1-A , B-1-A ]の範囲に含まれると No である。
mod B において Dx のとる値は gcd( B , D ) の倍数なので、mod B において、gcd( B , D )が [ C+1-A , B-1-A ]の範囲に含まれると No であると言える。


mod B において、
l := C+1-A
r := B-1-A
とおくと、

l \le r のとき、

  • l を gcd( B , D ) で割った商と r を gcd( B , D ) で割った商が異なる
  • l が gcd( B , D ) で割り切れる

のどちらかを満たす場合のみ、 gcd( B , D )が [ l , r ]の範囲に含まれる。

l > r のとき、[ l , r ]の範囲は [ (C+1)-A + Bk , (B-1)-A + B(k+1) ]の区間の集合となっていて、これは B(k+1) を含むので、かならずgcd( B , D )が [ l , r ]の範囲に含まれる。


各クエリごとの計算量は O(1) なので、全体の計算量は O(T) 。

Submission #2864673 - AtCoder Grand Contest 026


ABC038 D プレゼント

競技プログラミング AtCoder

問題概要

N 個の箱が与えられる。 i 番目の箱は縦 h_i cm × 横 w_i cmで、縦と横を入れ替えることはできない。
ある箱は縦・横ともにより大きいサイズの箱にのみ入れることができ、ある箱は1つまでしか他の箱を入れることはできない。
このとき、箱を最大で何重の入れ子にできるかを求めよ。

制約

1 \le N \le 10^5
1 \le h_i \le 10^5
1 \le w_i \le 10^5

部分点は N \le 1000

部分点解法

dp[i][j] :=  縦icm × 横jcm の箱に入る箱の数

としてdpをする。
h_i と w_i は大きいのでそのままではdp配列の添字にはできない。よって、 N \le 1000 を利用して座圧を行う。

Submission #2825855 - AtCoder Beginner Contest 038

満点解法

「ある箱は、縦・横ともにより大きいサイズの箱にのみ入れることができる」という性質から、入れ子にする箱を小さい順にならべると、 h_i と w_i がともに単調増加になっていることがわかる。つまり、縦の長さで昇順になるように並び替えた後、横の長さでも昇順になるように順番に箱を選んでいけばいいことがわかる。

ただし、縦の長さが等しい2つの箱があった場合、どちらか片方の箱しか選択できないことに注意しなければいけない。

普通の昇順ソートを行うと、キーを2つもつ場合は、 h_i = h_j かつ w_i < w_j のとき i が先に来るように並び替えられてしまうが、これだと縦の長さでソートしたあとに横の長さだけに着目して箱を選ぶと、縦の長さが等しい箱を2つ以上選んでしまう危険性がある。
よって、 h_i = h_j かつ w_i < w_j のとき j が先に来るように並び替えるようにする。
このように縦の長さでソートした後は、横の長さのみに着目しても「ある箱は、縦・横ともにより大きいサイズの箱にのみ入れることができる」を達成することができる。

あとは横の長さを数列の要素とした最大増加部分列（LIS）を求めてあげると、それが答えとなる。


Submission #2856054 - AtCoder Beginner Contest 038

感想

この問題を機にLISを真面目に勉強してスライドをつくったので下手ですが見てください
LIS.pdf - Google ドライブ

ACM-ICPC 2018 国内予選 参加記

参加記 競技プログラミング

「priMe.caT*1」というチームで人生3回目の国内予選に参加しました。

2018年国内予選 | ACM-ICPC 2018 Asia Yokohama Regional

 

チームメンバー

ixmel先輩…主に実装担当。

T.M先輩…主に考察担当。

ぼく…テンプレ写経やサンプル図示やデバッグなどを担当。 雑用係。

 

先輩方がM1で今年でICPC引退なので、今年限りのチームです。

 

国内予選まで

 

5月中旬ごろにチームメンバーが決まったので、そこから（部の活動も含めて）週3くらいでチーム練をはじめる。あと国内予選対策のための部内合宿を行ったりした。

 

練習のおかげか、国内予選1週間前にあった模擬国内予選*2では、国内予選の参加資格のあるチームの中で7位という素晴らしい成績をとれた。いえい！w

模擬国内後はライブラリを少し追加したり去年の国内予選の後ろのほうの問題を解いたりしていた。

 

国内予選

 

大雨の影響で大学が休講&JR運休で参加が危ぶまれていたものの、3人とも大学にたどり着くことができたので、ixmel先輩の研究室で出ることに。（研究室には作業している人が何人かいて、うるさくして少し申し訳なかったです…）

 

コンテストが始まって、ぼくがテンプレを写経している間、先輩がABを読む。テンプレ写経が終わってすぐixmel先輩がAを書いてAC。その後Bの実装方針をixmel先輩と一緒に考えながら実装していた。T.M先輩はCとDの考察をしていた。Cが全探索でできそうだと言われたので、解法をきいて、Dの考察をしてもらう。Bの実装が終わってサンプルを試すと、半分より右側や上側で折った時にバグってることがわかったので（というか考慮してなかったので）、そこを直して提出してAC。ixmel先輩にCの解法を伝えて実装してもらう。Dは各チームの勝ち数はわかるので枝刈り全探索で解けることがわかって、T.M先輩にEFの考察をしてもらう。CはすぐACしたので、ixmel先輩にDを実装してもらう。Dの実装が終わってサンプルを試してみるとだいぶ遅いので枝刈りを強化したりする。その後提出するとAC。このとき全体4位で結構盛り上がった。

 

この段階でEとFの両方ともの解法がわかっていなかったので3人で考える。Eは繰り返し二乗法で二進数の足し算をやればいいのかなあという話になってixmel先輩が実装を始める。（実装だいぶ手こずっててつらそうだった。）実装が終わってサンプルを試すとサンプルがあわない。つらい。Fが1辺の長さを二分探索して下辺のy座標を決め打ちしてしゃくとりっぽくやるとできそうと思いつく。Eの考察を再びT.M先輩に任せてixmel先輩とFの実装をする。つらそう。なんとか実装を終える。サンプルをためすと合うけど遅い。計算機パワーを信じて提出することにする。Fはpcしゃんにがんばってもらう*3。T.M先輩がEの解法を思いついたのでixmel先輩が実装する。実装つらそう。実装がおわってサンプルを試すとサンプルが再びあわない。かなしいね。Fのデータセット1つめがおわりません。コンテスト時間がおわりました。（Fの計算量がやばだったことがあとで判明しました。）

 

結果は4完23位。（4完最速）

 

f:id:wk1080id:20180708164824p:plain

4完した時点で2時間くらい残っていたのであと1~2問は解きたかったなあという気持ち。4完後の考察&実装の練習をたくさんしたんだけどなあ。

 

おそらくアジア地区大会には行けるので、英語力を強化して、アジア地区では良い成績をとりたいです。先輩方は2回目のアジア地区、ぼくは初めてのアジア地区です。がんばるぞー！

 

 

*1:twitterにチーム名を書くとリンクになるのがおもしろかった

*2:2018/Practice/模擬国内予選/案内 - ACM-ICPC Japanese Alumni Group

*3:お願い、死なないでpcしゃん！あんたが今ここで倒れたら、F問題はどうなっちゃうの？時間はまだ残ってる。ここでACできたら5完できるんだから！次回「Fの解法、死す」。デュエルスタンバイ！