プログラムのお勉強メモ

プログラムの勉強メモです. Python, Rust, など.

ABC218_D(Rectangles)

問題

考えたこと

  • (x, y) の座標を与えられるのでその中から 4 つ選択して x 軸、y 軸の両方と並行な長方形を作成する。
  • 入力例を見る限り正方形でもいいっぽい。
  • 最初は次のようなロジックで検討。
    1. 座標を 1 つ取得する。
    2. 座標の x 軸と等しい y 軸の一覧を取得。
    3. y 軸の一覧から x 軸の一覧を取得。
    4. 座標の y 軸と等しい x 軸の一覧を取得。
    5. x 軸の一覧から y 軸の一覧を取得。
    6. これで 4 点取得できるので長方形が作成できるか判定する。
  • 複雑すぎて実装が面倒だったので、別の方法はないか考えた。

思いついた別の方法

  • 座標を 2 点取る。これを座標 A, 座標 B とする。
  • 座標 A = (xa, ya), 座標 B = (xb, yb) とすると長方形を作るためには (xa, yb) と (xb, yb) が無いと作れない。
  • また (xa, yb) (xb, yb) を作成するにあたり、斜めに線が引けないと長方形が作れない。そのため xa == xb or ya == yb の場合には読み飛ばす。
  • 計算量は  N^{2} でも十分に間に合う。
  • 座標を set で持てば その座標が存在するかは  N(1) のオーダーで取得可能。
  • 4 つの点で同じ長方形を見つけてしまうため最終的に答えを 4 で割ってやれば正解。

実装

N = int(input())
point = set()

for i in range(N):
    x, y = [int(x) for x in input().split()]
    point.add((x, y))

ans = 0
for x, y in point:
    for tx, ty in point:
        if x == tx or y == ty:
            continue

        if (x, ty) in point and (tx, y) in point:
            ans += 1

print(ans//4)

ABC219_D(Strange Lunchbox)

問題

考えたこと

  • 全探索は無理。弁当を食べる場合、食べない場合の 2 択で考えると最大で  2^{300} の計算量になってしまう。
  • ナップザック問題の応用で行けそう、までは思いつく。
  • DP[選択した荷物の数][たこ焼きの数][たい焼きの数] で管理...?
    • 詰まる。

====ここまででコンテスト終了====

  • 解説を見て次のように理解した。
    • DP[弁当の番号][たこ焼きの数][たい焼きの数] = その重さになる弁当の個数の最小値 を保持しておく。
    • DP のテーブルは十分に大きな数で初期化しておく。
    • DP[0][0][0] = 何も弁当を食べていないのでたい焼きもたこ焼きも食べていない状態は 0 で初期化する。
    • 弁当 1 を たこ焼き0, たい焼き0 の状態で食べる場合と食べない場合で判断する。
      • 食べる場合: DP[1][0 + 弁当 1 のたこ焼きの数][0 + 弁当 1 のたい焼きの数] を更新する。
      • 食べない場合: DP[1][0][0] を 更新する。
      • 例えば弁当に入っているたこ焼きが 3 個、たい焼きが 2 個だったとすると弁当 1 を食べることによって DP[1][3][2] が 1 に更新される。
      • この状態で弁当 2 (1, 3 とする)を食べることを選ぶ場合
        • 弁当 1 を食べていなかった場合を仮定する場合には DP[2][1][3] = DP[1][0][0] + 1 で更新される。
        • 弁当 1 を食べていたと仮定する場合には DP[2][4][5] = DP[1][3][2] + 1 で更新される。

今食べようとしている弁当、食べる/食べない場合のたこ焼きとたい焼きの数、その場合の合計弁当数を保持する。弁当数が一番小さいものを保持し続けていけば最終的に DP[最後の弁当][目標のたこ焼き数][目標のたい焼き数] が答えになる。なお、どこかの弁当を食べた結果、目標のたこ焼き数と目標のたい焼き数が X と Y を超えた場合には X と Y だとして扱ってしまう。別に超えても目標の個数が食べられていることには変わりがないため、そのように扱っても問題はない。

以下、実装。

N = int(input())
X, Y = [int(x) for x in input().split()]

bento = []
for i in range(N+1):
    if i == 0:
        A, B = 0, 0
    else:
        A, B = [int(x) for x in input().split()]
    bento.append((A, B))

dp = [[[10**9] * (Y+1) for x in range(X+1)] for y in range(N+1)]

for i in range(N+1):
    A, B = bento[i]
    if i == 0:
        dp[i][0][0] = 0
    else:
        for j in range(X+1):
            for k in range(Y+1):
                # 弁当を選択する場合
                # 食べたあとの X, Y において弁当の個数が小さい方を残す
                ans = min(dp[i-1][j][k]+1, dp[i][min(j+A, X)][min(k+B, Y)])
                dp[i][min(j+A, X)][min(k+B, Y)] = ans

                # 弁当を選択しない場合
                # 前の値を引き継ぐのと、いまの値で弁当の個数が小さい方を残す
                dp[i][j][k] = min(dp[i-1][j][k], dp[i][j][k])

if dp[N][X][Y] == 10**9:
    print(-1)
else:
    print(dp[N][X][Y])

ABC152_D(Handstand 2)

問題

考えたこと

  • n が  2 * 10^{5} オーダなので, n * n のオーダにならなければ良さそう
  • (1, 1) -> (1, 11) -> (1, 101)... と推移していって, xの種類 * yの種類を計算すれば良い
    • (101, 101) の場合, 101, 111, 121...191 の10種類なので 10 * 10 種類
    • (x, y) と (y, x) の両方があるので, 2倍しながら足していけば良さそう
    • x = y の時は2倍にしてはいけない
    • a > b の時は既に加算済なので加算しない
    • a と bの最大値(初期値101なら191)が最大値より大きい場合, 終端処理が必要
  • 実装はできそうだったのでトライ
続きを読む

ABC146_D(Coloring Edges on Tree)

問題

考えたこと

  • 絵を書いてみる
  • 最大の色の数は最も枝の多い頂点の数になる
  • 色をどうやって分けるかが大きな課題
    • 最初は各頂点に k 種類の set をもたせて 1個ずつ pop させていくか?と思ったけど, TLE しそうだし, 実際にしたので駄目だった.
    • 考え直したら, 幅優先探索で頂点移動の際に使った色を渡していけば, 次の頂点ではその色だけ使わないようにできるじゃん, と気づく
    • 手計算でも問題なく動いたため, 実装に取り掛かってみる
続きを読む

ABC151_D(Maze Master)

問題

考えたこと

  • オーダの制約が 20 * 20 = 4,000 =  10^{3}
  • これなら  10^{6} 以内に収まるので全パターンで幅優先探索でOK
    • と思っていたらどうしてもTLEが取れない!なんで!?となりました
続きを読む

ARC030_A(閉路グラフ)

問題

考えたこと

  • 問題の意味がわからなかったため解けなかった
  • 連結成分 の意味を調べて理解できたので, きちんと備忘録として記録する
    • 連結成分 = 1つの独立したグラフ の こと
  • 今回の問題の場合, ノードが1つしか無いグラフに分割していくのが最適
  • 1個飛ばしでノードを切り離していくことになるので n / 2(切り捨て) が最大の連結成分数
  • k が 最大の連携成分より小さければ作成可能, そうでなければ作成不可
  • あとは実装のみ
続きを読む

ABC135_A(Harmony)

問題

考えたこと

  • 一瞬考えてしまったため備忘録として残すこととする
  • a, b の2つの数字が与えられて, |a - k| = |b - k| となる k が存在なら表示する
  • 絶対値なので2つの数字からの距離が等しくなる場所を探せば良い
  • つまり (a + b) / 2 が答え
    • (a + b) % 2 = 1 になる場合には存在しないということになる
続きを読む