ARC047

問題元　→　Welcome to AtCoder Regular Contest 046 - AtCoder Regular Contest 046 | AtCoder

A - ゾロ目数

概要

一つの数字から成る数値を値が小さい順に並べたときの項目を求めよ．

解法

桁が一つのゾロ目数は，桁が二つのゾロ目数は．
これからわかるように，項目で使われる数字は，何桁の数字であるかはで求めることができる.
（ただし，与えられるは1-indexedなので0-indexedに直す必要がある．）

n = int(input()) - 1
print(str(n % 9 + 1) * (n // 9 + 1))

B - 石取り大作戦

概要

Nから始まり，数値を減らしていき，0を言った方が勝ち．
高橋君は数をまで減らすことができる．
青木君は数をまで減らすことができる．
お互いが最善を尽くした時，勝つのはどちらか求めよ

解法

場合分けをする． 基本の考えは自分が を言えれば勝ち（0を宣言できる）であること．
これを延々と繰り返していけば，最初に自分がとるべき行動がわかり，どちらの必勝かがわかる．

これのの場合と同じゲームが小学校の頃にちょっとだけ流行ったことを覚えている．確か「恐怖の20」という名前だった．
教わった日の夜，お風呂場で必勝法を必死に計算したのを覚えている．
小学生にプログラムを教える際の良い題材になるかもしれない．

T = "Takahashi"
O = "Aoki"
def solve(N, A, B):
    if N <= A:
        return T
    if A == B:
        m = N - ((A + 1) * (N // (A + 1)))
        if 0 < m <= A:
            return T
        else:
            return O
    if A > B:
        return T
    return O

N = int(input())
A, B = list(map(int, input().split()))
print(solve(N, A, B))

C - 合コン大作戦

概要

男がN人，女がM人いる．それぞれ異性で，かつ年収が一定以上のパートナーを探している．
最大で何人のカップルが作れるか？

解法

一見して二部マッチングや安定な結婚問題のようだが，これらを解くアルゴリズムを使うのは制約の関係から時間的に不可能．残念．

かなり高速な部類の二部マッチングですら解を求めることが間に合わない以上，何かしらの貪欲な手法が隠れていることがわかる．
また「二部マッチングを解くアルゴリズムでは間に合わない」を言い換えると，「ある女性をどの男性とくっつけるかを求める時に，全ての男性を見る必要があるようでは間に合わない」となる．
（この解釈が本当に正しいのかはあまり自信がない．でもあるノードからの増加路を一つも見つけられなかった場合「全ての男性を見た」と同じことをしている訳で，そんなに外れた解釈ではないはず．）
（全てを見る必要をなくすと言えばSegment Treeだなぁ，なども考えられる．）
ここから逆算して良さそうな方法を考えていく．

まず，全ての男性が年収円を求めており，全ての女性が年収が円以上であるとする．
その仮定の上で適当な女性から順に条件に見合う男性をあてがってみる．
この時，どのような男性を当てがうのがいいだろうか？
これはカップル成立の条件を満たしていて，かつ，女性の求める年収との差が最も小さい男性がよい．
例えば，最も年収の差が小さい男性と次点で差が小さい男性の二人の候補がいる場合を考える．
この時

• 後者の男性を選んでしまうとどうなるか？
  後にひかえている女性全てが前者の男性を超える年収を求めている場合に最終的なカップルの数が一つ少なくなる．

• 誰も選ばなかった場合は？
  これも，後に控えている女性全てが前者の男性を超える年収を求めている場合に最終的なカップルの数が一つ少なくなる．

また，一人の男性を先に選んだために，後のマッチングで作られるカップルの数が二つ以上減ることはありえない．
したがって，求める年収との差が最も小さい男性を選んでおけば損をすることはない．

一部の男性を見るだけ済み，かつ貪欲な方法を考えつくことができた．
あとは先の仮定が成り立つように状態を調整し，その上で解を探せば良い．

仮定が成り立つように状態を調整するのに（ソートするのに）.
求める年収との差が最も小さい男性を選ぶのに(BITを使った二分探索に) ．
結果として．
なので十分間に合う．

...はずなんだけどなぁ？

あとは，平衡二分木を書くくらいしか計算量を減らす方法が考えられない． 素直にC++で書くべきかもしれない．

class BIT(object):
 
    def __init__(self, size, init_data=None):
        self.size = size
        if init_data is None:
            init_data = [0] * (size + 1)
        # self.data = array("q", init_data)
        self.data = init_data
 
    def sum(self, idx):
        ret = 0
        while idx > 0:            
            ret += self.data[idx]
            idx -= idx & -idx # idx = idx & (idx - 1)
        return ret
 
    def add(self, idx, value):
        while idx <= self.size:
            self.data[idx] += value
            idx += idx & -idx
 
    def lower_bound(self, idx):
        if self.sum(self.size) - self.sum(idx-1) == 0:
            return 0
        left, right = idx - 1, self.size
        while (left + 1) < right:
            mid = (left + right) // 2
            if self.sum(mid) - self.sum(left) > 0:
                right = mid
            else:
                left = mid
        return right
 
def unique(arr):
    arr.append("#")
    top = 0
    idx = 1
    while idx < len(arr):
        while arr[top] == arr[idx]:
            idx += 1
        arr[top+1] = arr[idx]
        top += 1
        idx += 1
    return arr[:top]
                
if __name__ == "__main__":
    N, M = list(map(int, input().split()))
    queries = [(lambda x: (int(x[1]), 0, int(x[0])))(input().split()) for _ in range(N)]
    queries += [(lambda x: (int(x[0]), 1, int(x[1])))(input().split()) for _ in range(M)]
    queries.sort()
    integers = unique(sorted(q[2] for q in queries))
    dic = dict(zip(integers, range(1, len(integers)+1)))
    bit = BIT(len(dic))
    ans = 0
    for a, c, b in queries:
        if c == 0:
            bit.add(dic[b], 1)
        else:
            idx = bit.lower_bound(dic[b])
            if idx:
                bit.add(idx, -1)
                ans += 1
    print(ans)

概要

解法