おはようございます。しほみんです。
火曜日余裕がなさ過ぎて更新し忘れていた...家計の話は土曜日にします。今日は、AB184です。C問題で大やけどしました。解けたものの、D,E問題をあんまり見れず無駄にしました。特にE問題は解けたのになあって感じです。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは1000程度になりました。最近下がり気味....（勉強不足）。
・C#でクラスとかつかってアプリケーションは作れます（最近作ってないからやばいかも...）。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学んでいる。第3回PAST70点で中級取得。
・基本的に本番でやっている。現在60回以上参加、2年目。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回は、ABC、80分でした。C問題焦って変数を書き間違えて30分以上無駄にしてました。D問題はdp的な思想はあってもどうもわからんってなって解けず。E問題はBFSはわかっても実装がめんどくて後回しにしてたら時間足りませんでした。レートは微減でして、966ですねえ。
やっぱC問題までで躓くと大したことにならんので、ちゃんと練習しないとなあって感じです。
今日はA-E問題まで解説します。
ここから問題です。
A問題
2行２列の行列式はad-bcです。これを求めなさい
ad-bcを出力するだけです。
B問題
N問のクイズを解きます。最初はK点です。
正解すると+1点、間違えると-1点です。ただし、0点のときは点数を引きません。
最終点数は何点でしょうか？
まあ、これも単純に
頭から文字列を読んで、'o'なら+1点、'x'なら得点が0点以外のとき、-1点すればよいです。
C問題
無限グリットがあり、超飛竜が(r1,c1)に置かれています。
(r2,c2)に動かすにはなんて必要でしょうか？
動きは以下のようになります
(a,b)にあるとき(c,d)に行ける
・a+b = c+d
・a-b = c-d
・|a-c| + |b-d| <= 3
うーんどれもやっかいですが、周辺3マスと斜めに無限移動できるってことです。
気が付くべき重要なことは、任意のナナメグリットの位置に2手以内で移動できるってことです。
つまり、(a+b) %2 == (c+d) % 2なら、2手以内なのです。
ということは、0,1,2手で移動できるかどうか判定してそれ以外は3手って出せばよさそうです。
1. 0手の条件（a=c,b=d)で判定
2. 1手の条件（上の動き方）で判定
3. 2手の条件（(a+b) %2 == (c+d) % 2または、周辺動いた後、1手の条件))
4. それ以外は3手と出す。
3で(a+b) %2 == (c+d) % 2の条件でよいのは、このとき、斜めに１手だけ動く可能性を2で排除しているからです。また、周辺動いたあと、1手で処理できる条件は別で処理します。
こう整理すると意外と単純ですね...私は0手の添え字が間違っていたのでクソ時間を食いました。添え字重要です。
問題D
金貨X枚、銀貨Y枚、銅貨Z枚あります。
確率DPって分野らしいです。
とはいえDP的な発想がないと解けないです。
答をf(X,Y,Z)とすると、
X+Y+Z = Sとして
f(X,Y,Z) = X/S*(f(X+1,Y,Z)+1) + Y/S*(f(X,Y + 1,Z)+1) + Z/S*(f(X,Y,Z + 1)+1)
となります。
といわれてもなあと思うのでちょっと話すと...
要するに(X,Y,Z)からなる状態は、(X+1,Y,Z)か（X,Y+1,Z)か(X,Y,Z+1)しかありません。
そしてそれぞれなる確率はX/S,Y/S,Z/Sです。
ということは、 XがX+1になるときは、S/X*(f(X,Y,Z) -1)= f(X+1,Y,Z) となるわけです。
これを踏まえるとYがY+1になるときは、S/Y*(f(X,Y,Z) -1)= f(X,Y+1,Z)
ZがZ+1になるときは、S/Z*(f(X,Y,Z) -1)= f(X,Y,Z+1)
ということで、それぞれ、X,Y,Zをかけて、Sで割って移項すると、
先ほどの上記の式が得られます。
結局はそれぞれの推移を考えてそこから推移式を適切に求められるかがカギですね。
コード的には、X,Y,ZからDFS的にどんどん100に近づくところまで求めて、そこから逆算していきます。このとき、メモ化しておいて高速化します。
詳しくはコードを見てください。
問題E
迷路があります。#は入れないところ、'a'から'z'の文字は、同じ文字の位置にワープできます。このとき、SからGまで何手で移動できますか？移動できないときは-1を出力してください。
普通にBFSすれば何とかなりそうです。
ただ問題なのはワープの処理です。これが結構厄介でした。
まず、ワープの位置は記録できるように'a'から'z'までの26のリストを作ります。
そして、ワープ位置はリストに全部入れます。
そして、まずは普通にBFSのコードを考えます。
後は、どこにワープを入れるかですが、ワープはそのワープ位置に来た時に、はじめて全部移動するって前提で入れて問題ないです。よって、ワープ位置のみを例外処理します。また、一度踏んだワープはもう一度踏んでどっか移るというのは必ず非効率（だったら、最初から目的のところに飛べばよい）となるので、すでに踏んだワープ文字は無視するようにします。
ということで書き方ですが、
1. まず迷路を解析。ワープ位置はリストで管理。
2. BFSの基本形を作る
3. ワープ処理を追加する。すべての位置で判定して、終わったらそのワープ文字はもう使わないようにする
詳しくはコードを見てください。
最後に...
まあ方針立ったらすぐ書く方がなんかいいっぽいですね、C-E問題で解けそうなところからやることにしてみます。
ではでは。
