ABC184バチャ

A - Determinant

概要

行列が与えられ、行列式を求める

カテゴリ

算数（四則演算）

考察

入力全て整数で、桁も小さいので特に型などは気にしなくていい
a*d-b*c

コード

#!/usr/bin/env python3
a, b = map(int, input().split())
c, d = map(int, input().split())
print(a * d - b * c)

B - Quizzes

概要

最初の持ち点がNでクイズの正解、不正解履歴が文字列で与えられる。
持ち点は正解、不正解に応じて変動し、oなら+1,xなら-1をする。（ただし、持ち点が負になることはない）
最終的な点数を答えよ

カテゴリ

ゲーム（そのままルールを実装）

考察

ループで文字列の長さ分を回す

コード

#!/usr/bin/env python3
n, x = map(int, input().split())
s = input()
cur_point = x
for i in s:
    if cur_point == 0 and i == "x":
        pass
    elif i == "x":
        cur_point -= 1
    else:
        cur_point += 1

print(cur_point)

C - Super Ryuma

概要

無限に広がる二次元グリッド上の位置(r1,c1)にコマがあり、それを(r2,c2)に動かすための最小手順を答えよ。
ただし、一回の移動で(a,b)にいるコマは以下の条件のどちらかを満たす場所(c,d)に動かせる。

　A:ユークリッド距離が３以下
　B:対角の位置（将棋の角が移動できる場所）

カテゴリ

最短経路、グリッド

考察

可能な２つの動き（斜めと３マス以内の移動）を考えた時に、２つの動きの順番は関係ない。
つまり、A,A,B でたどり着くならばB,A,Aでも同じ場所にたどり着く。

そのため、Bの動きを行う回数を固定してk回行うとすると、Aの動きを何回行えば終了時の位置とゴール位置のユークリッド距離を3*k 以内にできるか、という問題になる。

ただし、これではk に対してO(10**9)かかるので、明らかに間に合わない。
どういう時にAの動きがBよりも優位になるかを考えると、移動後にゴールとのユークリッド距離が3よりも減っている時、ということになる。

ここで、Aの動きには向きが２つあり（右斜と左斜）、その２つを組み合わせることで一回の動きではユークリッド距離が縮まらない場合にも2回トータルすると大きく縮められることがわかる（例として、スタートとゴール位置のx座標が同じ時など）

さらに、A,Bの動きの順番が関係ないことを考えると、Aの２つの動きはそれぞれ高々一回でよくて、ゴール地点から垂線を引いてそれにぶつかるまでAの動きをすればAの動きだけで最も近づくことができる。
それを行った時の距離は1か0なので手数は3,2,1,0のいずれかになる

実装

手数が0,1,2,3になる条件を羅列していって、手数を確定させる（簡単な少ない手数の条件から記述して3はその余事象とする）

移動A二回でゴールにつく条件は必ずどちらの動作もa-c,b-dの差が偶数変化するので、abs(a-c) + abs(b-d) % 2 == 0 で、
A一回、B一回でゴールにつけるかの判定は、abs(abs(a - c) - abs(b - d)) <= 3　で行える（気づくのにだいぶ時間がかかった）

#!/usr/bin/env python3
a, b = map(int, input().split())
c, d = map(int, input().split())
if a == c and b == d:
    print(0)
elif abs(a - c) == abs(b - d) or abs(a - c) + abs(b - d) <= 3:
    print(1)
else:
    if (
        abs(a - c) + abs(b - d) <= 6
        or (abs(a - c) + abs(b - d)) % 2 == 0
        or abs(abs(a - c) - abs(b - d)) <= 3
    ):
        print(2)
    else:
        print(3)

D - increment of coins

概要

ゲームの期待値を求める

カテゴリ

ゲーム、期待値

考察

ゲームが終了するまでの手数の期待値を求める問題
余事象で考えられるか考えたが、無理なので、全状態を列挙する必要があると考える。
ただし、全てのpath(どれかが100枚になるまで）を考えると状態数が多くなりすぎるので、DPのように状態をまとめることを考える。(それぞれがx,y,z になる確率はx-1,y,z,とx,y-1,z , x,y,z-1から移動する確率の全ての和で計算できる）

計算量はO(10**6)(DPが10**6マスあって、それぞれの遷移がO(1)*3パス）なので、これで間に合う。

実装

期待値DPなのでゴールから埋めていく。
DP[ある状態] = (そこからゴールまでの期待値)　という形で漸化式を形成する

#!/usr/bin/env python3
# input
a, b, c = map(int, input().split())
dp = [[[0] * 103 for i in range(103)] for j in range(103)]
dp[a][b][c] = 1  # initialization
for i in range(1, 300 - a - b - c + 1):  # スタートからの距離
    for a_d in range(i + 1):  # aに割り当てる距離
        for b_d in range(i + 1 - a_d):
            c_d = i - a_d - b_d
            if (((a + a_d) == 100) + ((b + b_d) == 100) + ((c + c_d) == 100)) > 1:
                continue
            elif a + a_d > 100 or b + b_d > 100 or c + c_d > 100:
                continue
            else:
                if a + a_d > 0 and b + b_d < 100 and c + c_d < 100:
                    dp[a + a_d][b + b_d][c + c_d] += dp[a + a_d - 1][b + b_d][
                        c + c_d
                    ] * ((a + a_d - 1) / (a + b + c + i - 1))
                if b + b_d > 0 and a + a_d < 100 and c + c_d < 100:
                    dp[a + a_d][b + b_d][c + c_d] += dp[a + a_d][b + b_d - 1][
                        c + c_d
                    ] * ((b + b_d - 1) / (a + b + c + i - 1))
                if c + c_d > 0 and b + b_d < 100 and a + a_d < 100:
                    dp[a + a_d][b + b_d][c + c_d] += dp[a + a_d][b + b_d][
                        c + c_d - 1
                    ] * ((c + c_d - 1) / (a + b + c + i - 1))
# print(dp[99][99][99:], dp[100][99][98:], dp[99][100][98:])
ans = 0
for i in range(101):
    for j in range(101):
        for k in range(101):
            if i == 100 or j == 100 or k == 100:
                ans += dp[i][j][k] * (i + j + k - a - b - c)
print(ans)