Codeforces Round #574 (Div. 2)
こんちー。コドフォの振り返り
A - Drinks Choosing
問題：n人の人が建物の中にいて、aiのドリンクが好きなのが知られている。1つのドリンクセットが2つの部分に分かれていてkタイプのドリンクセットがある。好きなドリンクを受け取れる最大人数を求めろ。n/2の切り上げ値分セットがある。
考察：英文読解。それぞれのドリンクの種類でカウントする
B - Sport Mafia
問題：キャンディーを箱に入れる。ただし前回入れたときより1つ多く入れる。キャンディーを箱から出して食べる。以上の2種類の操作をn回してk個箱に残っているとき食べたキャンディーの数を求めよ
考察：
・貪欲で求めたとき、nは最大でn*(n+1)/2=kとなるn。貪欲に求めたとき最大√kなので間に合う。
感想：
・怖かったので二分探索した。
・BはAより読みやすい文章だった(英語を思い出しただけかも)
C - Basketball Exercise
問題：2*nのmatrixのように人が並んでいる。制約通り人を選んで身長の合計の最大値を求めよ。図を見ると制約がわかりやすい。隣り合っているとダメ
考察：
・各列、1行目の人を選ぶ、2行目の人を選ぶ、どちらも選ばないの3通りが考えられる。
・2列以上前の状態は、いまの列に関係なさそう。隣り合うかどうかに前列は関係する。
・DPで解ける
・dp[i][j]：ｉ列目にｊ行目の人を選んだときの、ｉまでの身長の合計の最大値
・dp[i][0]=max(dp[i-1][0],dp[i-1][1],dp[i-1][2])
・dp[i][1]=h[i][1]+max(dp[i-1][0],dp[i-1][2])
・dp[i][2]=h[i][2]+max(dp[i-1][0],dp[i-1][1])
・以上の遷移で計算しdp[n][0],dp[n][1],dp[n][2]の最大値が問題の答えとなる
感想
・図がわかりやすく、解法も典型だったのでスラスラ解けて楽しかった
D1 - Submarine in the Rybinsk Sea (easy edition)
D2 - Submarine in the Rybinsk Sea (hard edition)
問題：N個の整数aiが与えられる。任意の2つの組み合わせi,j(重複を許す)のN^2通りについて、下で定義するf(ai,aj)を求めて足せ。ただし答えが非常に大きくなるため998244353で割った余りで答えよ
・f(a,b)：stringにして、下の位からb,aの順で1桁ずつ繋げる。長い方は余った分先頭に繋げる。詳しくはコドフォで見てください。
D1：全てのaiは長さが等しい
考察：
・D1はかなりシンプル。長さが同じなので123と???なら、1?2?3?か、?1?2?3のどちらかになる。もっと言えばどちらにもなる。
・関数ｆの引数であるaになる場合とbになる場合がそれぞれ何通りあるかを考えると、Ｎ通りずつである。
・したがって123なら112233と各桁2回繰り返したものをＮかけて、Ｎ個の数字で足せばよい。
実装：
・実装難なので書いておきます
・aiをstringで入力しておくとto_stringとか使わなくてよいので楽
・各桁の処理はstringの頭からやる。次の桁にするのは10進法なので*10する
string s=a[i];
long long int res=0;
for(int k=0;k<s.size();k++){
res=(res*10)%MOD;
res+=a[i][k]-'0';
res=(res*10)%MOD;
res+=a[i][k]-'0';
}
数字のchar型から'0'を引くのはよく使うと思います。
後から10をかけるより前に１０をかけるほうが実装が楽です。
aiが最大10ケタなので、MODを取らないと最大20桁になりオーバーフローすることに注意しましょう。
MOD取る問題はしつこいくらいMOD取っておくほうが結果的にバグが少なく早く通るイメージ。
D2:aiによってケタの数が違う場合がある
考察：
・D1の考察から各aiに対してaになるとき、bになるときを足すと楽だということがわかる。
・ｆのもう一つの引数がどんな値でもある桁数なら同じ寄与になる。
１．f(ai,x)、f(x,ai)についてｘの桁数1～10で場合分けしてそれぞれ求めて足しておく
２．N個のaiそれぞれがxになるとき、上で計算した合計値を足す
・１のループ内である長さのaiの個数を数えておくと２が10回のループで求まるので少し早くなる。まあ１が最大10^7のループなので、あまり変わらない。
・実装についてはD1とほぼ変わらず、ｘの長さで場合分けしてaiのほうが長ければ先頭何文字かを別処理すればよいだけです。
感想：
・実装問かつ、苦手な文字列操作だったんですけど、結構早く通せてうれしかったです。Ｄ１、Ｄ２に分かれていると考察がテンポよく進んで楽でした。
E - OpenStreetMap
問題：n*mのmatrixがある。範囲内のa*bの部分matrix内の最小値を、あり得る(n-a+1)*(m-b+1)通りで足せ。
考察：
・範囲最小値とかseg木だろ～(脳死)→MLE
・OMG；
・3000*3000のseg木は最大3.6*10^7くらいの大きさになるのかな？
・それを元と横で取った値の整理で2本作ったのでそれはMLE
・Segment Treeを使う解法
・単純にN*Mに対してセグ木を作る。縦で見るセグ木と横で見るセグ木を作るなどするとMLEする。
・したがって横の値をループの中で動的に確保し、b個の最小値だけを記録しておく
・縦で見るセグ木は長さｎをm-b+1個持ったがメモリは足りた。
・横の最小値を求める際、値を随時更新するとN*MlogMかかりTLEする
・一回ベクトルか配列に、ｍ個の値をまとめておき、一気にセグ木を作る
・こうすることでN*Mの定数倍に削減できる
・同じことを縦で見るときにも適用すればギリギリ間に合う
感想：
・AtCoderでは滅多に見ないMLEが出て焦った
・動的な確保をする。ベクトルから初期化する。というやり方は便利そうなので是非覚えたい
感想
D2を通したとき50分くらいで、Eにかけられる時間はかなりあったので通したかったですね。
やっぱり実装の遅さがネックになっていそうです。
というか、これからの難易度では実装スピードが本質っぽい気がするので、実力不足って感じですね
セグ木の区間で値を取得するとき[a,b)で設定しているんですけど、どっちが閉区間だっけ、開区間だっけって言ってたらバグりましたしね
範囲を示すindexの管理もa引くのか足すのか1引くのか足すのかみたいな
実装むずー
P.S. D2までのボトルネックは英文読解なんですけど、これは諦めてる
