Ccmmutty logo
Commutty IT
・4 min read

ABC224 茶色コーダーが解けた所まで

アルゴリズムAtCoder競技プログラミング
https://picsum.photos/seed/d8f80934cc894665b25358042e66fc34/600/800

AtCoder Beginner Contest 224

https://atcoder.jp/contests/abc224
ABC224の問題を、本番で自分が解けた所までの解説です。
ちょっとサボってたので（言い訳）
1日1ABC分、4日間で取り戻したいと思います…。
今回は3完でした。ううむ、グラフ問題が弱い…。
A - Tires Difficulty: 6
https://atcoder.jp/contests/abc224/tasks/abc224_a

if文で条件分岐してあげる

  • 制約より、入力される文字列は末尾が「er」か「ist」のどちらか
    • 2文字と3文字の比較…ううん…面倒な感じ…？
      • 2文字見て、erならer。erじゃないならist。
      • 3文字見て、istならist。istじゃないならer。
        • どっちでもいけますね。

(確か)Twitterで見かけた、スマートだと思った解法

  • 末尾の1文字だけ比較する
    • 末尾がr : 後ろ2文字がer
    • 末尾がt : 後ろ3文字がist
python
# 入力
S = input()

# 最後1文字がrなら、er。そうでないならist。
if S[-1] == 'r':
    print('er')
else:
    print('ist')

B - Mongeness

Difficulty: 81
https://atcoder.jp/contests/abc224/tasks/abc224_b

問題を咀嚼する

  • 添字が多かったり数式だったりすると、脳が文章を理解する事に対してブレーキをかけてしまいます…。
  • 一旦自分でも分かる簡単な日本語に直してみる。
    • 縦H横Wの数字表から、1マスを選んだとき、（Ai1,j1 A_{i_1,j_1}、Aと呼ぶ)
      • 選んだマスより下の行&右の列に存在するマスから、2マス目を選ぶ(Ai2,j2A_{i_2,j_2}、Cと呼ぶ)
      • マスAを左上、マスCを右下とする長方形を描く。左下のマスをB、右上のマスをDと呼ぶ。
      • マスAの値 + マスCの値 ≤\leq マスBの値 + マスDの値
        • マスA、マスCの全組み合わせについて、この条件を満たす？

制約を見て考える

  • H,Wは最大でも50行50列…2500マス。
    • すべてのマス目同士の組み合わせを考えると、2500*2500=6250000
      • 6×1066 \times 10^6…全部しらみつぶしに数えたとしてもいけそう感ある

条件を満たす? or 満たさない?

  • すべてのマス目の組み合わせが条件を満たす場合：Yes
  • そうではない場合：No
    • 1つでも反例があればNo：反例が見つかればNo,見つからなければYes
python
# 入力
H, W = map(int, input().split())

# マス目は二次元配列で持つ
L = []
for i in range(H):
    L.append(list(map(int, input().split())))

# ループ部。愚直に全探索。
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):

                # 左辺、右辺別々に計算する
                left = L[i1][j1] + L[i2][j2]
                right = L[i2][j1] + L[i1][j2]

                # 反例が見つかればそこで終了
                if left > right:
                    print('No')
                    exit()
                    
# 反例が見つからなかった場合の出力
print('Yes')

C - Triangle?

Difficulty: 301 https://atcoder.jp/contests/abc224/tasks/abc224_c

図形問題

  • N点の中から3点を選んで線分でつないだときに、図形が正の面積を持つ三角形になるような点の選び方の総数を求める

3点を結んだ図形が正の面積を持つ三角形になる…？

  • 三角形が成立するための条件は色々あると思われます。
    • 一番長い辺
    • 2直線の傾き
      • 今回は2直線の傾きを使用します。
      • 選ばれた3点（A,B,C）のうち1点（A）を固定して…
        • ABの傾きとACの傾きが等しい＝A,B,Cが一直線上に並ぶ＝三角形が出来ない

計算速度について

  • 本番でもやらかしたのですが、Python3で提出するとTLEでした…もっと上手いこと短縮できたらAC通るのかもしれませんが、技術不足故…。
    • Pypyで出したらあっさりAC、ソース自体は間違えてない…筈…？
python
# 入力部
N = int(input())

L = []
for i in range(N):
    X, Y = map(int, input().split())
    L.append([X, Y])

# 答え初期値設定
ans = 0

# 全探索ループ
for a in range(N-2):
    for b in range(a+1, N-1):
        for c in range(b+1, N):
            
            # A点、B点、C点の絶対位置取得
            a_x, a_y = L[a]
            b_x, b_y = L[b]
            c_x, c_y = L[c]

            # A点から見た時の、B点、C点の相対的位置を計算
            AB = (b_x - a_x, b_y - a_y)
            AC = (c_x - a_x, c_y - a_y)

            # もし、直線ABと、直線ACの傾きが異なるなら、ans+=1
            if AB[0]*AC[1] != AC[0]*AB[1]:
                ans += 1
print(ans)

Discussion

コメントにはログインが必要です。