AtCoder が提供しているABC（AtCoder Beginner Contest）359 C問題をC++とPythonで解いてみました。ABC359は、2024年6月22日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Couples（Difficulty : 828）
問題の詳細は、リンク先をご覧ください。
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 の問題を紹介していきます。
