.lazyload-placeholder { display: none; }

作成日 : 2021-10-24
更新日 : 2021-11-01
15 min readAtCoder

【備忘録】AtCoder Beginner Contest 224 A~D問題

AtCoder Beginner Contest 224のA~D問題に関して、問題文からContest中に考えたこと、解答等を備忘録としてまとめました。是非最後までご一読ください。

そもそもAtCoderとは?
「AtCoder Beginner Contest 224」
A -> Tires
B -> Mongeness
C -> Triangle?
D -> 8 Puzzle on Graph
参考文献

目次を開く⬇︎

執筆者 - おすすめの記事3選

この記事も読まれています

.lazyload-placeholder { display: none; }

【備忘録】AtCoder Beginner Contest 221 A~D問題

AtCoder Beginner Contest 221のA~D問題に関して、問題文からContest中に考えたこと、解...

この記事も読まれています

.lazyload-placeholder { display: none; }

【備忘録】AtCoder Beginner Contest 222 A~D問題

AtCoder Beginner Contest 222のA~D問題に関して、問題文からContest中に考えたこと、解...

この記事も読まれています

.lazyload-placeholder { display: none; }

【備忘録】AtCoder Beginner Contest 223 A~D問題

AtCoder Beginner Contest 223のA~D問題に関して、問題文からContest中に考えたこと、解...

そもそもAtCoderとは?

AtCoderを一言で表すと、オンラインで参加できるプログラミングコンテスト(競技プログラミング)サイトになります。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問に、いつでも挑戦出来ることが魅力です。

今回は 「AtCoder Beginner Contest 224」のプログラミングコンテストへ参加しました。

「AtCoder Beginner Contest 224」

コンテスト情報

コンテスト時間 : 100分
レーティング更新対象 : 0 - 1999

配点

問題	点数
A	100
B	200
C	300
D	400
E	500
F	500
G	600
H	600

ルール

コンテスト中に問題に正解すると点数を獲得できます。
順位は総合得点で決定します。
同点の場合は提出時間の早い人が上の順位になります。
誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは5分です。(ルールに関して詳しくみる)

このコンテストは「コンテスト中に提出された結果」だけで順位が決定します。

A -> Tires

問題文

末尾がerまたはistであるような文字列Sが与えられます。Sの末尾がerである場合はerを、istである場合はistを出力してください。

制約

2 ≤ ∣S∣ ≤ 20
Sは英小文字のみからなる。
Sの末尾はerまたはistである。

入力

入力は以下の形式で標準入力から与えられる。

1S

出力

答えを出力せよ。

本問題は、AtCoder株式会社で作成された、A - Tires問題を参照しております。

Contest中に考えたこと

文字列の末尾2文字を抽出する。
抽出した文字列がerならばerを返す。そうでなければ、istを返す。

解答

1# 標準入力を受け付ける。
2S = input()
3 
4lenS = len(S)
5
6# 文字列の末尾2文字を抽出する。
7# 抽出した文字列が`er`ならば`er`を返す。そうでなければ、`ist`を返す。
8# 「文字列の末尾2文字を抽出する」参考 : https://www.javadrive.jp/python/string/index11.html
9if S[lenS-2:lenS] == 'er':
10    print('er')
11else:
12    print('ist')

B -> Mongeness

問題文

縦H行、横W列のマス目があり、各マスには1つの整数が書かれています。上からi行目、左からj列目のマスに書かれている整数はAi, jです。

マス目が下記の条件を満たすかどうかを判定してください。

1 ≤ i1 < i2 ≤ Hおよび1 ≤ j1 < j2 ≤ Wを満たすすべての整数の組(i1, i2, j1, j2)について、Ai1, j1 + Ai2, j2 ≤ Ai2, j1 + Ai1, j2が成り立つ

制約

2 ≤ H, W ≤ 50
1 ≤ Ai, j ≤ 10の9乗
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

1H W
2A1,1 A1,2 ⋯ A1,W
3A2,1 A2,2 ⋯ A2,W
4⋮
5AH,1 AH,2 ⋯ AH,W

出力

マス目が問題文中の条件を満たす場合はYesと出力し、条件を満たさない場合はNoと出力せよ。

本問題は、AtCoder株式会社で作成された、B - Mongeness問題を参照しております。

Contest中に考えたこと

2 ≤ H, W ≤ 50なので、全探索して問題ないと判断する。
条件を満たすか確認するためのフラグを用意する。
愚直にA0, 0 + A1, 1 > A1, 0 + A0, 1の場合、A0, 1 + A1, 2 > A1, 1 + A0, 2の場合...と計算する。
Ai1, j1 + Ai2, j2 > Ai2, j1 + Ai1, j2の条件を満たす場合が見つかった時、フラグの値を変更してbreakする。
フラグの条件によってYes, Noを出し分ける。

解答

1# 標準入力を受け付ける。
2H, W = map(int, input().split())
3 
4A = []
5for _ in range(H):
6    A.append(list(map(int, input().split())))
7
8# 条件を満たすか確認するためのフラグを用意する。
9flag = False
10# 愚直にA0, 0 + A1, 1 > A1, 0 + A0, 1の場合、A0, 1 + A1, 2 > A1, 1 + A0, 2の場合...と計算する。
11for i in range(H):
12    for j in range(W):
13        # j + 1 >= W or i + 1 >= Hを満たす時、存在しない配列を参照することになるので、その場合は検証しないことにする。
14        if j + 1 >= W or i + 1 >= H:
15            continue
16 
17        # Ai1, j1 + Ai2, j2 > Ai2, j1 + Ai1, j2の条件を満たす場合が見つかった時、フラグの値を変更してbreakする。
18        if A[i][j] + A[i + 1][j + 1] > A[i + 1][j] + A[i][j + 1]:
19            flag = True
20            break
21 
22# フラグの条件によってYes, Noを出し分ける。
23if flag:
24    print('No')
25else:
26    print('Yes')

C -> Triangle?

問題文

xy平面上に1からNまでの番号が付いたN個の点があります。点iは座標(Xi, Yi)にあり、相異なる2点は異なる位置に存在します。

このN点から3点を選ぶとき、選ばれた3点を線分で結んだ図形が正の面積を持つ三角形になるような点の選び方の総数を求めてください。

制約

入力は全て整数である
3 ≤ N ≤ 300
−10の9乗 ≤ Xi, Yi ≤ 10の9乗
i ≠ jならば (Xi, Yi) ≠ (Xj, Yj)

入力

入力は以下の形式で標準入力から与えられる。

1N
2X1 Y1
3X2 Y2
4…
5XN YN

出力

答えを整数として出力せよ。

本問題は、AtCoder株式会社で作成された、C - Triangle?問題を参照しております。

Contest中に考えたこと

3点を選んで三角形ができない場合を考える。 ⏩ 3点を繋ぎ合わせると直線になる場合のみ、三角形ができない。
3点を繋ぎ合わせると直線になる ⏩ 原点からの傾きが等しいことを利用する。
1点は不要になるので、座標の平行移動に利用する。

解答

1N = int(input())
2
3position = []
4for _ in range(N):
5    x, y = map(int, input().split())
6    position.append((x, y))
7
8ans = 0
9for i in range(N):
10    for j in range(i + 1, N):
11        for k in range(j + 1, N):
12            x1, y1 = position[i]
13            x2, y2 = position[j]
14            x3, y3 = position[k]
15
16            # 1点は不要になるので、座標の平行移動に利用する。
17            x1 -= x3
18            y1 -= y3
19            # 1点は不要になるので、座標の平行移動に利用する。
20            x2 -= x3
21            y2 -= y3
22            
23            # 3点を繋ぎ合わせると直線になる ⏩ 原点からの傾きが等しいことを利用する。
24            # 傾き : (y - 0) = a(x - 0) → a = y / x
25            # (y1 - 0) / (x1 - 0) = (y2 - 0) / (x2 - 0) → y1 = (x1 * y2) / x2 → x2 * y1 = x1 * y2 → (x2 * y1) - (x1 * y2) = 0
26            if (x2 * y1) - (x1 * y2) != 0:
27                ans += 1
28
29print(ans)

D -> 8 Puzzle on Graph

問題文

高橋君は道端であるパズルを拾いました。このパズルは、9個の頂点とM本の辺からなる無向グラフ、および、8つのコマで構成されます。

グラフの9つの頂点はそれぞれ頂点1、頂点2、…、頂点9と呼ばれ、i = 1, 2, …, Mについて、i番目の辺は頂点uiと頂点viを結んでいます。

8つのコマはそれぞれコマ1、コマ2、…、コマ8と呼ばれ、j = 1, 2, …, 8について、コマjは頂点pjに置かれています。ここで、すべてのコマはそれぞれ異なる頂点に置かれていることが保証されます。コマが置かれていない「空の頂点」がただ一つ存在することに注意してください。

高橋君はこのパズルに対して下記の操作を好きな回数（0回でもよい）だけ行うことができます。

空の頂点に隣接する頂点に置かれたコマを1つ選び、選んだコマを空の頂点に移動する。

高橋君は上記の操作を繰り返して、このパズルを「完成」させようとしています。パズルは、下記の状態を満たしたときに完成となります。

j = 1, 2, …, 8について、コマjは頂点jに置かれている。

高橋君がパズルを完成させることが可能かどうかを判定し、可能な場合はそのために必要な操作回数の最小値を出力してください。

制約

0 ≤ M ≤ 36
1 ≤ ui, vi ≤ 9
与えられるグラフは多重辺、自己ループを持たない
1 ≤ pj ≤ 9
j ≠ j′ ⇒ pj ≠ pj′
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

1M
2u1 v1
3u2 v2
4⋮
5uM vM
6p1 p2 … p8

出力

高橋君がパズルを完成させることが可能な場合は、そのために必要な操作回数の最小値を出力せよ。高橋君がパズルを完成させることが不可能な場合は、−1を出力せよ。

本問題は、AtCoder株式会社で作成された、D - 8 Puzzle on Graph問題を参照しております。

Contest中に考えたこと

問題文を読んで、何もできませんでした。。

解答

1################################
2# <方針>
3# 9個の頂点に当てはまる、可能性のある数字(コマ)を全通り試して、答えを導き出す。
4# 可能性のある数字(コマ)を全通り試して、TLE(時間)に間に合うのか? ⏩　 大丈夫。
5# <全探索して問題ない理由>
6# 1~9の数字(コマ)の中で、p1, p2, p3, ...に属さないもの(空の頂点)をxと置く。3 x 3のパズルだと考えて、各数字(コマ)((p1, p2, p3, ...), x)を、3 x 3のパズルに当てはめる。
7# 3 x 3のパズルへ各数字(コマ)((p1, p2, p3, ...), x)が入る場合の数は9!。 ⏩ 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362880 ≒ 3 x 10の5乗なので問題ない。
8
9# 無効グラフの情報は、2次元配列で管理する。Trueの場合遷移可能、Falseの場合遷移不可能。
10# 場合の数の場合を、「数字の文字列」で管理する。数字の文字列の末尾の数字を、「空の頂点」とする。パズルの完成形を123456789にする。
11# 例) : 215634987の場合、7が空の頂点。319624578の場合、8が空の頂点。
12# ※ コメントを追記すると、TLEになりました。。コメントを全て消すと、ACできるのでご注意ください。🙇‍♂️
13################################
14
15# 標準入力を受けつける。
16M = int(input())
17
18# 無効グラフの情報を2次元配列で管理する。Trueの場合、遷移可能。Falseの場合、遷移不可能。
19edges = []
20# インデックスが0の箇所は利用しない。
21for _ in range(10):
22    edges.append([False] * 10)
23
24for _ in range(M):
25    u, v = map(int, input().split())
26    edges[u][v] = True
27    edges[v][u] = True
28
29p = list(input().split())
30for i in range(1, 10):
31    tmp = str(i)
32    # 空の頂点を探索して、末尾に数字として格納する。
33    if not tmp in p:
34        p.append(tmp)
35# 場合の数の場合を、「数字の文字列」とする。
36p = int(''.join(p))
37
38# 現在探索すべき、場合(数字の文字列)情報を格納する。
39current_vec = [p]
40# 場合(数字の文字列)と場合の数の情報を格納する。
41# p : 場合(数字の文字列), 0 : 場合の数
42dist = {p: 0}
43
44# 探索すべき場合(数字の文字列)情報がなくなるので、回し続ける。
45while len(current_vec) != 0:
46    # 次に探索すべき、場合(数字の文字列)情報を格納する。
47    next_vec = []
48    for p in current_vec:
49        now = list(str(p))
50        # 空の頂点の数字情報を格納する。
51        emptyNum = int(now[8])
52        for i in range(8):
53            pos = int(now[i])
54            # 空の頂点とある数字を元に、遷移できるか探索する。
55            if edges[pos][emptyNum]:
56                # 空の頂点と、遷移できる数字の入れ替えを行う。
57                tmp = now[i]
58                now[i] = now[8]
59                now[8] = tmp
60
61                next = int(''.join(now))
62                # 一度探索した場合(数字の文字列)を再度探索しない。
63                if not next in dist:
64                    # 次に探索すべき、場合(数字の文字列)情報を格納する。
65                    next_vec.append(next)
66                    # 場合(数字の文字列)が見つかった、探索数を記録する。
67                    dist[next] = dist[p] + 1
68
69                # 後続処理のため、復元する。
70                tmp = now[i]
71                now[i] = now[8]
72                now[8] = tmp
73    vec = next_vec
74
75# パズルの完成形を123456789にする。
76goal = 123456789
77if goal in dist:
78    print(dist[goal])
79else:
80    print(-1)