ARC103/ABC111 D Robot Arms
これ
D - Robot Arms
を解いた。
解説はこれ
https://img.atcoder.jp/arc103/editorial.pdf。
参考にしたのはこれ
AtCoder ARC 103 D - Robot Arms (600 点) - けんちょんの競プロ精進記録。
という長さのアームがあれば、各格子点のx座標とy座標の和が奇数であり、
以下の部分に色がついた、市松模様ができる。
いくつか実験すると、成り立つことが分かる。
あとは、マンハッタンマンハッタンした感じにすると、x軸とy軸を独立に処理できるので、なんとかなる。
というわけで、pythonでの実装はこれ。
def solution(x,y): ans = '' nowx, nowy = 0,0 preX = [0]*31 preY = [0]*31 for i in range(31): if nowx < x: nowx += 2**(30-i) preX[i] = 1 else: nowx -= 2**(30-i) preX[i] = -1 if nowy < y: nowy += 2**(30-i) preY[i] = 1 else: nowy -= 2**(30-i) preY[i] = -1 for i in range(31): if preX[i] == -1 and preY[i] == -1: ans += 'L' elif preX[i] == 1 and preY[i] == 1: ans += 'R' elif preX[i] == -1 and preY[i] == 1: ans += 'D' else: ans += 'U' return ans N = int( input()) X = [0]*N Y = [0]*N x, y = map( int, input().split()) X[0] = x Y[0] = y evod = (x+y)%2 Flag = True for i in range(1,N): x, y = map( int, input().split()) X[i] = x Y[i] = y if (x+y)%2 != evod: Flag = False if Flag: D = [2**i for i in range(30,-1,-1)] if evod == 1: print(31) print(' '.join(map(str,D))) for i in range(N): print( solution(X[i]+Y[i],X[i]-Y[i])) else: print(32) D.append(1) print(' '.join(map(str,D))) for i in range(N): print( solution(X[i]+Y[i]-1,X[i]-1-Y[i]) + 'R') else: print(-1)
pythonの「=」について
pythonの「=」がよくわからなかったが、教えてもらったり、先述の「苦しんで覚えるC言語」でメモリとかポインタとかを勉強してちょっと分かったので、まとめる。
a = 1 b = a a = 2 a b
すると、次のようになる。
2 1
これは当然。
で、次にリストの一部を変更してみる。
a = [1,2,3] b = a a[0] = 1000 a b
すると、次のようになる。
[1000,2,3] [1000,2,3]
私はここでaだけが更新できると思ったけど、bも更新された。
混乱した。
これは、C言語でいうと、配列は配列の先頭のメモリを指定しているものであるため、
pythonのリストは確保したメモリの先頭を指定している。
従って、同じメモリ領域を使っているため、aとbが等しくなってしまうのです。
ちなみに、メモリ領域を確保しなおせば良いので、次はうまくいく。
a = [1,2,3] b = a a = [1000,2,3] a b
で、こうなる。
[1000,2,3] [1,2,3]
AGC028 B問題
AtCoder Grand Contest 028のB問題を解いた。
時間内には解けなかったし、解説もよくわからなかった。
問題はこれ
B - Removing Blocks。
解説はこれ
https://img.atcoder.jp/agc028/editorial.pdf。
参考にしたのはこれ
AGC028 B問題 Removing Blocks - banbooooのブログ。
解説
解説でよく使われる確率を理解できたことが殆どなかった。
今回もそれ。
いろいろ調べてたら上の参考サイトを見つけた。
解説などに置ける、同様に確からしい確率は確率を表しているわけでなく、
背反な事象でそれぞれの個数が等しいもののことを言っているということがわかった。
数学っぽく言うと、数え上げ測度の等しい disjoint な可測集合たちのことを言っていることがわかった。
とはいえ、確率の気持ちで理解するのは大事っぽい。
同様に確からしいっぽい気持ちで考える問題もよく見る。
解説をします。
i番目のブロックを取り除いたとき、j番目のブロックの値が加算されるとする。
i番目からj番目までのブロックがどれも除かれておらず、その中で、i番目のブロックが初めに取り除かれる場合の数を求めれば良い。
が成り立つ。
互いに排反なので、
となる。
また、（同様に確からしいの部分だが、）各に対して、
は等しい。
従って、どのに対しても、
となる。
特に、今はの場合である。
あとは、色んなサイト書いてあるように、累積和とかmodにおける逆元とか頑張ればできる。
プログラムは次のやつ。
def getInv(N): inv = [0] * (N + 1) inv[1] = 1 for i in range(2, N + 1): inv[i] = (-(Q // i) * inv[Q % i]) % Q return inv from itertools import accumulate N = int( input()) A = list( map( int, input().split())) Q = 10**9 + 7 fact = [1]*(N+1) invs = getInv(N) accI = [0]*(N+1) for i in range(N): fact[i+1] = fact[i]*(i+1)%Q accI[i+1] = (accI[i]+invs[i+1])%Q factN = fact[-1] ans = 0 for i in range(N): C = factN*(accI[i+1] + accI[N-i]-1)*(A[i]%Q)%Q ans += C ans %= Q print(ans)
ARC094/ABC093 D問題を解いた
めっちゃ調べて、なるほどって言いながら解いた。
解いた問題はこれ
D - Worst Case。
解説がこれ
https://img.atcoder.jp/arc094/editorial.pdf。
解説はよくわからなかったので、これ
AtCoder ARC 094 D - Worst Case (700 点) - けんちょんの競プロ精進記録
を参考にして解いた。
これを読むと、元の解説でなんであんなことをしているかも理解できる。
解説
最大となる組み合わせは、1,2,...,xと1,2,...,xという頂点を逆順で組み合わせることで得られることが分かる。
途中に存在するであろうA, Bを飛ばす必要があるため、解答はx-1である。
1, 2, ..., x-1, x x, x-1, ..., 2, 1
このとき、この最大値は
(x+1)//x * (x+1 - ((x+1)//2))
である。
感覚的に
x//2 * (x - x//2)
だと思っていたので、めっちゃ混乱した。
ここで、B = A + nであるとすると、最大はA*(A+(n-1))以上になることが分かる。
n >= 1であれば、（AとBが異なることに注意すると）積の最大値はA.Bを飛ばしても実現されることが分かる。
A=Bのときはよくわからない。
というわけで、そこは別で扱うことにする。
Q = int( input()) def matching(A,B): #最大となる組み合わせは、1,2,...,xと1,2,...,xという頂点を逆順で組み合わせることで得られることが分かる #このとき、これらの積の最大値は(x+1)//2*(x+1-(x+1)//2)である #ここで、B = A + nであるとき、最大はA*(A+(n-1))以上になることが分かる。 #n >= 1であれば、積の最大値はA.Bを飛ばしても実現されることが分かる。 if A == B: return 2*A - 2 S = A*B L, H = 0, A*B while H - L != 1: M = (L+H)//2 if ((M+1)//2)*(M + 1 - (M+1)//2) < S: L = M else: H = M return L-1 #L-1なのは、A,Bを飛ばすため for _ in range(Q): A, B = map( int, input().split()) print( matching(A,B))
