こんにちは、nemuru_poyaです。飲み過ぎで二日酔いです。画像はhttps://www.photo-ac.com/ からDLしたものです。

今日はAtCoderの大会に参加するために、AtCoder Beginners Selection(https://atcoder.jp/contests/abs) を使って勉強をした際に、どうしようもなく詰まってしまった話をします。

結論としては、「イージーミス」は怖いという内容になっています。

問題  ABC086C - Traveling

リンク: https://atcoder.jp/contests/abs/tasks/arc089_a

こちら、AtCoderで実際に出題されたことのある300点(高得点)問題でしてその内容を要約すると

// 2次元座標で、原点(スタート)から、途中地点への移動を繰り返し、最終的にある点(ゴール)へと到達したい
// 点は全て第一象限にある
// 点から点への移動には、時間tがかかり時間1ごとに、上下左右1マスしか移動できない

// 入力形式
// 途中地点の数Nを指定し、その後N回途中地点の情報を入力する。その際、最後の入力地点がゴールとなる

// N (途中地点の数)
// t x y (途中地点への到着時刻と、途中地点のx,y座標)

// 途中地点には入力された時刻tちょうどに到達する必要がある
// 全ての地点を定刻に訪れ、ゴールに定刻通り辿り着ける場合 「Yes」 を、不可能であれば 「No」を出力する

// N は　1以上　10^5以内
// x, y, t は全て 0以上　10^5以内
// t(i) < t(i+1) でなくてはならない (1 <= i <= N - 1)

この条件を元に、私が最初に出した答案がこちらです

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
 int N;
 // max 10^5 steps
 int t[100000], x[100000], y[100000];
 
 // initial parameter
 t[0] = x[0] = y[0] = 0;
 
 cin >> N;
 rep(i, N) {
 	cin >> t[i + 1] >> x[i + 1] >> y[i + 1];
 }
 
 // ++i
 // 1Step 移動するごとに、総移動距離は奇数→偶数→奇数→偶数となる
 // つまりStep数とStepにおける移動距離の偶奇は一致してないといけない
 // また1Stepで移動できる距離は1なので
 // 総移動距離がStep数以下でなくてはならない
 bool can = true;
 rep(i, N) {
   int dt = t[i + 1] - t[i];
   int dist = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]);
   
   if (dt < dist) {
   	can = false;
   }

   if (dt % 2 != dist % 2) {
   	can = false;
   }
   
   if (!can) {
   	break;
   }
 }
 
 cout << (can ? "YES" : "NO") << endl; 
}

一見良さそうにみえますよね。じつはこれ、ある致命的なイージーミスを犯してしまっています。

「おわかりだろうか...」

具体的には

 // max 10^5 steps
 int t[100000], x[100000], y[100000];
 
 // initial parameter
 t[0] = x[0] = y[0] = 0;

 cout << (can ? "YES" : "NO") << endl; 

の2箇所です。これらは端的に表すと、解法以前の話で

初期条件も含め、制約を守れる初期化をできていなかった

出力規約を守れていなかった

につきます。これで30分ほど悩んでいたので、結構凹みました。

一応の解説

前者の方は最大「10^5」だということで、配列長を「10^5」で設定していました。しかし「10^5」は移動地点の数であって、そこには初期状態(0, 0)が含まれていないことを見落としていました。そのため、N = 10^5のケースの場合にWAとなってしまいました。

後者の方は、問題文の出力条件が「Yes」「No」なのに「YES」「NO」と出力してしまいWAとなってしまいました。

結論 イージーミスは怖い

競技プログラミングの問題を解く中で、つい解法にばかりフォーカスを当ててしまいがちですがこういった問題文をしっかり読み込めていないことが原因のミスにも注意しないと行けないなと改めて感じました。

こういったイージーミスほど、意識の外で起きるため気付けない恐怖があります。その上、同様なミスは日常生活・業務にもつきまとうものです。特に、環境が変わった場合・慢心している場合に牙をむいてきます。

私自身、普段プログラミングの仕事をしているので意識外でのミスの怖さを知っているつもりだったのですが、競技プログラミングという世界の雰囲気と、「普段からコード書いているから」という慢心で、こういったミスを生んでしまいました。

次イージーミスの魔の手にかかるのはあなたかもしれません。私も含め、みなさんも今一度ご注意を...