0.はじめに
久々にデイリートレーニング等をやって気合を入れて挑戦。
結果はABCの3問しかとけずいつも通り・・・。
Dは行けそうに感じましたが、解説を見たら行けそうになかったです。
レートは-1とまぁレートにあった成績だったようです。
1.A - Raise Both Hands
ちょっと問題文の理解に時間がかかった問題。
まぁ素直に言葉通りに
L=1、R=0の時 Yes
L=0、R=1の時 No
上記以外はInvalid
と、実装してACでした。
https://atcoder.jp/contests/abc370/submissions/57506634
2.B - Binary Alchemy
Bなのにややこしいなと思いましたが、
インプットをもとにリストを作ったら
あとは、
ansに1をセット
for文で、iを1～Nで回す
ans>=iの時はansにA[ans-1][i-1]をセット
ans<iの時はansに=A[i-1][ans-1]をセット
最後にansを出力
でACでした。
最初、問題文をよく読まず、初手を1と1の融合ではなく
１と2の融合で作ってしまい、WAとなってしまいました。
引っかかった人多そうだなと思いました。
https://atcoder.jp/contests/abc370/submissions/57518138
3.C - Word Ladder
こちらも問題文をよく読まず、簡単だな！と思ってしまいましたが
最後のリストが辞書順にならないといけないというのを見落としてました。
提出前に気づき、考察。解説には素直に全パターン試しても間に合うとありましたが
コンテスト時はC問題だし間に合わないだろうと以下のような考え方で実装
【考え方】
まず、Ｓ[i]>T[i]の箇所を先頭からＳ→Ｔに変換
その後、S[i]<T[i]の箇所を末尾からＳ→Ｔに変換
こうすることで、辞書順に小さい方からのリストができる。
【実装】
1.各入力を読み込む（SとTはリスト化して入力）
2.答えを格納するリストXを空で定義
3.リストLを空で定義
リストLは、以下の2要素で構成されるタプル型を格納
要素１：Ｓ[i]>T[i]の時0、S[i]<T[i]の時1
要素２：要素１が0の時i、1の時i×-1（ソートした時、降順に並ぶように）
4.SとTを一文字ずつ比較して、リストLを作成
5.リストLを昇順ソート
6.リストLを順に読み、以下の処理を実行
-1.要素１が0の時、S[要素2]にT[要素2]をセット
-2.要素１が1の時、S[要素2*-1]にT[要素2*-1]をセット
-3.XにリストSをjoinして追加
7.Xの長さを出力
8.Xを1つずつ出力
https://atcoder.jp/contests/abc370/submissions/57532862
4.D - Cross Explosion
コンテスト時はどうしてもTLEが消えず、時間切れ。
解説をみるとちょっと理解できませんでしたが
Union-Find木をを用いた別解を見てしっくりきて
解説の実装例を模写しつつ、自分なりに解説を
加えて理解できました。
以下余談
コンテスト時1回目の解答
・試しに素直に実装してどれくらい時間が足りないかをつかむ
爆弾が落ちた時の処理は落ちたマスの隣のマスから1つずつ
→TLE４つと意外とちょっとした工夫で行けそうな感じ
コンテスト時２回目の解答
・そのマスに爆弾が落ちた回数を記録しておき
爆弾が落ちた時の処理は落ちたマスの落ちた爆弾数分先のマスから1つずつ行う
→TLE3つとちょっと改善。
コンテスト時３回目の解答
・そのマスに爆弾が落ちたかと、落ちた時は前回落ちた時何マス先の壁を壊したかを記録しておき
爆弾が落ちた時の処理は、何マス先の壊したかの記録分先のマスから1つずつ行う
→時間が迫っていて慌てたためかＷＡ、ＴＬＥも1個あったのでどのみちだめ。
と、あがいていました。
https://atcoder.jp/contests/abc370/submissions/57562413
以上