ABC396回答メモ

0.はじめに

　前回茶色落ちしたものの、あと２つ上がれば緑に戻れるので
　気合を入れなおして臨んだコンテスト。
　今回はなかなか手ごたえがあり、Cでも苦戦するも
　なんとかDまで解けました。
　これは言ったかなと思いましたが、レートは+1と1足りずに
　茶色にとどまりました。
　まぁ、緑だからどうということも無いのですが、何か悔しい感じです。

1.A - Triple Four

　なんとなく、前回のAと似た問題。
　リストを３つ目の値から見ていき
　今見ている値が2つ前の値と同じ＆1つ前の値と同じ場合
　Ｙｅｓを出力して終了
　最後までみて終了していなければＮｏを出力して終了

　https://atcoder.jp/contests/abc396/submissions/63495376

2.B - Card Pile

　キューの練習のような問題。
　キューqを用意し、
　1のクエリーの時は、キューにクエリーで示された値を格納
　2のクエリーの時は、キューが空なら0を
　空でなければｑの右端を取り出して出力
　
　まぁカンタンですが、Ｂ問題でキューを使うようになるとは・・・。

　https://atcoder.jp/contests/abc396/submissions/63504130

3.C - Buy Balls

　意外と難しく、諦めかけた問題。
　【考え方】
　　１）黒のボール数が白以上になるという制約をなくした場合
　　　白と黒それぞれ何個ボールを取り出した場合に
　　　価値が最大になるかを求める
　　２）１）で求めた黒のボール数が、白のボール数以上なら
　　　１）で求めた価値が回答となる
　　３）１）で求めた黒のボール数が、白のボール数未満の時
　　　黒と白の数が同じになるまで、価値の減少が少なくなるように
　　　黒を減らすor白を増やすようボールを選んでいく

　【実装】
　　1.変数N、M・リストB、Wを読み込む
　　2.BとWを降順ソートする
　　3.Bからボールを取り出す場合の価値の最大を求める
　　　-1.変数BS(Bの価値の合計:初期値0)、Bi(価値がBSの時のボール数-1:初期値-1)を定義
　　　　 Bから1つも取り出さない場合の方が価値が高くなる状態を初期値とする（Bの価値がすべてマイナスの場合）
　　　-2.リストBをインデックスiで先頭から見ていく
　　　　-1.B[i]が0以上の時BSにB[i]を加算し、Biにiをセット
　　　　-2.B[i]が0未満の時ブレイク
　　4.3同様に、Wからボールを取り出す場合の価値の最大を求める
　　　変数は、WSとWi（後で考えると、Wは価値が0より大きい場合で参照すればよかったですが
　　　提出時はBと同じロジックで見ています）
　　5.BiがWiより小さい場合以下繰り返し（Bi≧Wiの時は条件を満たしているので5の処理は行わない）
　　　～黒を増やした場合の価値の減少値Bxを求める
　　　-1.BiがN-1より小さい場合、BxはB[Bi+1]*-1(黒の袋から最大の数（マイナス値）を取り出した場合に減少する価値)
　　　-2.BiがN-1と同じ場合は、黒の袋からボールは取り出せないので、BxにINF(10の18乗)をセット
　　　～白を減らした場合の価値の減少値Wxを求める
　　　-3.Wiが0以上の時、WxにW[Wi]をセット
　　　-4.Wiが0の時は白の袋からボールは取り出せないので、WxにINF(10の18乗)をセット
　　　-5.WxよりBxが大きい場合（黒のボール数を増やした方が価値の減少が少ない場合）
　　　　-1.Biに1を加算し、BSにB[Bi]を加算
　　　-6.WxがBx以上の場合（白のボール数を減らした方が価値の減少が少ない場合）
　　　　-1.WSから、W[Wi]を減算し、Wiから1減算
　　6.BS+WSを出力して終了

　https://atcoder.jp/contests/abc396/submissions/63539360

4.D - Minimum XOR Path

　DFS問題に単純な重さではなく、XORで色付けした問題といった感じ。
　根はCOBOL出身の古いプログラマーのため、再帰関数とか今一苦手なので
　不安に思いながら実装。
　【実装】
　　～前準備
　　1.変数N、Mを読み込む
　　2.デフォルトリスト型辞書D(キー：頂点、値：tuple（キーとつながっている頂点とその辺のラべル値）)を定義
　　3.リストR（DFS時に訪れた頂点を保持するリスト）を[0]×（N+1）で初期化
　　4.回答保持用変数ansを2の61乗で初期化
　　6.M回辺情報読み込み
　　　-1.u、v、wを読み込む
　　　-2.D[u]に(v,w)を追加
　　　-3.D[w]に(u,w)を追加
　　6.関数dfs定義（引数　x:チェック始点の頂点、y:チェック終点の頂点、w:チェック中経路のラベルXOR合計値）
　　　(後で見るとyは不要だった)
　　　-1.グローバル変数としてansとRを定義
　　　-2.xがNと同じとき
　　　　-1.ansにansとwの小さい方をセット
　　　　-2.リターン
　　　-3.以下、D[x]からxx,xwを取り出し繰り返し
　　　　-1.R[xx]が0の時（今調べている経路で通ってない時）
　　　　　-1.R[xx]に1をセット
　　　　　-2.関数dfsを引数(xx,y,w^xw)で呼び出し
　　　　　-3.R[xx]に0をセット
　　～メイン処理
　　7.R[1]に1をセット
　　8.関数dfsを引数(0,N,0)で呼び出し
　　9.ansを出力して終了

　最初、ansの初期値を10の18乗にして提出したところ2問WAとなり
　よくよく調べたら、Wの制約である2の60乗の方が大きい事に気づき
　2の61乗に変更したところACでした。
　ここさえ気づいていれば、緑行けたかも…と悔やみました。

　https://atcoder.jp/contests/abc396/submissions/63552894

以上