AtCoder

ABC359 C問題(Tile Distance 2)を解く

AtCoder_ABC359_C

AtCoder が提供しているABC(AtCoder Beginner Contest)359 C問題をC++とPythonで解いてみました。ABC359は、2024年6月22日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Couples(Difficulty : 828)

問題の詳細は、リンク先をご覧ください。

ABC359 C問題 Tile Distance 2

x軸とy軸を分けて考えます。AtCoder Problems による Difficulty は 828 でした。

解答案

少なくとも $| S_y \;-\; T_y |$ の通行料が発生することが分かります。これを前提として、$x$ 軸方向で必要となる通行料を求めます。

場合分けを簡単にするために $S_x > T_x$ であれば、最初の地点と最後の地点を入れ替えて、$S_x \leqq T_x$ となるようにします。明らかにこの操作で結果は変わりません。

次に $S_x$ と $T_x$ を通行料が発生しない範囲で、二つの値を寄せます。

  • $S_x < T_x$ であり限り
    • $S_x$ のひとつ右の点が同じタイルであれば、$S_x$ の値をひとつ増やす。
    • $T_X$ のひとつ左の点が同じタイルであれば、$T_x$ の値をひとつ減らす。

$y$ 軸方向にひとつ移動すると、$x$ 軸方向の差を通行料を変えずにひとつ少なくすることができます。$x$ 軸方向の差が $y$ 軸方向の差よりも大きい場合に、$x$ 軸方向に余分に発生する通行料を加えます。

C++ プログラム例(ABC359C)

上記の考察をプログラムに変換しました。最後の「$x$ 軸方向の差が $y$ 軸方向の差よりも大きい場合に、$x$ 軸方向に余分に発生する通行料」は、$S_x$ と $T_x$ の値を可能な限り寄せているため、$x$軸の差から$y$軸の差を引いた値を2で割って切り上げた値になります(33行目)。

以下が、C++プログラムです。

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

int main()
{
	ll sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;

	if (sx > tx) {
		swap(sx, tx);
		swap(sy, ty);
	}

	if ((sx % 2 == 0)&&(sy % 2 == 0)&&(tx > sx)) {
		++sx;
	}
	if ((sx % 2 == 1)&&(sy % 2 == 1)&&(tx > sx)) {
		++sx;
	}
	if ((tx % 2 == 0)&&(ty % 2 == 1)&&(tx > sx)) {
		--tx;
	}
	if ((tx % 2 == 1)&&(ty % 2 == 0)&&(tx > sx)) {
		--tx;
	}

	ll y_diff = abs(sy - ty);
	ll result = y_diff;
	ll x_diff = abs(sx - tx);
	if (x_diff - y_diff > 0) {
		result += (x_diff - y_diff + 1)/ 2;
	}

	cout << result << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC359C)

Python版も基本的な考え方は同じです。以下がプログラムです。

"""AtCoder Beginner Contest 359 C"""
sx, sy = map(int, input().split())
tx, ty = map(int, input().split())

if sx > tx:
    sx, tx = tx, sx
    sy, ty = ty, sy

if sx % 2 == 0 and sy % 2 == 0 and tx > sx:
    sx += 1
if sx % 2 == 1 and sy % 2 == 1 and tx > sx:
    sx += 1
if tx % 2 == 0 and ty % 2 == 1 and tx > sx:
    tx -= 1
if tx % 2 == 1 and ty % 2 == 0 and tx > sx:
    tx -= 1

y_diff = abs(sy - ty)
result = y_diff
x_diff = abs(sx - tx)
if x_diff - y_diff > 0:
    result += (x_diff - y_diff + 1) // 2

print(result)

こちらも「AC」と判定されました。

最後に

今回は、C問題までしか解くことができませんでした。ただし、C問題としてはやや難しい緑Diffであったため、レートはあまり下がりませんでした。

引き続き ABC の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA