0.はじめに
ちょっと業務時間と被っていましたが、こっそり参戦。
点数的にもD問題も易しめだったためか、A～Dまで解けましたが
D終わった時点で22:30近くとなっておりE以降まで手が届きませんでした・・・。
レートは+22で711と700台に復帰しました。
1.A - Cut
スライスの問題。
まずは適当に作ってみて、結果を見て微調整・・・。
最初に作ったときは、上からK枚とって後ろにつなげるようになっていたり
1枚ずれてたりしましたが、微調整してACとなりました。
https://atcoder.jp/contests/abc368/submissions/57035502
2.B - Decrease 2 max elements
手順がややこしい問題。
心を無にして問題通りにコーディングを行いました。
【実装】
1.変数NとリストAを入力
2.リストAを降順ソート
3.変数ansを0で初期化
4.以下リストA[1]が0以下なるまで繰り返し
-1.A[0]から1マイナス
-2.A[1]から1マイナス
-3.ansに1加算
-4.リストAを降順ソート
5.最後にansを出力して終了
https://atcoder.jp/contests/abc368/submissions/57040210
3.C - Triple Attack
C問題ともなると問題通りにコーディングしてもダメそうなので
敵の体力が5以上の時は、3回の攻撃を1セットでダメージ5として
4以下まで体力減らして・・・・という感じで考えつつ実装。
あとで解説見たらスマートな感じでしたが
泥臭く場合分けして実装しました。
【実装】
1.変数NとリストAを入力
2.変数T(今何回目の攻撃か)を0で定義
3.以下iを0～N-1まで繰り返し
-1.A[i]が5以上の時
-1.変数TP(3回攻撃を1セットとし、何セット攻撃するか)にA[i]//5をセット
-2.TにTP×3を加算
-3.A[i]からTP×5を減算（A[i]に残った敵の体力が入っている）
-2.A[i]>0の時(敵の体力がまだ残っている時)
-1.Tに1加算(とりあえず1回は攻撃必要)
～このタイミングでTに加算することで、残った敵の体力を減らす攻撃が
3の倍数かどうかをこの後計算しやすくなる
-3.A[i]が2の時（A[i]が1の場合は3-2-1.で加算した1回の攻撃で体力が0になる）
-1.T%3が0でない時(3-2-1.の攻撃が3倍撃ではない時)
-1.Tに1加算
-4.A[i]が3の時
-1.T%3が1の時(あと2回攻撃しないと3倍撃にならない時)
-1.Tに2加算
-2.T%3が2の時(あと1回の攻撃で3倍撃になる時)
-1.Tに1加算
-5.A[i]が4の時
-1.T%3が1の時(あと2回攻撃しないと3倍撃にならない時)
-1.Tに2加算
-2.T%3が2の時(あと1回の攻撃で3倍撃になる時)
-1.Tに1加算
4.最後にTを出力して終了
https://atcoder.jp/contests/abc368/submissions/57057776
4.D - Minimum Steiner Tree
木の問題であきらめかけましたが、E以降も解ける気がしなかったので
頑張りました。
よく読めば、Vのリストにない木の頂点を除去していき、除去できなくなったら
その頂点数が答えだなと気づきました。
【考え方】
・リストPに頂点毎に接続される辺の数を保持
・辞書Dに、頂点毎につながっている頂点を保持
・以下、除去される頂点がなくなるまで繰り返し
・リストPから値が1の頂点iを抽出
・頂点iが、リストVにない場合、木から除去
→リストP[i]の値を1マイナスし、辞書Dから除去
合わせて、辺でつながっている先の頂点についても
リストPの値を1マイナスし、辞書Dの値からiを除去
・最後にP[i]の中で、1以上の値の数をカウントし、出力して終了
【実装時の問題と解決法】
・例３のように、最後に点しか残らない場合、P内の値がすべて0になる
→Vを読み込んだ際、Vにある頂点はPの値に1加算しておく
(頂点につながる辺の数が+1されていても回答に影響ない。)
・辞書Dの値をリストで持っていたら、TLEになる
→cPythonで提出したりやC++に翻訳したりと悪あがきするもNG
デフォルト辞書のリスト型を、辞書型にしたところ
TLEせずに行けました。
久々に難問を解いた達成感が味わえました。
https://atcoder.jp/contests/abc368/submissions/57084508
以上