AtCoder Beginner Contest 113

競プロ

さっさと3完したけどDの解法が生えずに終了。
だいたい解法がDPの時はいつもこんな感じなので現状では良しとしよう。

A - Discount Fare

X + Y/2をする。

B - Palace

一個ずつ比較していって平均との差が最も小さいindexおよびその差を記録しておく。
本番では誤差の影響出ないだろうとdouble型使ったけど1000倍してintで解いた方が賢いね。

C - ID

特に考えることはなく実装あるのみ。 vector< pair< int, int > >を用いてP[i]とY[i]を格納した後、県の番号の昇順、県の番号が同じなら年代の若い順に並び替える。ソートする関数はこんな感じかな。 

typedef pair<ll, ll> lpair;

bool comp(lpair p1, lpair p2){
    if(p1.first == p2.first){
        return (p1.second < p2.second);
    }
    return (p1.first < p2.first);
}

vector<lpair> lp;
sort(lp.begin(), lp.end(), comp);

最後の出力のために、もともと何番目にあったかを保持しておく必要がある。方法としてはmap使う or pairの中に何番目だったかの変数をもう一個追加するのが良さそう。圧倒的にmapの方がラク。

D - Number of Amidakuji

解説みたらすんなり理解できたのはよかった。ただ本番中には思いつかないと思った。

「今上から何段目、左から何列目にいて、そこまでにあり得る場合の数」を考えるとそのさきの経路はその値を元に計算できる、つまり部分問題として捉えることができる。

この場合の数がdp[i][j](上からi段目, 左からj列目)で、これを上から下に進めていくことで求める値 dp[H][K]が出てくる。dpの計算は前準備さえすればループ回してやるだけなので省略。

この問題の肝となるのが「i段目からi+1段目に移動するときのその段の線の書き方は何通りあるか」ということである。

このパターンは段によらず一定なので「各段において、列jから列kに移ることができる線の書き方は何通りあるか」というものを求めてあげれば良い。

二次元配列で持つとすればi => jの移動の総数はnum[i][j]となる。

W-1本の線が存在するかどうかはW-1ビットの数値で持ってあげるとよい。隣り合うビットが1になるものを排除するにはどうしたらいいかなーと考えていたところ、TLで「i & (i <<1)がtrueなら排除すればいい」というものを見つけた。頭良すぎでは。

あとはダメなものを排除した全パターンにおいてi => jの移動が可能なnum[i][j]をインクリメントしていけば良い。
もう少し詳しく言えば、それぞれのパターンにおいて縦線につく横線が0本ならnum[i][i] += 1をし、横線があれば、その横線によって移動する先をjとしたときnum[i][j]+=1, num[j][i] += 1をしてあげれば良い。
一番端の縦線のみ少し条件が違うので注意する。

W = 8の時(i,j)要素がこんな感じになれば正しく計算できてると思われる。 

21 13 0 0 0 0 0 0
13 13 8 0 0 0 0 0
0 8 16 10 0 0 0 0
0 0 10 15 9 0 0 0
0 0 0 9 15 10 0 0
0 0 0 0 10 16 8 0
0 0 0 0 0 8 13 13
0 0 0 0 0 0 13 21

当然、2個以上離れた要素では0になっていることがわかる。

そろそろDPに慣れていかないとなぁ(毎回言ってる気がする)