0.はじめに
昨日のARCでレートが699と700まであと１に迫ったので
気合を入れて臨みました。
結果としてはCまでしか正解できず、レートダウンとなりました・・・。
ただ、今回のD問題は予選と違っていつものレベルだった気がします。
1.A - camel Case
文字列ないから大文字を探す問題。
文字コードとかはややこしいので
前に使った大文字一覧を検索して
大文字だったら出力でACとなりました。
https://atcoder.jp/contests/abc291/submissions/39228337
2.B - Trimmed Mean
リストから指定した範囲を抜き出す問題のアレンジ版。
いろいろやり方はありそうでしたが、要素数も少ない制約だったので
-もらったリストをソートしたのち、回答用リストLに移していく
-ただし、先頭N個(添え字がNより小さい場合)と
末尾N個(添え字が4*Nより大きい場合)はうつさない
-Lの合計をLの個数で割って平均を求め表示
と、素直に組んでACとなりました。
https://atcoder.jp/contests/abc291/submissions/39237397
3.C - LRUD Instructions 2
座標移動問題。
最初、途中で原点に戻るかどうかの問題と勘違いしてWAを食らいました。
（例題含め、ミスリードしている気がしないでもない。）
その後移動後の座標位置を辞書に登録する形で実装し
移動後に前に訪れた場所かを判定し訪れていればYesを表示して
exitする実装でACを頂けました。
もったいなかったのは、提出時にテスト用のdictを出力する
バージョンを提出してWAを食らったことでした・・。5分ロス。
https://atcoder.jp/contests/abc291/submissions/39246854
4.D - Flip Cards
一時間以上時間が残ってましたが正解にたどり着けませんでした。
考え方の方向性はあっていた・・・ようないないような・・・。
【考え方(誤)】
・まず先頭のカードは裏表どちらでもよいので
パターン数(ans)に2をセット
・その後、1枚ずつパターン分けして考える。
前表：後表、前表：後裏、前裏：後表、前裏：後裏
をそれぞれ比較し、Nans(初期値0)に同じなら+1、違うなら+0する
-i番目のカードが、表でも裏でもi-1番目のカードと
同じ数字にならない（Nans＝0）時は、ansに2をかける。
-表も裏も同じ数字かつ、1枚前のカードも表も裏も
同じ数字の場合（Nans＝4)は、ansに0をかけて出力してexit。
といったところまでは、思いついたのですが、
Nans＝1～３の時どうすればいいの？？となって時間切れ。
解説を見ると、DPとなってはいましたが、上の考え方の
ansをXとY（前のカードが表のパターンと裏のパターン） に分けて
考えればよいと理解しました。
【考え方(正)】
1)リストXにカードの1枚目から表の数字を格納
2)リストYにカードの1枚目から裏の数字を格納
3)前のカードが表の場合の変数ansXと裏の場合の変数ansYを用意し
1枚目のケース分ansX=1、ans=1で初期化。
（Nが1の場合は、答えはansX+ansYで2となる。）
4)以下、添え字iを１～Nまで繰り返す。
4-1)添え字iのカードが表の場合のケース数をセットする変数NansXと
添え字iのカードが裏の場合のケース数をセットする変数NansYを用意
4-2)前のカード(i-1枚目)の表裏と今のカード(i枚目)の表裏を比較
4-2-1)前表(X[i-1])：後表(X[i])が違うとき
NansXにansXを加算
4-2-2)前裏(Y[i-1])：後表(X[i])が違うとき
NansXにansYを加算
4-2-3)前表(X[i-1])：後裏(Y[i])が違うとき
NansYにansXを加算
4-2-4)前裏(Y[i-1])：後裏(Y[i])が違うとき
NansYにansYを加算
4-3)ansXにNansXをセット
4-4)ansYにNansYをセット
5)ansX+ansYのmodを出力
前のカードが表だった場合、今のカードが表裏どちらでもよい場合は、
今のパターンが表＆前のカードが表のパターン数+今のパターンが裏＆前のカードが表のパターン数
なので結果的に2倍、
前のカードが表だった場合で、今のカードが表しかだめな場合は、
今のパターンが表＆前のカードが表のパターン数なので、結果的にパターン数は増えない。
と、うまく説明できているかはわかりませんが、私の中では納得いきました。
https://atcoder.jp/contests/abc291/submissions/39280542
以上