ARC049

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

A - "強調"

概要

指定された4箇所に'"'を挟むだけ．

解法

Pythonでは文字列を作成する際に"と'の両方を使えるが，文字列中で"を使いたい時は'を，文字列中で'を使いたい場合は"で作成すればエスケープシーケンスを使う必要がなくなる．
例えば

s1 = '"""強調"""'
s2 = "'''強調'''"

string.joinもいいが，python3系ではprint関数でsep='"'を指定する方がちょっとだけ楽．
（この機能，競プロですごく便利．）

S = input()  
A, B, C, D = list(map(int, input().split()))
print(S[:A], S[A:B], S[B:C], S[C:D], S[D:], sep='"')  

B - 高橋ノルム君

概要

2次元平面上に 人の高橋君がいる．にいる高橋君はへ移動するのにの時間がかかる．最も適した場所を選んだ時，全員が集合するのにかかる最小の時間は？

解法

全ての点を調べることは不可能な以上，場所を絞る必要があることはすぐに分かる．
また，一般的に，条件を満たす値そのものを求めるよりも，条件を満たす値が存在するかyes/noを求める方が簡単．
ここら辺から逆算すると，時間で集合可能な場所が存在するかを求めれば良さそうなことが分かる．
(時間でどこかしらに全員が集合可能なら，それより少し後の時間でも移動可能．単調増加であり，yes/noが切り替わる箇所は2分探索で求められる．）
また，移動時間の式から，時間内に高橋君が移動できる箇所はそれぞれ座標軸に平行な（？）矩形を描くことが分かる．
通常，重複箇所の判定は非常にややこしいものになるが，この性質を考慮すれば簡単に済む．
ここまできたらあとはコードに落とすだけ．

N = int(input())
X, Y, C = [], [], []
for _ in range(N):
    x, y, c = list(map(int, input().split()))
    X.append(x)
    Y.append(y)
    C.append(c)
 
def check(cost):
    left, right = -10**5, 10**5
    for x, c in zip(X, C):
        left = max(left, x - cost / c)
        right = min(right, x + cost / c)
    if left > right:
        return False
    left, right = -10**5, 10**5
    for y, c in zip(Y, C):
        left = max(left, y - cost / c)
        right = min(right, y + cost / c)
    if left > right:
        return False
    return True
 
left, right = -1, 10 ** 5 * 10 ** 3 + 1
for _ in range(100):
    mid = (left + right) / 2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)

C - ぬりまーす

概要

全ての制約を満たすようにグラフの頂点に色を塗る． 制約は二種類ある.
- 制約1: 頂点xを塗る時，頂点yを塗っていなければならない．
- 制約2: 頂点xを塗る時，頂点yが塗られていてはいけない．
最大でいくつの頂点を塗ることができるか？

解法

何かしら簡単にする方法があるはず．
与えられる制約2の数はこれよみがしに少ないので制約1のみの場合を考える.
まず塗れない箇所を調べる方法を考える．
例えば，
- 頂点xを塗らなければ頂点yを塗れない，
- 頂点yを塗らなければ頂点zを塗れない，
- 頂点zを塗らなければ頂点xを塗れない，
のように，制約がぐるっと輪を作っている場合，どの頂点も塗ることができない．
これは有向グラフに落とし込めそうだ．

では真っ先に塗れる頂点はどこだろうか？これはグラフ上で入次数が0であるノードであることが分かる．
では次に塗れるのは？これは入次数が1，かつ，入ってくる辺の元の頂点が塗られているノード．
ではさらにその次に塗れるのは？これは入次数が2，かつ，入ってくる辺の元の頂点が全て塗られているノード．
（もしくは入次数が1，かつ，入ってくる辺の元の頂点が塗られているノード）
このステップを続けても，制約がぐるっと輪を作っている場合とは矛盾しない．
また，いずれかのステップであえて色を塗らなかった場合，最終的に塗られている頂点の数は必ず少なくなる．
かつ，（制約1のみを考えているので）ある頂点に色を塗ることで他の頂点に色が塗れなくことはない．
よって，この方法で更新が起こらなくなった時に塗られている頂点の数が塗れる頂点の最大となる．
このアルゴリズムをもう少し賢く行うと頂点数を，辺の数をとして塗れる頂点の最大を求めるのに.
ここまでくれば，制約2に関しては，
- 制約2: 頂点yを決して塗らないか、頂点xを塗る時，頂点yを塗っていなければならない．
と言い換えれば良いだけ．
以上から[tex: {O(NA2^B)}].
（振り返ってみると，塗れない箇所云々は必要なかったが，メモとして残しておく．）

class Node(object):
    def __init__(self):
        self.in_degree = 0
        self.cur_inputs = 0
        self.dest = []
 
    def __str__(self):
        return "in_degree:{}, cur_inputs:{}, dests:{}".format(self.in_degree, self.cur_inputs, self.dest)
 
def bfs(edges, N, used):
    from collections import deque
    ret = 0
    nodes = [Node() for _ in range(N)]
    que = deque(list(range(N)))
    for e in edges:
        nodes[e[0]].dest.append(e[1])
        nodes[e[1]].in_degree += 1
    while len(que) > 0:
        n = que.popleft()
        if used[n]:
            continue
        if nodes[n].in_degree > nodes[n].cur_inputs:
            continue
        ret += 1
        used[n] = True
        for d in nodes[n].dest:
            nodes[d].cur_inputs += 1
            que.append(d)
    return ret
        
if __name__ == "__main__":
    from itertools import product, compress
    N = int(input())
    A = int(input())
    YX = []
    for _ in range(A):
        x, y = map(int, input().split())
        YX.append((y-1, x-1,))
    UV = []
    B = int(input())
    for _ in range(B):
        u, v = map(int, input().split())
        UV.append((u-1, v-1,))
    ans = 0
    for flags in map(list, product([0, 1], repeat=B)):
        edges = list(compress(UV, list(map(lambda x: x^1, flags))))
        used = [False] * N
        for e in compress(UV, flags):
            used[e[0]] = True
        ans = max(ans, bfs(YX + edges, N, used))
    print(ans)

D - すわっぷしまーす

概要

解法

解けていない．
で書けてると思うのだが...

ところで，解説（ヒント）のセグメント木に関する記述が面白い．

・たとえば、RMQ(Range minimum Query)をSegTreeでやるとどうなるか?
・[a, b]の最小値というクエリを、O(logn)個の”木の全ての葉の値の最小値”というものに分割している

今まで，RMQ（セグメント木）はをのように分割し，その途中経過を覚えておくことで更新のコストを最小限に抑える手法，のようなイメージだった．
解説の解釈の方が抽象度が高く，応用を効かせやすい．
ぜひ次回に生かしたい．
（そもそも「区間クエリ」って言葉を知らなかったり，セグメント木を知らな過ぎたとも...）

from array import array

class Tree(object):
    def __init__(self, rank):
        self.rank = rank
        self.swap_flags = array("L", [0] * (2**rank))

    def getitem(self, key):
        left, right = 1, 2 ** (self.rank - 1) + 1
        index = 1
        swap_flag = 0
        while left + 1 < right:
            swap_flag >>= 1
            swap_flag ^= self.swap_flags[index]
            mid = (left + right) // 2
            if key < mid:
                index = 2 * index + (swap_flag & 1)
                right = mid
            else:
                index = 2 * index + ((swap_flag & 1) ^ 1)
                left = mid
        return index - 2 ** (self.rank - 1) + 1

    def swap(self, a, b):
        def _swap(a, b, left, right, depth, index=1, swap_flag=0):
            if b < a or right < left:
                return
            if right < a or b < left:
                return
            if a == left and right == b:
                self.swap_flags[index] ^= 1 << depth
                return
            swap_flag ^= self.swap_flags[index]
            mid = (left + right) // 2
            _swap(a, min(mid, b), left, mid, depth-1, 2*index+(swap_flag & 1), swap_flag >> 1)
            _swap(max(a, mid+1), b, mid+1, right, depth-1, 2*index+((swap_flag & 1) ^ 1), swap_flag >> 1)
        for d in range(self.rank):
            left, right = 2 ** d , 2 ** (d + 1) - 1
            _swap(max(a, left), min(b, right), left, right, d)


if __name__ == "__main__":
    N, Q = list(map(int, input().split()))
    tree = Tree(N+1)
    for _ in range(Q):
        t, a, b = list(map(int, input().split()))
        if t == 1:
            print(tree.getitem(a))
        else:
            tree.swap(a, b)

単体テストの作成にハマる

要約

InternalVisibleToに渡した名前が異なっていた． プロジェクトのプロパティからアセンブリ名を変更した．

VisualStudio2013での単体テストプロジェクトの作成

ここらへんをみる．
リンク先は2015だが大して変わらない．

[ファイル]→[追加]→[新しいプロジェクト]→[Visual C#]→[単体テストプロジェクト]

ここまではよい．

Internal/private属性のメソッドのテストに失敗する

Internal/private属性のメソッドのテストも作りたいなーとなる．当然なる. しかしクラス内にテスト用のメソッドを埋め込むのも避けたい．当然避けたい。
こういった場合C#（.NET?）に便利な機能があり，どうやらProperties内のAssemblyInfo.csに

[assembly: InternalVisibleTo(“XXXXXX”)] // XXXXXXは参照元のアセンブリ名

と、おまじないを追加すると良いらしい．

しかし追加しても単体テストプロジェクトから なぜかアクセスできない.

（ アクセスできない保護レベルになっています ）

アセンブリ名はプロジェクト名ではない

結局、アセンブリ名とプロジェクト名を混同していたことが原因だった。

プロジェクトのプロパティ内に アセンブリ名 　の項目がある．
最初のプロジェクト作成時に適当な名前を付けて，あとからソリューションエクスプローラー内で名前を変更すると，この「アセンブリ名」と「プロジェクト名」に不一致が生じる．
これを直せばちゃんとテストしてくれる．うーん便利。

感想

特にどこにも書かれていなかったので原因の発見まで時間がかかり、辛かった． 仕組みわからないで使うのはよくないね.

念のため

アクセスレベル云々の前に，そもそも参照できない場合，

[ソリューションエクスプローラーでプロジェクトを右クリック] → [追加] → [参照] → [ソリューション] → [プロジェクト]

から参照を追加すれば良い．

【メモ】土台手順と伸ばし手順について

メモ

土台の目的

• 土台作成時点では，将来的に14,15連鎖も望めることが重要
  • 相手が大連鎖を打った場合にも対応できない→死
• フィールド全体を使えるように組む必要がある
  • 純正15連鎖を打つ場合，60マスを利用し，残りは16マス（窒息箇所は使えないとして）
  • 第2折り返し第1折り返しの兼ね合いから，実際には更に減る
  • 発火テンパイ状態で8マス残っていれば4手捨てられる
    • ある一色が来る確率は7/16，4回連続で来ない確率は1/10程度．案外打てない
  • 発火テンパイ状態で10マス残っていれば5手捨てられる
    • 5回連続で来ない確率は1/20程度
  • 1マス，2マスの節約が大きな効果を生む

伸ばしの目的

• 伸ばしでは相手の先打ち本線よりも大きい連鎖（高い得点）を組む必要がある
• 5連鎖先打ちには7連鎖，6連鎖先打ちには8連鎖，9連鎖先打ちには11連鎖を合わせられれば勝ちは固い
• つまり，決まった連鎖数が組めればよい
• フィールド全体を使う必要はない

土台手順と伸ばし手順の違い

• 土台手順では"無駄なマスが生じないよう"組む
• 伸ばし手順では"決まった連鎖数が最短で目指せるよう"組む
• 両者は目的が異なる

例

土台手順で身についた癖が伸ばしの効率を落とす例

• ↓速攻二ダブが決まった．相手は崩れ気味に5連鎖を発火．ネクストは緑ゾロ，ダブルネクストは黄色ゾロ．

• ↓土台手順では12寝かせが定石．ついつい置いてしまう

• ↓更に手癖で置いてしまう．合体には使いやすいが，意味がない．おそらく7連鎖は打てない

• ↓緑からの順でも黄色からの順でも可能．おそらく最善手．ゾロ受けも多く，色の偏りにも強い．

• ↓緑は癖で置いてしまったが，黄色の置き方をとっさに変えたパターン．元よりは良い

• ↓良さそうに見えるが，黄色から繋げようとするとちぎりが必要になる場合が多い．

例から学ぶこと

• 緑を12に寝かせた手では，緑が消えた後，段差が1列目に生じるのを意識している
  • これは"凹の形になるよう組むとフィールド全体を使える"という経験則がおそらくの原因
  • （2~5列目のいずれかが極端に高くなると大連鎖を狙いにくい）
• これでは緑の置き場所が一つに絞られてしまう

• また，緑が消えた後，1列目の段差を使い2列目につなげる他につなげる方法がない

  • 端に好きな色を置くのは難しい

• 一方で，緑を2に立てた手では，緑を消すための置き場所が3箇所ある

• さらに段差が2列目に生じるため，3列目，1列目のどちらへも繋げられる

まとめ

以上から

• 土台手順の癖で伸ばしを行うと損をする

また，伸ばし手順では

• ぷよを消すための箇所が複数生じるように置くとよい
• 連鎖尾の段差は1列目に起こすより2列目に起こす方がよい

と予想する

おわり