目的

Atcoderで上を目指すべく頑張っている中でABC224を解いたので、解説してみる
- pypy7.3を使って解いている

A問題

考察

問題文通りに解けば良い

実装

S = input()

if S[-2]+S[-1] == "er":
    print("er")
else:
    print("ist")

結果

無事に解けた

B問題

atcoder.jp

考察

問題文通りに解けば良い
- H,W <= 50 なので4重ループでも解くことができる

実装

import sys

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]


for i1 in range(H-1):
    for j1 in range(W-1):
        for i2 in range(i1+1, H):
            for j2 in range(j1+1, W):
                if A[i1][j1]+A[i2][j2] > A[i2][j1] + A[i1][j2]:
                    print("No")
                    sys.exit()

print("Yes")

結果

無事に解けた

C問題

atcoder.jp

考察

割り算による誤差で解けず、焦って時間を使って、結果Cも解けず・・・

N <= 300 なので、3点を nC3 で探索しても間に合いそう
- (300299298) / 6 なので
3角形の成立条件を考えて、計算したが sample でも答えが合わず・・・

methodology.site

3点が1直線上になっている場合を考える
- X,Y <= 10⁹ なので割り算すると誤差が出る
- Decimalを利用しても誤差が出てしまう

$ cat c.py
import decimal
from decimal import Decimal
from itertools import combinations

N = int(input())
P = []

for _ in range(N):
    X, Y = map(Decimal, input().split())
    P.append((X, Y))

ans = 0
for p1, p2, p3 in combinations(P, 3):
    p1_x, p1_y = p1[0], p1[1]
    p2_x, p2_y = p2[0], p2[1]
    p3_x, p3_y = p3[0], p3[1]
    if p2_x-p1_x == Decimal("0") or p3_x-p1_x == Decimal("0"):
        continue
    a1, a2 = (p2_y-p1_y)/(p2_x-p1_x), (p3_y-p1_y)/(p3_x-p1_x)
    if a1 == a2:
        continue
    ans += 1
    # s = abs((p2_x-p1_x)*(p3_y-p1_y) - (p3_x-p1_x)*(p2_y-p1_y))/2
    # if s > 0:
    #     ans += 1

print(ans)

$ python c.py
20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0
1115

今回外積を用いて割り算せずに面積を求め考える

面積が0以外の場合を数え上げる

imagingsolution.net

実装

from itertools import combinations

N = int(input())
P = []

for _ in range(N):
    X, Y = map(int, input().split())
    P.append((X, Y))

ans = 0
for p1, p2, p3 in combinations(P, 3):
    p1_x, p1_y = p1[0], p1[1]
    p2_x, p2_y = p2[0], p2[1]
    p3_x, p3_y = p3[0], p3[1]
    s = abs((p2_x-p1_x)*(p3_y-p1_y) - (p3_x-p1_x)*(p2_y-p1_y))/2
    if s > 0:
        ans += 1

print(ans)

結果

無事に解けた

D問題

atcoder.jp

考察

水色diffでチャレンジ問題であるが、解説見ながら解いた

9個の頂点と、8個のコマを動かす
- 全部で9! = 362880通りなので全文探索で考える
問題はどうやって全文探索を実現するか？
- その上で、ゴール(駒j が頂点j にある状態)までの最短経路を考える必要がある
どのように実装するかを考える
1. 駒がどの頂点にあるかをどのように表現(=駒がどの頂点にある状態なのかをどのようなデータ構造で保持する)するか？
  - 1つは駒がない状況になる
2. 1.の状態の遷移させ、ゴールまでの経路の距離(= 初期状態から何回駒を動かしたか？)をどのように計算するか？
  - BFSやDFSをすれば良さそう
1.に関して
- stringで表現する(9は駒がないということにする) -> 123456789
  - 左から何文字目(=index number) にあるかで、頂点を表現する
  - pythonのstringはlistと同様に0-indexで表現できる
- 駒の情報を文字(ex. 1) で表現する
  - ex. 123456789 -> 駒j が頂点j にある状態を表現している
2.に関して
- 初期状態から、駒がない箇所に、何かの駒を移動させることを考える
  - これを距離1 と考える
  - 頂点をつなぐ辺は条件で与えられるので、9がある頂点と辺でつながる頂点にある駒をひたすら入れ替えていく
- 距離は状態を key とする dictで表現し、更新していく
  - { "321456789": 5 } のように保持する
- 今回はBFSで、初期状態から都度状態を遷移させ、それぞれの状態の距離を記録していく
  - ゴールに途中でたどり着けば break する
  - BFSで遷移し切ったが、距離を保持する dictにゴールを表す状態のkeyがなければ、遷移不可能となる

f:id:kazu_0716:20211026020123p:plain — ABC224 Dメモ

dictのinは平均計算量がO(1)

既に遷移した経路であればdictにkeyがあるので、それを都度調べるのが重いと思ったが、なんとかなった
- listでは O(n) となって TLE してしまう

wiki.python.org

実装

from collections import deque

M = int(input())
edge = [[] for _ in range(9)]
for _ in range(M):
    u, v = map(int, input().split())
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)
P = list(map(int, input().split()))
GOAL = "123456789"
EMPTY = "9"

tmp = [EMPTY]*9
for i, e in enumerate(P):
    tmp[e-1] = str(i+1)
ini = "".join(tmp)
queue = deque([ini])
dist = {ini: 0}

while queue:
    cur = queue.popleft()
    if cur == GOAL:
        break
    dst = cur.index(EMPTY)
    for src in edge[dst]:
        tmp = list(cur)
        tmp[dst], tmp[src] = cur[src], EMPTY
        nxt = "".join(tmp)
        if nxt in dist:
            continue
        dist[nxt] = dist[cur] + 1
        queue.append(nxt)

if GOAL in dist:
    print(dist[GOAL])
else:
    print(-1)

結果

無事に解けた

まとめ

また、Cを落としてしまい、rateを下げてしまった・・・
- まだまだ穴があるなーと思うのと、ハマったところから抜け出せない自力のなさを感じた

f:id:kazu_0716:20211026020451p:plain — ABC224 結果

ABCのD埋めは、ABC126(6問体制開始)まで遡り、だいたい終わってきた
- が、いまだにDはほとんど解けないし、たまにCでもコケたりする・・・
- 非常にモチベーションを保つのが辛い時期にある
といっても腐ってもしょうがないので、1日1ACを続けていく
- プログラミング未経験から、2ヶ月で緑になる人とか見るとすごいと思う
  - 業務経験も数年あってこれな自分なので・・・
- リアルに参戦記録をつけ続けてるので、これはこれで価値があり、いつか自分が緑になった時に「こうすれば、控えめにいっても緑になれる」と言えそうなコンテンツは作れそう
  - なんとなくだが、大多数は自分のような人間で、なおかつ大体途中で諦めてしまうと思うので、そういった人の助けになるコンテンツになればいいなと思う

絶対、まずは入緑して、緑になるためはブログ書いてやるぞ！

今日も1日1AC こういう式変形系の問題は得意な気がする
AtCoder Beginner Contest 133 https://t.co/02WR7gaIaB
— オ-℃ (@kazu_kun0716) 2021年10月23日

EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder-ABC224をpythonで解いてみた

目的

A問題

考察

実装

結果

B問題

考察

実装

結果

C問題

考察

実装

結果

D問題

考察

実装

結果

まとめ