はじめに

競技プログラミング、yukicoder
No.627 ランダムウォークの軌跡
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

数直線上における点Pのランダムウォークを考える。
☆ランダムウォークとは、一般に、次の位置がランダムに決まる運動のこと
・時刻t=0において、点Pは原点にある。
・ある時刻tにPが座標xにある時、時刻(t+1)には確率1/2で座標(x+1)に移動し、確率1/2で座標(x−1)へ移動する。
長さTの数列Xiが与えられるので、
「この数列が時刻1から時刻Tにおける点Pの座標を順に記録したものとなり得るかどうか」を判定する。

入力：
T
X_1
X_2
...
X_T

1≤T≤100
−100≤Xi≤100

一行目に数列の長さT
続くT行には時刻iにおけるPの座標Xiが与えられる

出力：
数列が「時刻1から時刻Tにおける点Pの座標を順に記録したもの」
となり得る場合は「T」、そうでない場合は「F」を出力する。

解き方

与えられた数列が「時刻Tにおける点Pの座標を順に記録したもの」であるかどうかを調べたい。
まず問題文から点Pは
①時刻t=0において、原点にある
②ある時刻tにPが座標xにある時、時刻(t+1)には確率1/2で座標(x+1)に移動し、確率1/2で座標(x−1)へ移動する
というものであることが分かる。
点Pの移動について②から、
時刻tに「座標x」にある場合時刻が1増えると2/1の確率で「座標(x+1)」もしくは「座標(x-1)」に移動する。
→時刻tが1増えたときの点Pの動きは必ず1ずつ
そして入力は「X_1,X_2,X_3,…,X_T」であることが保証される、
つまりこの数列の中で時刻tは必ず1ずつ増えていく。
ここから、出力は時刻Tが1増えるごとの点Pの位置の記録かどうかを判断したいので
この数列が次の項に進む際に前の数字との差異が１であることを確認すればよい、
ということになる。
また①から時刻t=0において点Pは必ず原点、すなわちx=0にあるので
点Pがtが1増えるごとに1しか動けないことを考慮すると
「X_1」にくる要素は「-1」か「1」になる。

上についてまとめると
出力が「T」すなわち「入力が点Pの動きの記録となりうるために確かめるポイント」は以下の二つとなる。
1.「X_1」にくる要素が「-1」か「1」である
2.数列の「現在の要素」と「次の要素」の差は「1」である

まず2について、
時刻tが1増えるごとに要素が1変化していることを調べればよいので、
前の要素を一時的に保存しておき、
現在の要素との差が1であるかどうか確認すればよい。
このとき、確認したいことは差なので絶対値（Math.Abs(x)）で1の差があるかどうかを確認する。
そして、差が1でないものが一つでもあった時点で
その数列は点Pの記録とはなり得ないので「F」であることが確定する。
また1については点Pが時刻tのとき、必ずx=0に存在することから
前の値の初期化を0でしておけば特別な処理は必要なく
2と同じように処理すればよい。

コード例

using System;

class No627{
    static void Main(string[] args){
        //初めの入力は数列の長さなので
        //後でfor分の回る回数（数列の長さ分、確認すれば全ての要素を確認できる）として
        //使えるようにintにキャストしておく
        var length=Int32.Parse(Console.ReadLine());
        //現在の値を0で初期化
        //t=0のとき、点Pはx=0にあるので次にX_1と比べるときに0で初期化しておくと
        //他の項の処理と同様の、次の値を比べる処理で処理できる
        var now=0;
        //次の値を保存するための変数
        //すぐにX_1が入るので初期化の値は何でもいい
        var next=0;
        //数列の長さ分、今の値と次の値の差異を比べる処理を繰り返す
        for(int i=0;i<length;++i){
            //入力を次の項の変数に入れて保存
            next=Int32.Parse(Console.ReadLine());
            //もし現在の値と次の値の差の絶対値が1かどうか確かめる
            //絶対値→Math.Abs(x)
            if((Math.Abs(now-next))!=1){
                //1ではない場合「F」を出力
                Console.WriteLine("F");
                //この時点で答えは確定しているので処理を終了する
                return;            
            }
            //現在の値と次の値の差が1だった場合は処理を継続
            //「現在の値」を入れる箱に、今の処理で「次の値」だったものを入れて保存する
            now=next;
        }
        //現在の値と次の値の差が1出なかった場合は途中で処理が終了するので
        //ループの最期まできて抜けた数列は各項の差が全て1である
        //よって点Pの記録であると言えるので「T」を出力する
        Console.WriteLine("T");
    }
}