0.はじめに
Cのグラフ問題にてこずるも、Dはすんなり解けたので
意外と高レートをゲットできました。
ただ、Cはもう少し頑張れば時間内AC頂けたと思うので
その点は反省・・・。
1.A - Majority
A問題なので素直に順に読んでカウントして
過半数が賛成だったらYesを出力。で作りました。
工夫というか、面倒だったので、賛成判定は
インプット文字列の文字数で判断しました。
https://atcoder.jp/contests/abc287/submissions/38379714
2.B - Postal Card
S文字列は下3桁をリストに入れておいて
T文字列は辞書登録。
最後にリストを頭から辞書にあるかチェックしてカウントを
最後に表示。
と素直に解きました。
https://atcoder.jp/contests/abc287/submissions/38386377
3.C - Path Graph?
パスグラフは各頂点が一直線に並ぶと理解し
単純に、各頂点について、辺の頂点として現れる数をカウント
→各頂点のカウントが、1が2つ、そのほかが２
となればいいのでは！と思い実装。
→そんな簡単な話でもなくAC30、WA6
意外といけるかもと微調整するもうまくいかず
ググると閉路判定が必要ということで、そこらへん含めて実装
→AC33、WA3 →なんか根本的な問題かなと思いすっ飛ばしました。
その後解説を見ると、頂点数-辺数＝１という条件もあったので
それを付け加えたら、AC頂けました・・・。
条件自体は気づいていたので、実装できず無念です・・・。
https://atcoder.jp/contests/abc287/submissions/38405605
4.D - Match or Not
自分的には、C問題レベルな気がしながらときはじめ
考え方
先頭からみていって一致する部分と
末尾から見ていって一致する部分で
Tの文字列が作れるか？を簡単に判断できる方法を検討
実装方法
1)リストFCは、先頭からTとSを一文字ずつ比較し
先頭から一致しなかった場合(同じ文字orどちらかが？ではない場合)文字数を保持
実際は一致しなくなったらあとは１でいいけど面倒なのでそのように実装
例）
aabaa
aaaa
FC：0,0,1,1
2)リストBCは、末尾からTとSを一文字ずつ比較し
末尾から一致しなかった文字数を保持
実際は一致しなくなったらあとは１でいいけど面倒なのでそのように実装
例）
aabaa
aaaa
BC：1,1,0,0
3)xを0からlen(T)まで以下の判定
xが0の時(後方一致判定)
BC[x]の値が0ならYes違えばNo(例だとNo)
xがlen(T)と同じ場合(前方一致判定)
FC[x]の値が0ならYes違えばNo(例だとNo)
xがそれ以外の場合
FC[x-1]とBC[x]の合計が0ならYesそれ以外No
→例だと、x＝2の時、Yes
出力例）
No
No
Yes
No
No
TLEだけ心配でしたが、余裕でした。
https://atcoder.jp/contests/abc287/submissions/38413239
5.E - Karuta
残り30分位でとりかかってみるも、AC17、TLE16。
時間を減らす工夫が思いつきませんでした。
ユーザー解説に、ソートすれば前後の文字との比較で済むとあり
目からうろこでした・・・。
ソートしてからチェックすれば、TLEも出ずAC頂けました。
実装
1)文字列のリストをLに格納
2)LをソートしたリストSLを作成
3)SLを先頭から読み込み
前後の文字列と戦闘から比較して
辞書にキーを文字列、値を一致する数が多い方を登録
4)Lを先頭から読みこみ、文字列で辞書を検索して
値を表示
https://atcoder.jp/contests/abc287/submissions/38437825
以上