AtCoder Beginner Contest213に参加しました。
結果
A,B,C問題の3問正解でパフォーマンスが633でした。
最近成績が悪い。精進サボってるのが目に見える形で出てきてるから、日々の訓練は大切なんだなって実感してる。
A - Bitwise Exclusive Or
A問題にしては難しい気がする。ビット演算の知識がないと全探索を始めるところだった。
結論としてはAとBのXORを計算して出力するだけ。
XORは同じ値で2回計算するともとに戻る。例:（X XOR A）XOR A ＝X
なのでBとAのXORを取ることでBからAを相殺して求めたいCが残ることになる。
B - Booby Prize
Aをソートしたときに大きい方から2番めの値がもともとは何番目のものだったかを求める問題。
点数からもともと何番目の値だったかをマップなりの何らかのデータ構造で持っておいて、点数をソート。その後、何らかのデータ構造で持っておいたデータを参照してもともとの番号を求める。
C - Reorder Cards
結構時間がかかった... 操作自体は難しくなさそうに見えるけど計算量を考えると二重ループとかH,Wそれぞれに対するループはできなさそうでちょっと難しかった。
行と列を独立に考えて良さそうで、それぞれをソートしたときに何番目の値なのかを数えれば良さそうなのはすぐにみえた。だけど、行や列で値が被った時の場合を考えるとああでもないこうでもないと考えこんでちょっと混乱した。
D - Takahashi Tour
深さ優先探索（DFS）をすれば良さそうな問題。DFS自体はスタックを使ってすぐにできたけど、遷移先がなくて戻る場合の処理のうまい方法が見つからず、強引に実装したけど結局いくつかのケースてTLEになっちゃった。
回答例を見るとスタックじゃなくて再帰を使っていたからそもそもの第1歩目を間違えてたみたい。スタックを使ってもうまくやる方法があるんだろうなぁ。
