ハチイチ裏二ダブ

ハチイチ裏二ダブとは

本線の方向（順方向）から暴発を利用して作成する二連鎖ダブルに対して，裏方向から発火するので裏二ダブ． これがハチイチを利用したものだとハチイチ裏二ダブとなる． 今勝手に作った．今生まれた．

相手の虚を衝く勝利をもたらし，仮に負けても構えていたことを悟らせない． 連戦では狂ったマルチでいかに相手にプレッシャーをかけるか，いかに実力を低く見積もらせるかが重要になる． よってハチイチ裏二ダブは最強．たぶん．

以下，思いつく範囲のハチイチ裏二ダブを載せる．

ハチイチ裏二ダブ

もっとも有名．ようかんさんがよく使っていた． 逆に言うとバレやすい．第二折り返しにどうぞ．

第二折り返しでも狙えるし，折り返し上部にも作ることができる． 狙いやすい割にあまりメジャーではない．よって強い．

先ほどの形の亜種． 土台をうまく使いたい．

順方向のハチイチ2ダブは有名だが，裏から使っている人はあまりいない． 凝視で気づける相手はほとんどいない．よって強い． でも自陣にあっても気づきづらい．意識意識．

先ほどの形の亜種．

なかなか使う機会がない．いや，ツモが偏った時に真ん中に作ることがあるかも．

順方向からもハチイチ二ダブが見えている．意外と強いかもしれない．

先ほどの形の亜種．

盤石の構えが見えているが，構え切る前に発火することで虚を衝く．

先ほどの形の亜種． 青が間に挟まれているのが見づらさを増している．

ネタ切れ感が強くなってきた．合体の帳尻を合わせようとすると折り返し上部にこの形を築くことがあるかもしれないし，ないかもしれない．

ネタ切れ．新GTRでの第2折り返しと見せかけて即発火． 合体が来ると勝手に思い込んでいる相手は死ぬ．

まとめ

順とか裏とか，区別する必要ってなんだろうね？（自問自答）

ABC038

問題元　→　

abc038.contest.atcoder.jp

A - お茶

概要

末尾がTか判定しろ．

解法

やるだけ．

print("YES" if input()[-1] == "T" else "NO")

B - ディスプレイ

概要

ディスプレイが2枚ある． 片方はH_1 x W_1の大きさで，もう片方はH_2 x W_2の大きさ． ディスプレイは90度回転できる． 高さを合わせることはできるか？

解法

総当りを行う． 関数を作るのがお決まりだが，Pythonならfor-else構文でぱぱっと書ける．

今回はディスプレイ2枚で固定だったが，ディスプレイがN枚の時に最大何枚高さを合わせられる？ と問われた場合にはどうすればいいのかがわからない． HとWが小さければDPでいけるが，もっと良い方法がありそうで気が気でない．

追記：何言ってるんだこいつ．酔っていたかもしれない．前から舐めていけば終わり．O(n)．

from itertools import product
for n, m in product(map(int, input().split()), map(int, input().split())):
    if n == m:
        print("YES")
        break
else:
    print("NO")

C - 単調増加

概要

数列が与えられる．単調増加な部分数列の数を求めよ．

解法

全てを数え上げていると間に合わなくなることはすぐにわかる．

長さNの単調増加な数列には(N+1) * N / 2個の単調増加な部分数列が含まれる． この性質を利用すればすべてを数え上げる必要がなくなり，通る．

変数名関数名が悪すぎて怒られそうだなぁ...と思いながら書いていた． 「変数名関数名に使える単語帳」のようなものが欲しい．

def f(seq, idx):    
    for i, j in zip(range(idx, len(seq)), range(idx+1, len(seq))):
        if seq[i] >= seq[j]:
            return j
    return len(seq)

def g(seq):
    idx = 0
    ret = []
    while idx < len(seq):
        ret.append((idx, f(seq, idx),))
        idx = ret[-1][-1]
    return ret

def h(l, r):
    n = r - l + 1
    return n * (n - 1) // 2


N = int(input())
a = list(map(int, input().split()))
print(sum(h(l, r) for l, r in g(a)))

D - プレゼント

概要

H x W の大きさの箱がN個ある． 最大でいくつの箱を入れ子にできるか？

解法

漸化式は次のようになる．

DP[h][w] = max(DP[h-1][w-1], ..., DP[i][j], .. DP[1][1]) + 1

あとはhの小さい順にソートして漸化式を埋めていく．(これでDAGになる） maxについてはRangeMaximumQueryをSegmentTreeで実装すればO(logN)．

「大丈夫でしょ？w」と思いPythonで書き，通らないことを確認してからC++で書き直した．随分時間をロスしてしまった． 計算量的にはO(NlogN)と十分そうだが，SegmentTreeのようなリストへのアクセスが頻繁に起こるデータ構造はPythonでは相当遅くなる．

コンテスト中は「あっ，LISだ」とならなかった．反省．

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// RMQ
template<class T>
struct SegmentTree {
    int n;
    vector<T> dat;
    SegmentTree(int n_ = 0) : n(n_){
        n = 1;
        while(n < n_) n <<= 1;
        dat.resize(n*2, 0);
    }
    T query(int v, int w, int l, int r){
        if(r <= l || w == 0) return 0;
        if(r - l == w) return dat[v];
        T res = 0;
        res = std::max(res, query(v*2, w/2, l, min(r, w/2)));
        res = std::max(res, query(v*2+1, w/2, max(0, l-w/2), r-w/2));
        return res;
    }
    void update(int i, T x){
        i += n;
        dat[i] = x;
        while(i != 1){
          dat[i>>1] = std::max(dat[i], dat[i^1]);
            i /= 2;
        }
    }
    T query(int l, int r){
        return query(1,n,l,r);
    }
    size_t size() const {
        return n;
    }
};

int main(){
  int N;
  cin >> N;
  vector<pair<int, int> > HW(N);
  for(int i = 0; i < N; ++i){
    cin >> HW[i].first >> HW[i].second;
  }
  sort(HW.begin(), HW.end());
  SegmentTree<int> rmq(100001);
  int l = 0, r = 0;
  int ans = 1;
  while(l < HW.size()){
    while(r < HW.size() && HW[l].first == HW[r].first){
      ++r;
    }
    int n = r - l;
    vector<int> indices(n), values(n);
    for(int i = 0; i < n; ++i){
      int v = rmq.query(0, HW[i+l].second);
      indices[i] = HW[i+l].second;
      values[i] = v + 1;
    }
    for(int i = 0; i < n; ++i){
      rmq.update(indices[i], values[i]);
      ans = std::max(ans, values[i]);
    }
    l = r;
  }
  cout << ans << endl;
  return 0;
}

class SegmentTree(object):
  
    def __init__(self, size, op=min, init=float("inf")):
        self.size = 1
        self.op = op
        self.init = init
        while self.size < size:
            self.size *= 2
        self.data = [init] * (self.size*2+2)
  
    def update(self, idx, value):
        k = idx + self.size - 1
        self.data[k] = value
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self.op(self.data[k*2+1], self.data[k*2+2])
  
    def find(self, start, end):
        def query(k, left, right):
            if right <= start or end <= left:
                return self.init
            if start <= left and right <= end:
                return self.data[k]
            vl = query(k*2+1, left, (left+right)//2)
            vr = query(k*2+2, (left+right)//2, right)
            return self.op(vl, vr)
        return query(0, 0, self.size)

def compress(arr):
    dic = dict(zip(sorted(set(arr)), range(len(arr))))
    return [dic[v] for v in arr]

if __name__ == "__main__":
    N = int(input())
    H, W = [], []
    for _ in range(N):
        h, w = list(map(int, input().split()))
        H.append(h)
        W.append(w)
    H = compress(H)
    W = compress(W)
    HW = list(zip(H, W))
    HW.sort()
    rmq = SegmentTree(max(W)+1, max, 0)
    ans = 1
    l, r = 0, 0
    while l < len(HW):
        while r < len(HW) and HW[l][0] == HW[r][0]:
            r += 1
        tmp = []
        for h, w in HW[l:r]:
            tmp.append((w, rmq.find(0, w)+1))
        for i, v in tmp:
            rmq.update(i, v)
            ans = max(ans, v)
        l = r
    print(ans)

ABC036

問題元　→　

abc036.contest.atcoder.jp

A - お茶

概要

1箱にA本の商品が入っている．B本手に入れるには何箱買えば良いか出力しろ．

解法

剰余が0でなければ+1すれば良い．

A, B = list(map(int, input().split()))
print(B // A + min(1, B % A))

B - 回転

概要

N * Nの文字列を時計回りに90度回転させて出力しろ．

解法

zipとunpackingを使うことで行列を転置させることができる． これを列について反転させる（？）ことで求める「時計回りに90度」となる．

回転を考慮した重複の除去を行う時なんかに使う．

N = int(input())
S = [input() for _ in range(N)]
print(*["".join(s[::-1]) for s in zip(*S)], sep="\n")

C - 座圧

概要

1次元の配列に対して座標圧縮を行い，圧縮後の配列の値を出力しろ．

解法

正しくマッピングすれば，大小関係も守られる．

リーダブルコードだかに似た問題があった気がする．（圧縮じゃなくてuniqueだけだったかも？） 方法は色々あると思うけど，自分としてはこのコードがベストかなぁ？

N = int(input())
a = [int(input()) for i in range(N)]
dic = dict(zip(sorted(set(a)), range(N)))
print(*list(map(lambda x: dic[x], a)), sep="\n")

D - 塗り絵

概要

N個のノードがあり，N-1個の辺があり連結である． ノードは黒色か白色で塗ることができる． ただし，辺の両端がどちらも黒色であってはならない． 何通りの塗り方があるか出力しろ．

解法

要するに木．解は膨大なものになり愚直な方法では間に合わない．

こういった問題は動的計画法が有効な場合が多い．という訳で，DAGを構成するために逆算していく．

あるノードを新たにくっつけた時に答えがどう変化するかを考える． 単純に2倍になるだろうか？もちろんそうはいかない． くっ付ける先のノード（隣接するノード）全てが必ず白色となる場合を除き，いずれかが黒色である場合を考慮しなければならない． 逆に言えば隣接するノード以降は考えなくても良いし，この二つの状況だけを考えれば良い．

答えのために持つべき情報も，DAGも見えた．あとはコードに落とすだけ．

解説を見ると，この手のDPを木DPというらしい． 「tree dp tutorial」でググったら良さげなサイトが見つかった

codeforces.com

そのうち やる．

MOD = 10 ** 9 + 7
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
q = [0]
top = 0
visited = [False] * N
visited[0] = True
while top < len(q):
    node = q[top]
    top += 1
    for n in edges[node]:
        if visited[n]:
            continue
        visited[n] = True
        q.append(n)
white = [1] * N
both = [1] * N  
for node in reversed(q):    
    both[node] = (both[node] + white[node]) % MOD
    for par in edges[node]:
        white[par] = (white[par] * both[node]) % MOD
        both[par] = (both[par] * white[node]) % MOD
print(both[0])

ABC037

問題元

abc037.contest.atcoder.jp

A - 饅頭

概要

A円の饅頭とB円の饅頭がある． C円持っている時，最大でいくつの饅頭を買えるか．

解法

価値が同じ，かつ，いくつでも買えるので安い方をめいいっぱい買えば良い．

買える個数に上限ができ，価値がバラバラとなったら，総当りもしくは動的計画法を使うことになる．

A, B, C = list(map(int, input().split()))
print(C // min(A, B))

B - 編集

概要

大きさNの配列が与えられた後，ある区間全てをTに更新するクエリがQ個次々と与えられる． 最終的な配列の値を出力しろ．

解法

NとQが小さいのでO(NQ)で愚直に実装すれば良い．

Nが大きい場合，更新する値と更新時間（？）をもたせたSegmentTreeを実装すればO(Qlog(N)+N)かな？

N, Q = list(map(int, input().split()))
ans = [0] * N
for _ in range(Q):
    L, R, T = list(map(int, input().split()))
    for i in range(L-1, R):
        ans[i] = T
print(*ans, sep="\n")
        

C - 総和

概要

長さNの数列が与えられる． この数列の長さKの連続する部分数列の総和を出力しろ．

解法

愚直にこなすとO(N²)で間に合わない．

真っ先に思い浮かぶのはSegmentTree．つまり，愚直な手法では部分列の和を求めるのに一々インデックスから引いて値を確認しているが，これをlogN個の区間の和の値を見るだけで済ませよう，という考え．

SegmentTreeを使えばO(NlogN)．おそらく間に合う．

先頭がiから始まる区間の和をsumとすると，先頭がi+1から始まる区間の和はsum-arr[i]+arr[i+K]． この関係を利用すると数列を先頭からなめていくだけで済む．O(N)．

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = tmp = sum(A[:K])
for i in range(N-K):
    tmp = -A[i] + tmp + A[i+K]
    ans += tmp
print(ans)

D - 経路

概要

H*Wマスのフィールドそれぞれに数字が振られている．
上下左右数字の小さい方へは移動ができる．
スタート地点は好きに選んで良い．考えられる全ての経路の数を出力しろ．

解法

経路の数が膨大なものになることは容易に想像出来る．経路一つ一つをなぞって行っては到底間に合わない．

こういった場合は動的計画法が有効な場合が多い．というより，経路の総和を求める問題はその典型． つまり，ある地点へ到達する経路の数を求めるには，その地点の丁度一つ前の地点へ到達する経路の数が分かれば十分という性質を利用する．

動的計画法については田山さんの記事が非常に参考になる．

d.hatena.ne.jp

（部分問題の解を求めることで，次の問題の解を求め，最終的な解へ膨らませていく訳だが，その為にまずDAGを意識するべし．というイメージ．）

動的計画法を利用したコードを書く場合，簡単にでも漸化式をメモをしておくと楽に済む． ICPC形式の場合，漸化式の形式で相手に渡すと伝わりやすいため2度美味しい．

ボトムアップに求める場合，順序を決めるのにソートする必要があり計算量 O( ( W * H ) log ( W * H ) )． （実はこれだとPythonでは通らない．ひどい罠だ）

トップダウンに求める場合，計算量 O(W * H)．
（速度がギリギリだったため，Python2かつPyPyを利用している）

import sys
sys.setrecursionlimit(500000)
MOD = 10 ** 9 + 7
H, W = list(map(int, raw_input().split()))
a = [list(map(int, raw_input().split())) for _ in range(H)]
table = [[0] * W for _ in range(H)]
def dfs(x, y, v):
    if a[x][y] >= v:
        return 0
    if table[x][y] > 0:
        return table[x][y]
    ret = 1
    for dx, dy in zip((0, 0, 1, -1), (1, -1, 0, 0)):
        nx, ny = x + dx, y + dy
        if not(0 <= nx < H and 0 <= ny < W):
            continue
        ret = (ret + dfs(nx, ny, a[x][y])) % MOD
    table[x][y] = ret
    return ret
ans = 0
for x in range(H):
    for y in range(W):
        ans = (ans + dfs(x, y, a[x][y]+1)) % MOD
print(and)

ボトムアップ型だとこんな感じ．

from itertools import product
from array import array
MOD = 10 ** 9 + 7
H, W = list(map(int, input().split()))
a = [array("L", map(int, input().split())) for _ in range(H)]
q = list(product(range(H), range(W)))
q.sort(key=lambda x: a[x[0]][x[1]])
table = [array("L", [1] * W) for _ in range(H)]
for x, y in q:
    for dx, dy in zip((0, 0, 1, -1), (1, -1, 0, 0)):
        nx, ny = x + dx, y + dy
        if not(0 <= nx < H and 0 <= ny < W):
            continue
        if a[x][y] >= a[nx][ny]:
            continue
        table[nx][ny] = (table[nx][ny] + table[x][y]) % MOD
print(sum(sum(t) % MOD for t in table) % MOD)

今回とは逆に，呼び出しやら何やらのコストでトップダウン型だと通らない問題も存在するのが非常にタチが悪い． また，配るDPにするか貰うDPにするかで速度が変わる（定数部分が変わる）場合もある． トポロジカル順序にソートするために2要素，3要素を比較しないとならない場合もあるだろう． まだ見たことはないけど，ステートマシーンを回すようなDPもあるらしい．奥が深い．

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)

概要

解法

ARC048

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

A - タブの開きすぎ

概要

ブラウザのタブを開ける，閉じるのどちらかを順序に沿って回行う．
ただし，個以上のタブが開くとブラウザがクラッシュしてタブが1個の状態に戻る．
ブラウザがクラッシュした回数を求めよ．

解法

この手の問題はステートマシーンを思い浮かべながら，reduceを使って書くと楽なイメージ．
（再帰で書くとスタックオーバーフローで死ぬ）
python3で引数にtupleを入れる構文(Tuple Parameter Unpacking?)が廃止されたことを初めて知った．

www.python.org

reduceもfunctoolsに隔離されるし，lambdaを廃止する話もあったらしいし，極端だなぁ

from functools import reduce
N, L = list(map(int, input().split()))
def solve(tab_crash, c): 
    tab, crash = tab_crash
    if c == "+":
        tab = (tab % L) + 1
        return (tab, crash + (1 if tab == 1 else 0), )
    else:
        return (tab-1, crash)
print(reduce(solve, input(), (1, 0))[1])

B - 同一円周上

概要

2次元平面上に個の点が存在する．各点は格子点上に存在している．
全ての点からのマンハッタン距離が等しい，かつ，格子点上に存在する点を求めろ．

解法

なぜこれがB問題なのか...
全ての点と求める点Pのマンハッタン距離が等しいということは，点Pを中心(?)とした菱形の辺上に全ての点が並んでいるということ．
この菱形の候補を考え，点P（菱形の中心）の候補を求め，実際に条件を満たしているか判定すれば良い．
点を全て90度回転させる（+2倍に伸ばす）とわかりやすくなる．

from itertools import product
def transform(pos): # (rotate 90) + 2x
    x, y = pos
    return (x + y, -x + y)

def origin(pos):
    x, y = pos
    return ((x - y) // 2, (x + y) // 2)

def dist(pos1, pos2):
    return sum(abs(a - b) for a, b in zip(pos1, pos2))

def get(positions):
    minx = miny = float("inf")
    maxx = maxy = -float("inf")
    for x, y in positions:
        minx = min(minx, x)
        miny = min(miny, y)
        maxx = max(maxx, x)
        maxy = max(maxy, y)
    return minx, miny, maxx, maxy

def solve(positions):
    t_positions = map(transform, positions)
    minx, miny, maxx, maxy = get(t_positions)
    D = max((maxx - minx), (maxy - miny)) // 2
    P = list(product((minx + D, maxx - D), (miny + D, maxy - D)))
    for ppos in map(origin, P):
        if all(dist(pos, ppos) == D for pos in positions):
            return ppos
    raise

N = int(input())
positions = [tuple(map(int, input().split())) for _ in range(N)]
print(*solve(positions))

C - N!÷K番目の単語

概要

}]の数字を並べ替えたものを個用意する．
これを辞書順に並べたとき，番目を求めよ.

解法

部分点しか取れてない．なぜこれがC問題なのか...
このセットは全体的に難易度が高いように思う．

X番目の数列を求めるとして，この数列の先頭1番目はとなる.
すでに使った数字を考慮しながら，これを再帰的に繰り返していけば良い．
（コードでは数列の先頭番目が残っている数字の内何番目に小さいかを求めた後，実際の数列に戻している）

from itertools import compress
from functools import reduce
from math import factorial

def calc(x_order, i):
    x, order = x_order
    order.append(x // factorial(i))
    x %= factorial(i)
    return x, order

def get(order_unused_ans, i):
    order, unused, ans = order_unused_ans
    idx = order[i]
    for n in compress(range(len(unused)), unused):
        if idx == 0:
            ans.append(n)
            unused[n] = 0
            break
        idx -= 1
    return order, unused, ans


if __name__ == "__main__":
    N, K = list(map(int, input().split()))
    order = reduce(calc, range(N-1, -1, -1), (factorial(N) // K - 1, []))[1]
    ans = reduce(get, range(N), (order, [0] + [1] * N, []))[2]
    print(*ans, sep="\n")

概要

解法

ARC048

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

A - 階段の下

概要

地上[tex: {10⁹}]階，地下[tex: {10⁹}]階を持つビルがある．ただし0階は存在しない．
階から階への移動には，階段を何階分登る必要があるか？

解法

ソートしてから場合分け． 0-indexedの偉大さがわかる（？）

a, b = list(sorted(map(int, input().split())))
if a * b > 0:
    print(abs(b - a))
else:
    print(b - a - 1)

B - AtCoderでじゃんけんを

概要

N人集まって総当りでジャンケンを行う．
ただし，参加者はそれぞれレートを持っており，相手よりレートが高い場合は問答無用で勝ちとなる．
また，総当り中の手は全て固定．

解法

いわゆるTopCoderジャンケン．（元ネタを貼ろうと思ったが見つからなかった...）
愚直に総当りをすると[tex: {O(N²)}]となり間に合わない．
レートでのソート+総当り中の手が全て固定なことをを利用すると．
...のはずなのだが，通らない．辛い．

他の言語であれば通るのでよしとする（？）
おそらく，リストの各要素へのアクセスが（言語として）遅いことがネックとなっていると予想している．

indexで頑張るよりもクラスなりを作って名前でアクセスする方が頭がこんがらなくて良い．
（といつも思うのだが，本番だと少しの時間をケチってindexでのアクセスで頑張り，結局バグって後悔することが多い）

from collections import namedtuple
from itertools import islice
Player = namedtuple("Player", ["rate", "hand", "id"])
class Result:
    def __init__(self):
        self.win = 0
        self.lose = 0
        self.draw = 0

    def __str__(self):
        return "{} {} {}".format(self.win, self.lose, self.draw)

N = int(input())
players = []
for i in range(N):
    r, h = list(map(int, input().split()))
    players.append(Player(r, h-1, i))
players.sort(reverse=True)
results = [Result() for _ in range(N)]
start, end = 0, None
while start < len(players):
    end = start + 1
    while end < len(players) and players[end].rate == players[start].rate:
        end += 1
    rps = [0] * 3
    for p in islice(players, start, end):
        rps[p.hand] += 1
    for p in islice(players, start, end):
        results[p.id].draw = rps[p.hand] - 1
        results[p.id].win = rps[(p.hand + 1) % 3] + N - end
        results[p.id].lose = rps[(p.hand + 2) % 3] + start
    start = end
print(*results, sep="\n")

C - 足の多い高橋君

概要

解法

from fractions import gcd
from functools import reduce
from math import ceil
MOD = 10 ** 9 + 7
N = int(input())
L = list(sorted(set([int(input()) for _ in range(N)]), reverse=True))
ml = L.pop()
cycle = reduce(gcd, map(lambda x: x-ml, L)) if L else 0
print(pow(2, ml+int(ceil(cycle/2)), MOD))

D - たこ焼き屋とQ人の高橋君

概要

解法