AtCoder AGC 036 A - Triangle (python)

irisruneです。Rustはきちんと勉強してから使わないと厳しい言語だと認識したので、しばらく温めることにします。

問題

atcoder.jp

あまりにも数学要素が強い問題ですが、アルゴリズム面でも少々癖があります（というか癖を出してしまいました）。

import sys
LIM = 1000000000


def input():
    return sys.stdin.readline().rstrip()


def main():
    s = int(input())

    x1 = 0 if s == LIM * LIM else 1
    y1 = 0
    x2 = min((s // LIM) + 1, LIM)
    y2 = s % LIM
    x3 = 0
    y3 = LIM
    print(x1, y1, x2, y2, x3, y3)


main()

何はともあれ三角形の面積を求める公式を使わないことには始まりません。座標点でもベクトルでも何でもいいので調べてきて、式変形を駆使してとおいたときにとなることを導き出しましょう。コンテスト当時の検索キーワードは間違いなく大変なことになっていたでしょう。

あとはこの式からを求めるだけですが、ここも割と詰まりがちな部分だと思います。

自分が解いた道筋としては、はじめ2のべき乗を用いてビット演算で解こうとしていましたが、制約条件としてが設定されていたため、を扱うことができず解くことができませんでした。だと勘違いしていたんですね。

そこで、で割ったときの商と剰余に分割して解こうとしましたが、絶対値の中身が和ではなく差であるため、無理やり和の形にしようとした結果上記コードのように少しややこしくなってしまいました。

具体的な方策としては、

• のとき、で割った剰余はとなる。
  • そのため、とおくことができる。
• のとき、で割った商はより小さくなる。
  • このとき、でを置き換えると、である。
  • そのため、とおくことででを置き換えることができる。
• あとはで割ったときの商と剰余をに、をに代入すればよい。

という形でした。商と剰余の和の形で計算することにこだわった結果、という前提を崩したり3項演算子を用いたりと解説に困る形になってしまいましたね。

雑記

• 今週（先週）はABCもAGCも問題が厳しめな気がします。
• そろそろまたコンテストに参加したいですね。言語はGoの予定です。