ABC138参戦記

はじめに

ABC138に参加しました。結果は以下の通りです。
結果:５完　60分+2WA
順位:742
パフォーマンス:1490
レート変動:1506→1502
結果はちょっと良くなかったですね...来週の第一回日本最強プログラマー学生選手権の予選に向けて頑張りたいと思います。
以下問題を振り返っていきます。言語はPython3(Pypy3)です。

A

time: 1:30
はい

a = int(input())
s = input()
print('red' if a<3200 else s)

(ちょっと短く書き直してみました）

B

time: 1:30
はい

N = int(input())
A = list(map(int, input().split()))
res = 0
for ai in A:
    res+=1/ai
print(1/res)

C

time: 18:00
ソートして小さい方からかなぁと思ったのですが確信が持てず、一回飛ばしてDを先に解きました。戻ってきてからも証明がよくわからなかったのでぐだぐだ考えてしまいました...冷静に考えればそれはそうだし、C問題なのでそんなに深く考えるべきではなさそうだし、目をつぶって提出すべきでしたね。完全に戦略ミスです。反省。

N = int(input())
v = list(map(int, input().split()))
v.sort()
for i in range(N-1):
    v = [(v[0]+v[1])/2]+v[2:]
print(v[0])

D 8:00+1WA

time: 10:00+1WA
ちょっと前にオイラーツアーとかを学んでたので、それかなぁとか思ったんですが、冷静にDに出るようなものではなさそうなので、もう少し考えると、まず頂点pのカウンターにxを加えておき、それを最後に下に累積和的な感じで伝えていけば良いことがわかりました。どうやって下に伝えるかですが、DFSでもBFSでも良さそうだったので、dequeを使うと簡単に実装できるBFSを用いました。ちょっといもす法っぽいなぁと思いながらpypyで提出しましたが、結果はなんと1948ms! 心臓に悪いですね... あと一回リストをprintするものを提出するという大失態を犯し1WA。反省。

from collections import deque
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
count = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for i in range(Q):
    p, x = map(int, input().split())
    count[p-1]+=x
q = deque([0])
flag = [False]*N
while q:
    v = q.pop()
    flag[v] = True
    for e in G[v]:
        if flag[e]:
            continue
        count[e]+=count[v]
        q.append(e)
print(*count)

本番ではリストを空白区切で出力するのに' '.join(list(map(str, count)))を使ったのですが冗長すぎました。*countの方が簡潔で速いです。

E

time: 27:00+1WA
まず、文字列tの前方から貪欲にsの出来るだけ長い部分列を取り除いていく問題であることがわかります。ただそれをナイーブに実装していてはとても間に合わないので、下処理を施しておくことで、どうにか高速に処理できないかなぁと考えます。ここでよくあるテクニックが各要素についてそれが出現するインデックスをはじめにメモしておくことです(インデックスの逆写像的なやつです）。
こうすれば任意の要素についてその出現箇所がすぐにわかるようになります。そうすると部分列というのはインデックスの増加列と対応しているので（実は今日、こういう話を数学のゼミでちょっと触れました）、tの前方から、tの要素に対応するインデックスの中から適当に一つ選ぶことによって出来るだけ長い増加列を作るという問題にすり替わります。これは貪欲に実現できます。つまり、「直前のインデックスより大きい最小のインデックスを選ぶ」とすれば良いです。これは二分探索によりO(logn)で実現できるので全体としてはO(nlogn)くらいで解けました。
ところで、これは本質ではないですが、**pythonのbisectライブラリにはbisect_leftとbisect_rightという二つの関数が存在します。**どちらもxよりも大きい最小の要素のインデックスを返しますが、xが要素に含まれる際の挙動が異なります。例えばbisect_left([0, 1, 2, 3, 4], 1) = 1ですが, bisect_right([[0, 1, 2, 3, 4], 1) = 2となります。より正確に言えば、bisect_leftはx以上要素のうち最小のインデックスを返し、bisect_rightはxより真に大きい要素のうち最小のインデックスを返します。今回は狭義の増加列を求めたいのでbisect_rightを使うべきですが、僕は最初bisect_leftを使ってしまいWAになってしまいました。反省。

import sys
from bisect import bisect_right
s = input()
t = input()
n = len(t)
index = [[] for i in range(26)]
for i in range(len(s)):
    j = ord(s[i])-97
    index[j].append(i)
tmp = -1
ans = 0
for i in range(n):
    j = ord(t[i])-97
    if len(index[j])==0:
        print(-1)
        sys.exit()
    k = bisect_right(index[j], tmp)
    if k<len(index[j]):
        tmp = index[j][k]
    else:
        ans+=1
        tmp = index[j][0]
print(ans*len(s)+tmp+1)

97はord('a')です。

F

制約が10**18と無茶苦茶大きいので$log$がかかる感じにならないと間に合いそうにないです。そこで二進表示の桁ごとに考えるという方針が立ちます。ごちゃごりゃ考えていると、$x\rm xory$がxで割った余りであることから、$x \rm xor y < x$であることがわかります。もしxとyの二進数での桁が異なるとすると例えばx=1010, y = 10001などを考えればわかるようにx xor yはyと同じ桁数になってしまうので$x<x \rm xor y$となり矛盾します。よってxとyの桁数は等しいことがわかります。そうすると必然的に$y%x=y-x$となるので、結局問題の条件は$x \rm xor y = y-xと$言い換えることができます。これは桁ごとに考えることができるので、x,yの各桁ごとの組は(0, 0), (0, 1), (1, 1)のみであることもわかります。問題は端っこの処理です。こういうのは桁dpだろうなぁと思ったのですが、うまくまとめきれずコンテスト中には解けませんでした。
以下は解説を参考にして書きました。
問題を整理すると以下のようにまとめられます。

L<x, y<R、x, yの最上位ビットが同じであるという三つの条件を満たす(0, 0), (0, 1), (1, 1)の列 の個数を求める。

そこで以下のようなdpを考えます。

dp[i][flag_L][flag_R][flag_M] (i:確定している桁, flag_L:L<xがすでに満たされているか, flag_R:flag_Lと同様, flag_M:最上位ビットが等しいという条件がすでに満たされているか)

普通の桁dpと比べて条件が2つ増えており、なかなかに煩雑ですが、気合いを入れて実装すると以下のようになります。

L, R = map(int, input().split())
mod = 10 ** 9 +7
l = '{:060b}'.format(L)
r = '{:060b}'.format(R)

memo = [[[[-1]*2 for i in range(2)] for j in range(2)] for k in range(60)]
def f(pos, flagL, flagR, flagM):
    if pos == 60:
        return 1
    if memo[pos][flagL][flagR][flagM] != -1:
        return memo[pos][flagL][flagR][flagM]
    ret = 0
    #(0, 0)
    if flagL or l[pos] == '0':
        ret+=f(pos+1, flagL, 1 if r[pos]=='1' else flagR, flagM)
    #(0, 1)
    if flagM and (flagL or l[pos]=='0') and (flagR or r[pos]=='1'):
        ret += f(pos+1, flagL, flagR, flagM)
    #(1, 1)
    if flagR or r[pos]=='1':
        ret += f(pos+1, 1 if l[pos]=='0' else flagL, flagR, 1)
    memo[pos][flagL][flagR][flagM] = ret%mod
    return ret%mod
print(f(0, 0, 0, 0)%mod)        

二進表示の文字列を取得する'{:060b}'.format()は覚えておきたいですね。あと条件分岐も3つのif文の線型結合的に書くと、結構楽に実装できるのはうまいなぁと思いました。今回は再帰関数の方が楽っぽいですね。

メモ

ord: alphabet→num
bisect_rightとbisect_leftの違い
インデックスの逆写像
桁DP
'{:060b}'.format()