AtCoder Beginner Contest 183 レビュー

結果

4 完でした。

3 完が安定していなかった少し前から比べると成長している実感はあります。が、緑が見えてしまうともう 3 完どころか 4 完でも満足できなくなっている自分がいるのもまた真実です。

今回は、D 問題が茶 Diff で弱かったにもかかわらず解くのに時間をかけてしまい、パフォーマンスは緑にギリギリ届きませんでした。

これまでやったこと

AGC の翌日ということもあり、AGC で出てきた期待値の線形性などの復習も満足に進まないまま臨みました。復習が進んでいないので、AGC049 より今回のレビュー記事のほうが先に投稿される形になりそうです。

以下は AGC049 時点と同一です。

• AOJ の ITP1 を C++で完走した
• paiza の D 問題を Python で 162 問ぜんぶ埋めた
• paiza で S ランクを取得した
• 蟻本の初級編をある程度理解した
• 蟻本の中級編に目を通した
• AtCoder Problems で Easy と Medium をちょこちょこ Python でやった
• 「コーディングを支える技術」を読んだ

これまでの成績

着実に伸びてきていることは嬉しいですが、レート推移グラフの傾きが寝てしまったので、悔しいです。 どうもコンテスト参加 14 回目から、参加回数が少ないことによる補正がなくなるらしいので、次回は緑目前くらいまでいけるといいな、と思っています。

B 問題、メチャクチャ簡単なはずなのに書き間違いに気付かず無駄に時間を書けてしまい、3 完 20 分切りはまたもや失敗してしまいました。悔しい。

A,B,C 問題

割愛します。C 問題はまたもや itertools で楽をしましたが、順列全探索くらいは自力で書けないといけない気がするので、この記事を投稿し終えたら練習します。

D 問題

どうも、これはいもす法の典型問題だったようです。
imos 法という言葉自体は以前から知っていたのですが、全く使えるシーンと内容とが結びついていませんでした。

今回覚えられたので、次からは使っていきたいと思います。（このあと実際に imos 法で解き直すつもりです）

本番時の考え方

1. 開始時間をソートしてplus配列に足し込む（止める時間は考えない）
2. 終了時間をソートしてminus配列から引いていく（出し始めの時間は考えない）

という単調増加／単調減少に分ければ$O(N)$で予備処理が可能なので、まずやる。

最後にplusとminusを合わせこんで、供給量$W$を超えていなければ OK

としました。

が、この考え方が思いついてから、実装にかなり時間がかかりました。
特に実質$O(N)$の処理をnested loopsにして書いているところはかなりセンスがない気がします。（コンテスト中にスッキリとした書き方を思い付けませんでした。）

imos 法で実装したらかなりシンプルですし事前のソートも要らないので、次から区間への足し込みは imos 法を使おうと思います。

n,w=map(int,input().split())
s,t=[],[]
for _ in range(n):
  si,ti,pi=map(int,input().split())
  s.append([si,pi])
  t.append([ti,pi])
s.sort()
t.sort()
MAX_LEN=t[-1][0]-s[0][0]+1
plus=[0]*MAX_LEN
minus=[0]*MAX_LEN
pl=mi=0
for i in range(1,n):
  pl+=s[i-1][1]
  mi-=t[i-1][1]
  for j in range(s[i-1][0],s[i][0]):
    plus[j]=pl
  for j in range(t[i-1][0],t[i][0]):
    minus[j]=mi
for i in range(s[-1][0],t[-1][0]):
  plus[i]=pl+s[-1][1]
flg=True
for i in range(s[0][0],t[-1][0]):
  if plus[i]+minus[i]>w:
    flg=False
print('Yes' if flg else 'No')

E 問題

実は D 問題の実装でバグり散らかして途中 E の考察とかもしていました。
結局、また D に戻って E に取り掛かる頃には残り 10 分という悲惨な結果に。

とりあえず、解説 AC はしておきました。

h,w=map(int,input().split())
s=[input() for _ in range(h)]
MOD=10**9+7

# DP table(1-index)
dp=[[0]*(w+1) for _ in range(h+1)]
# cum sum
bot=[[0]*(w+1) for _ in range(h+1)]
rig=[[0]*(w+1) for _ in range(h+1)]
bor=[[0]*(w+1) for _ in range(h+1)]

# cum sum: 0 to (N-1) => 0 to N
for i in range(1,h+1):
  for j in range(1,w+1):
    # start position is 1
    if i==j==1: dp[i][j]=1
    # add cumsum to dp table each dir
    dp[i][j]+=(bot[i-1][j])%MOD
    dp[i][j]+=(rig[i][j-1])%MOD
    dp[i][j]+=(bor[i-1][j-1])%MOD
    # can get new cumsum from current new dp
    bot[i][j]+=dp[i][j]+bot[i-1][j]
    rig[i][j]+=dp[i][j]+rig[i][j-1]
    bor[i][j]+=dp[i][j]+bor[i-1][j-1]
    # reset value to 0 at wall position
    if s[i-1][j-1]=='#':
      dp[i][j]=0
      bot[i][j]=0
      rig[i][j]=0
      bor[i][j]=0
    # get MOD
    dp[i][j]%=MOD

# output
print(dp[h][w])

解説 AC はしたものの、これを本番で添字をバグらせない自信がまったくないです。

本番の時点での考察

DP は DAG のトポロジカルソートに相当するという概念は知っていたので、まず DP を考えました。

クイーンはタテ・ヨコ・ナナメの直線上にしか動けないので、問題解説にある$DP[i][j]=\dots$の式になりそうなところまではいいとして、そこから累積和を使って解くという考え方ができませんでした。

でも、これよく考えると前回の ABC182 で AC した E 問題の Akariとベースの部分の考え方は一緒なんですよね。

とりあえず、DP・累積和・二分探索・しゃくとりの単発問題はそこそこ気付けるようになってきたので、これらの組み合わせを精度良く見抜けるようになることが大事だと感じました。

まとめ

典型アルゴリズムがだんだん見えるようになってきたので、とにかく実装を重ねて速度と精度をあげることに専念していきます。

早く目標の水色になりたい！頑張りマッスル。