AGC034 A-Kenken Race

１．概要

今日トライした問題は以下。

A - Kenken Race

岩が2つ続いていたらダメ，というのが基本的な考えかた。問題文の制約からA<B<Dは確定するので，CがA,B,Dの間のどこに来るかで3パターンに分かれる。

1. A < C < B < D
2. A < B < C < D
3. A < B < D < D

２． パターン１ （ A < C < B < D ）

AはCに向かい，BはDに向かうので，A-C間とB-D間のそれぞれの区間に岩が2つ続けて存在するときは到達不可能。それ以外は到達可能。

ここでのポイントはC-D間には岩が２つ続いていても良いという点

３．パターン２ （ A < B < C < D ）

区間A-Cと区間B-Dは重なっているため，区間A-Dにおいて岩が2つ続けて存在してはならない。それ以外のときは先にB→Dを移動させておけば，A→Cの移動においてBが邪魔になる（パターン３で後述）こともないので，到達可能である。

４．パターン３ （ A < B < D < C ）

このパターンではまった。区間A-Cが区間B-Dを含んでいるため，AがBを追い越す必要がある。このとき，AにとってBは岩と同じ役割（つまり邪魔）である。ただBは移動できるので，区間B-Dの中に 　． （岩がないところ）が3つ続けてあれば，．Ｂ  ．となるようにBをあらかじめ移動させておけばAはBを追い越すことができると考えた。そう考えて実装すると1ケースWAとなった。誤りだったのは区間B-Dの中に 　． （岩がないところ）が3つ続けてあればという点であった。実際はBの１つ手前の場所をB1とすると区間B1-Dにおいて　． が3つ続けてあればよかったのである。そのように実装を修正して提出すると無事ＡＣとなった。

５．終わりに

パターン３において，最初の実装では1ケースWAになり，BをBの1つ手前までと修正することでACを獲得したが，そこをBの2つ手前までとするときちんと最初のときとは別の１ケースのみWAとなった。

きちんと境界値をテストケースに入れてあるということを思い知らされる良い学びであった。