Zenn
🅰️

ARC.158 by Iyaa

2023/03/13に公開
Python
競技プログラミング
競プロ
tech

概要

コンテスト

AtCoder Regular Contest 158

結果

Iyamada
1613 位
300 点 (1)
110 分 28 秒

A問題
300点(1)
105分28秒

B問題
0点(1)
ー

C問題以降提出なし

本題

感想


　今回のARCはかなり苦戦した。

A問題に時間のほぼすべてを使い、B問題はヤケクソ全探査を提出したのみであった。
　今回のARCはリアル世界の問題の最適解を求めるものではなく、卓上の数字のみの計算という問題を集めたようなものであった。

A問題 +3 +5 +7

問題

整数 x_1 , x_2 , x_3が与えられます。あなたはこれらの整数に対して、次の操作を行うことができます(0回でもよい)

  • (1, 2, 3) の順列　(i, j, k) を一つ選ぶ。つまり 1 \leq i,j,k \leq 3 であるような整数の組(i, j, k) であって i \neq j , i \neq k, j \neq kとなるものを選ぶ。
  • その後、 x_i を x_i + 3, x_j を x_j + 5, x_k を x_k + 7 で置き換える
    あなたの目的は x_1 = x_2 = x_3 が成り立つようにすることです。このことが可能であるか否かを判定してください。可能な場合には、それを達成するための最小の操作回数を出力してください。

T個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \leq T \leq 2 \times 10{^5}
  • 1 \leq x_1, x_2, x_3 \leq 10{^9}


　まず注目したのが、ケース数が20万ということであり、1ケースあたりO(1)で解かないとTELになる可能性が高いということだ。
　今回自分はpythonを使っているため、数はこなせない。

　次に、足す数 3, 5, 7は全て奇数であるため、条件を達成するためにはx_1 , x_2 , x_3がすべて偶数、またはすべて奇数である必要があるということに気が付いた。
　なので、入力が終わった後、このようにして振り分けた。

if x1%2 == x2%2 == x3%2:
    print("これは解けるかもしれない")
else:
    print("これは確実に解けない")


　次に、x_1 , x_2 , x_3の値に関わらず、三つの数の差分によって解けるかどうかが決まっていることに気が付いた。
　なので、問題を単純化し、最小値からの差分が 0, a, b　である三つの数(0 \leq a, b)に3, 5, 7を足していく問題となる。
　次に、3, 5, 7を足す行為も0, 2, 4を足す行為と変えても、まったく問題がないと気が付いた。

　ここからは、問題の本質について考えていく。
　まず自分が発見したのは、差分が0, 0, 2の時、どう頑張っても等しくできない。ということだ。
　しかし、0, 0, 6は
　0, 0, 6 -> 2, 4, 6 -> 6, 6, 6
　となって条件を達成できる。
　他にも、0, 2, 4は達成できるが、0, 2, 6は達成できない、0, 4, 4は達成できないが、0, 6, 6は達成できるなど、色々な差分を試してみた。
　その結果、差分の合計(0 + a + b)が6の倍数である場合、条件を達成できる、ということがわかった。

　なので、コードにその条件を追加する。
　既に奇遇は一致してることを確認しているので、3で割った余りというコードに変更した。

if x1%2 == x2%2 == x3%2:
    if (x1 + x2 + x3)%3 == 0:
        print("これは確実に達成できる")
    else:
        print("これは確実に無理")
else:
    print("これも確実に無理")


　この時点で、条件を達成できるものは選別できた。
　あとは、必要な工程数を考えるだけだ。

　しかし、色々な場合を考えてみるが、法則性が見えてこない。
　とりあえず、考えられる通りを書き出してみた。

場合分け一覧(24まで)
0(もち0) a(小さい方) b(大きい方) 操作回数(回) 0+a+b
0 0 0 0 0
- - - - -
0 2 4 1 6
- - - - -
0 6 6 2 12
0 4 8 2 12
0 2 10 3 12
0 0 12 4 12
- - - - -
0 8 10 3 18
0 6 12 3 18
0 4 14 4 18
0 2 16 5 18
0 0 18 6 18
- - - - -
0 12 12 4 24
0 10 14 4 24
0 8 16 4 24
0 6 18 5 24
0 4 20 6 24
0 2 22 7 24
0 0 24 8 24


　合計値18までやっても見えず、24までやって縦に並べて眺めていたら、次のことに気が付いた。

  • 絶対に合計値を6で割った数よりは小さくならない。
  • aを減らすごとに1ずつ操作回数が増えていく区間がある。

    　さらにみていくと
  • 合計値を6で割った数の時はaとbの値の差が少ない
  • b - 0 + b - aを6で割った数(例えば0, 4, 8の場合、(8 - 0 + 8 - 4) / 6 = 3)になる区間がある。

ここから、b - 0 + b - aを6で割った数が合計値を6で割った数より大きい場合、b - 0 + b - aを6で割った数を操作回数、それ以外の場合は合計値/6とするアルゴリズムを書いて提出したところ、ACとなった。

T = int(input())
answers = list()

for i in range(T):
    x1, x2, x3 = map(int, input().split())
    if x1%2 == x2%2 == x3%2:
        if (x1+x2+x3)%3 == 0:
            X = [x1, x2, x3]
            X.sort()
            X[2] -= X[0]
            X[1] -= X[0]
            X[0] = 0
            a = X[2] - X[0]
            b = X[2] - X[1]
            ab = a+b
            if ab//6 > sum(X)//6:
                answers.append(ab//6)
            else:
                answers.append(sum(X)//6)

        else:
            answers.append(-1)
    else:
        answers.append(-1)

for answer in answers:
    print(answer)


　A問題を解いた時点で既に残り時間は10分となっていた。
　B問題はまったく解けなかったので割愛する。

　それでは、私と貴方に良いアルゴリズム生活を。

Discussion