ABC371回答メモ

0.はじめに

　企業名を冠していないノーマルコンテスト。
　C問題が難しいと言うかめんどいと言うかだったので
　D問題を見たら簡単で解けました。
　と、いうわけでABDの3問クリアでレートは+21となりました。

1.A - Jiro

　しょっぱなからややこしい問題。
　最初はIF文で条件分けしようと思いましたが
　取りうる値が少ないので＜＞を３つtupleで辞書のkeyにし
　key毎に次男となる人を値に保持し
　読み込んだ値をもとに辞書の値を表示するようにしました。

#辞書の値
D[("<","<","<")]="B" #CBA
D[("<","<",">")]="C" #BCA
#D[["<",">","<"]]="x" #xxx　矛盾した組み合わせ
D[("<",">",">")]="A" #BAC
D[(">","<","<")]="A" #CAB
#D[[">","<",">"]]="B" #xxx　矛盾した組み合わせ
D[(">",">","<")]="C" #ACB
D[(">",">",">")]="B" #ABC

　https://atcoder.jp/contests/abc371/submissions/57744701

2.B - Taro

　凄い決まりのある国だなと思いつつ回答。
　太郎が生まれた家を保持する辞書を用意し
　太郎が生まれた＝辞書にない家で男が生まれたら
　Yesを出力して、辞書に家を追加
　それ以外ならNoを出力とし、AC。
　Aより簡単な気はしました。

　https://atcoder.jp/contests/abc371/submissions/57749316

3.C - Make Isomorphic

　試験中は解き方はなんとなくわかるものの、ちゃんと組み上げる
　自信がなく、D以降に流れてしまいました。
　コンテスト後、解説を見ても、思ったような面倒な解法でしたが
　回答をなぞって一応ACを取って置きました。

　辺を比較しやすくするため、2次元表に持ち、
　それと対応するようにコスト表を整形し
　itertools.permutationsで、H表の全パターン毎に
　辺を全列挙しながら、差異がある辺を比較していくという
　流れで実装しました。

　https://atcoder.jp/contests/abc371/submissions/57797220

4.D - 1D Country

　競プロで典型的な問題。
　XとPのリストと、Pを元に累積和を格納したSのリストを用意
　クエリのLとR毎に、X列から該当の位置を探し
　累積和をもとに間の村の人数合計を表示する感じでACとなりました。

　https://atcoder.jp/contests/abc371/submissions/57760470

5.E - I Hate Sigma Problems

　コンテスト中にCをあきらめたので、Dの後取り掛かりましたが
　正直さっぱりでした。

　コンテスト後解説を見て、答えは数字毎の連続部分列の個数の合計という説明を
　見て、目からうろこでした。
　【実装】
　　1.NとリストAを読み込む
　　2.辞書Dを初期化（D:キー＝リストAに存在する文字種、値＝キーがリストA内に現れる位置のリスト）
　　3.リストAを読み込み、辞書Dにキーと値を登録
　　4.解答用変数ansを0で定義
　　5.変数iに、Dのキーが無くなるまで読み出し
　　　-1.iが含まれる部分文字列をセットする変数sumをN×(N+1)÷２(N個のリストに存在する総連続部分列数)で初期化
　　　-2.リストpを[0]+D[i]+[N+1]で初期化(Aの先頭と後ろにiが存在するようリストを設定)
　　　-3.１～pの要素数の間、jを1ずつ繰り上げして繰り返す
　　　　-1.sumから、(p[j]-p[j-1]-1)*(p[j]-p[j-1])÷2(iが存在しない区間の総連続部分列数)をマイナス
　　6.ansを出力して終了

　https://atcoder.jp/contests/abc371/submissions/57802807

以上