参加日記: Pythonで解くAtCoder ABC 253 AからF(CのみC++)

A - Median? (3つの解き方)

3つの値a,b,cをソートした時に、bが真ん中に来るかを判定すればよいです。以下の3つが考えられます。

• 案1: 実際にソートをしてbが真ん中(0-indexedでは[1])かを判定するsorted([a,b,c])[1] == b
• 案2: bが中央というのは、a,b,cかc,b,aの並びしかないので(a<=b<=c) or (c<=b<=a)
• 案3: bが中央というのはbが最大でない かつ 最小でない ならば真ん中になるので、not (a < b and c < b) and not (b < a and b < c)

以下2つ注意です。

• a=b=cなどのケースもあることに注意します。(<か<=など注意します)
• 中央値を求めるとき、要素の数が偶数の時は定義を確認してください。真ん中の２つの平均だったり、問題によっては真ん中のどちら（小さい方か、大きい方か）が違うこともあります。

a, b, c = map(int, input().split())
# 以下のどれか
print("Yes" if sorted([a,b,c])[1] == b else "No")
print("Yes" if (a<=b<=c) or (c<=b<=a) else "No")
print("Yes" if not (a < b and c < b) and not (b < a and b < c) else "No")

B - Distance Between Tokens

解法1: マンハッタン距離 |h1-h2| + |w1-w2|

解説通りです。
https://atcoder.jp/contests/abc253/submissions/32005090

解法1-2: 一次元配列とみてマンハッタン距離

やっていることは解法1と同じです。

解法1はh,wの座標をもってマンハッタン距離を計算します。これと同じことを、１次元配列上の"o"のindexで計算することもできます。

--o
o--

というのを--oo--という配列とみて、2つのoのindexであるa, bを2, 3とします。この時、b//w - a//w + abs(b%w - a%w)になります。ときおり、入力が１次元配列で任意の長さで切ったときにこのような距離を求めたくなることがある...かもしれません。

実装(Python)

```Python h, w = map(int, input().split()) s = [] for h in range(h): s += list(input()) a, b = [i for i, char in enumerate(s) if char == "o"] print(b//w - a//w + abs(b%w - a%w)) ```

C - Max - Min Query (C++)

解法1: multisetでシミュレーション

解説通りです。multisetで書いてある通りに実行します。解説の通り、multiset::eraseは値で指定するとすべて消してしまうことに注意します。

このケースではクエリ1が1個しか値を追加しませんが、c個追加する場合はmultisetではなく、mapで個数を管理すると良いです。この場合、map.second == 0になっても、mapからキーが消えるわけでないので、

if(cnt[x] == 0) cnt.erase(x);

などしてキーを消す必要があります。

• multiset版

• map版

解法2: セグメントツリーやBIT上での２分探索(ACLの練習)

明らかにtoo muchで面倒です。

• クエリ先読みをし、座標圧縮します
• １点加算、区間クエリができるセグメント木を用意します
• クエリを処理し、クエリ3の際には、右端からの区間和が0でなくなる最初の要素、と、右端からの区間和が全区間の和と等しくなる最初の要素、つまり最小と最大の要素を座標圧縮前に戻し、引き算します

この実装にはatcoder::segtree::max_right<f>(l)を使います。ドキュメントの通り、fを満たす最大のindexの+1を返します。

計算量は$O(QlogQ)$です。
https://atcoder.jp/contests/abc253/submissions/32081544

D - FizzBuzz Sum Hard

解説以外思い浮かびませんでした。包除原理です。

import math
def lcm(x, y): return (x * y) // math.gcd(x, y)
def sigma1(n): return n * (n + 1) // 2
n, a, b = map(int, input().split())
c = lcm(a, b)
acnt, bcnt, ccnt = n // a, n // b, n // c
print(sigma1(n) - sigma1(acnt) * a - sigma1(bcnt) * b + sigma1(ccnt) * c)

E - Distance Sequence

これも解説通りです。$dp[i][j]$は、$abs(k-j) >= k$であるような$dp[i-1][k]$のすべての和です。
各$i$の計算に入る前に累積和(更新はないので単なる累積和で良いです)を求めます。

F - Operations on a Matrix

長々と書いていますが、結局解説通りです。

この問題はクエリ1は区間を、クエリ2は１点を更新することに注意します。
ここで、次の2つの小問題を考えます。

小問題1: クエリ2と3しかない場合

この時、クエリ2はすべての$j$の$i$を置き換えるので、クエリ3のjは無視してよいです。このため、クエリ3はiに対する最後のクエリ2のx(がない場合は初期値0)を答えれば良いです。

小問題2: クエリ1と3しかない場合

この時、クエリ1はすべての$i$の$l$から$r$の$j$を置き換えるので、クエリ3の$j$は無視してよいです。

クエリの数が小さい場合、あるクエリ3のjに対して、それまでのクエリ1のlからrの範囲に入っているxすべての和を求めればよいですが、クエリ数が多いのでこれでは、$O(Q^2)$かかってしまい、間に合いません。例:1 1 1 1というクエリが大量にあり、3 1というクエリが大量にあるときを考えてください。そこで、区間加算・一点クエリ可能なBIT(やセグメント木など)を用います。
クエリを順に処理して、1はl,rの区間にxを加算します。そして、3が来たら$i$の値を取得します。

これらを合わせて考える

F問題に戻るとは、クエリ1,2,3が存在します。

さて、クエリ3の時、小問題2だけを考えたとします。ところが、クエリ2はそれまでのクエリ1の結果が何であっても、xという値に書き換えてしまいまいます。逆にいえば、クエリ2の後のクエリ1はそのクエリ3に影響します。つまり、あるクエリ3 i,jはiに対する最後のクエリ2のxに、jがl,rの範囲に入っているすべてのクエリ1のxを足したものを答えればよいです。ところが、小問題2で見た通り、これらのクエリ1の存在をすべて確認するのは大変です。

次の例を考えます。(コメントはクエリは20, 5に対してだけなので、これに注目します)

# 20, 5は最初0です
1  3 10 1 # j=5は範囲内なので値は1
1  1  6 1 # j=5は範囲内なので値は2
1 10 10 1 # 範囲外なのでなにもしない
3 20  5 # 2を出力
2 20 100 # i = 20は対象なので値は100
1  3 10 1 # j=5は範囲内なので値は101
1  1  6 1 # j=5は範囲内なので値は102
1 10 10 1 # 範囲外なのでなにもしない
3 20  5 # 102を出力

さて、値は2, 102の出力になりますが、これは、クエリが少ないので追いきれました。

次のように工夫します。以下、「時間」とはそのクエリの順番を示します。

• 最初にクエリ2とクエリ3だけを先読みし、各クエリ3に対応するクエリ2と、そのクエリの時間及び、クエリで更新される値を覚えておきます。
• 次にクエリを再度、クエリ1,3だけ処理していきます。クエリ1は小問題2のようなBIT(区間加算・一点クエリ可能)を持っておき、その際のl, rにxを加算します。
• もし、最初に見た各クエリ3に対応するクエリ2の時間になったなら、各クエリごとに対応するその瞬間の(クエリ1向けの)BITのindex=$j$を記録します。
• 次に、クエリ3の処理になった場合、その瞬間のBITのindex=$j$から、先ほど保管したそのクエリのBITの値を引きます。さらに、最初の先読みで記録したクエリ2によって更新された値を足します。(これらの値がない場合は対応するクエリ2が存在しないので、初期値0です)

このように、クエリを先読みすることで計算量が少なくなります。なぜなら、各クエリ3に影響する最後のクエリ2(置換)のタイミングをクエリ3個分覚えておき以上のような処理をすることで、そのクエリ3に関係するクエリ2が発生した直後から、そのクエリ3に関係する最後のクエリ2まで、のクエリ2が加算したxの総和を求めることができるからです。