0.はじめに
本当にじわじわとレートが上がっている今日この頃。
BでミスをしつつもCまで順調に解け、デンソーを冠している割には
難易度低めか!?と思ったとたんDとEにはてこずり
そのまま時間切れ。
久々のレート減少で-16の750となりました。
3歩進んで3歩下がる感じですね・・・。
1. A - Append s
入力に”s”を付けて出力するだけの簡単な問題でした。
https://atcoder.jp/contests/abc443/submissions/72863374
2.B - Setsubun
節分で食べる豆の総数が一定値を超えるタイミングを出力する問題。
N歳から豆の数を加算していき、Kを超えたらその歳引くNを出力して
終了と 余裕で回答したらWAが出てしまいました。
ちゃちゃっとなおして・・・とおもったらさらにWAが出て
真面目に確認するとループの回数をK回と適当にしていたため
ループに入らないケースが出てしまっていることに気づきました・・・。
無駄に10分も時間をロスしてしまい、レート大幅減の原因となったなと思います。
https://atcoder.jp/contests/abc443/submissions/72874739
3.C - Chokutter Addiction
C問題にしては簡単なので、罠でもあるのか・・・と思いつつ
悩む時間ももったいないので回答。
結果すんなりACでした。
【実装】
1.N、T、リストAを入力
2.次にチョクッターの閲覧を開始する時間X(最初は0)を定義
3.チョクッターを見ていた時間ans(最初は0)を定義
4.以下iを0からカウントアップさせつつN回繰り返し
-1.XがA[i]より小さい場合(チョクッターを見ているときに青木君が通りかかった場合)
-1.ansにA[i]からXを引いた値(Xから青木君が通るまではチョクッターを見ていられた)を加算
-2.XにA[i]+100をセット
5.XがTより小さい時(最後に青木君が通りかかってからT秒までの間にチョクッターを見ていられたケース)
-1.ansにT-Xを加算
6.ansを出力して終了
https://atcoder.jp/contests/abc443/submissions/72880636
4.D - Pawn Line
見た感じいけそうかなーと思い取り掛かりましたが
結局時間内には解けませんでした。
一番前に来ている駒から左右に階段状になるように揃える・・・と考えましたが
途中で中途半端に前にある駒とかあった場合等に適応できませんでした。
解説の2つ目をみたら、基本的な解き方が若干似通っていて
すんなり理解できるのがあったのでそれを参考にしたらACできました。
【実装】
~以下T回繰り返し分~
1.N、Aを入力
2.q(ヒープキュー)とansL(初期のA状態を持たせるリスト)を空で定義
3.リストAを先頭から読み込み、qにAの値と位置のタプルをセット
(ついでにansLにAの値を転記)
4.以下qがなくなるまで繰り返し
-1.qに先頭値を取り出してai(Aの値)とi(値の位置)、にセット
-2.A[i]!=aiの時(qにセットした時点とリストの値が変わっている時)は次のループへ
~iの左側の値チェック~iが0でない時に実行
-3.Ai-1がA[i]+1より大きい時(iの左側の駒を前に進める必要がある)
-1.A[i-1]にA[i]+1をセット
-2.qに(A[i-1],i)のタプルを追加
~iの右側の値チェック~iがN-1でない時に実行
-4.Ai+1がA[i]+1より大きい時(iの右側の駒を前に進める必要がある)
-1.A[i+1]にA[i]+1をセット
-2.qに(A[i+1],i)のタプルを追加
5.ans(移動回数最終値)を0で初期化
6.リストansLとAを先頭から比較し差をansに加算
7.ansを出力して終了
https://atcoder.jp/contests/abc443/submissions/72928866
5.E - Climbing Silver
今一壁を無効かできる条件がしっくりきませんでしたが
まぁ問題なので割り切り、とりかかりました。
コンテスト中は時間が無く糸口もつかめませんでしたが
その後解説を見て意外と簡単だったかもと思いました。
(解説を見た後で言うセリフではないですが)
【実装】
~以下T回繰り返し分~
1.N,Cを読み込む
2.壁情報を入れるS、”#”の最も低い位置を入れるリストWM(初期値-1)を定義
3.以下N回繰り返し(index=j)
-1.sをリストとしてインプット
-2.Sにsを追加
-3.sを先頭から参照し、"#"の時jをWMにセット
4.リストdpをN×Nマス定義(初期値0(移動不可))
5.dp[N-1][C-1](初期位置)に1(移動可能)をセット
6.以下iをN-2から0まで1ずつ減らしつつ繰り返し(壁の下&高橋君の現在値一個上から見ていく)
-1.以下jを0からN-1まで1ずつ増やしつつ(壁の左から右を見る)繰り返し
-1.flg1(下段3方向に移動可能マスがあるかの判断に使用)に0をセット
-2.jが0以外(左端ではない)かつ、dp[i+1]j-1が1(移動可能)の時flg1に1をセット
-3.dp[i+1]jが1(移動可能)の時flg1に1をセット
-4.jがN-1以外(右端ではない)かつ、dp[i+1]j+1が1(移動可能)の時flg1に1をセット
-5.flg1が1の時(下段からの移動ルートがあるとき)
-1.S[i][j]が"."(壁ではない)の時dp[i][j]に1をセット
-2.S[i][j]が"."ではない(壁である)時
-1.WM[j](最下段の壁)がi(現在値)以下の時=壁を壊せる
-1.dp[i][j]に1をセット
-2.WM[j]に-1をセット(そこより上の壁は壊せるため)
7.回答用変数ansに””をセット
8.dp[0]の段の値を文字列としてansにセットし、出力して終了
dpを使いこなせていれば解法を思いつけたのかな‥と思いました。
以上