programming

AtCoder Beginner Contest 182 レビュー

ABC182の振り返り

• 4 min read
share:このエントリーをはてなブックマークに追加

結果

Rated コンテスト参加 12 回目にして初の水パフォとなりました。
前々回に緑パフォが出て喜んでいましたが、まぐれの 5 完でまさかの結果です。

嬉しい誤算ですが、持続性には疑問がありますね。
次回で落胆しないように、精進はちゃんとしていこうと思います。

やったこと

  • AOJ の ITP1 を C++で 41 問埋めた
  • paiza の D 問題を Python で 162 問ぜんぶ埋めた
  • AtCoder Problems で Easy と Medium をちょこちょこ Python でやってた
  • 「コーディングを支える技術」を読んだ

これまでの成績

ABC の C 問題は怖くなくなってきたので、A は 1 分、B は 3 分、C は 15 分くらいで解いて 3 完 20 分切りが安定するようにしたいですね。

No.contestABCDEprf
12ABC1820:597:1621:16(1)32:2784:071235
11ABC1810:485:3823:4458:56(4)-881
10ARC10613:12(1)62:56(2)---914
9ARC10520:20(4)40:16-(1)-600
8HHKB20202:3120:16(1)43:36(3)--543
7ARC1047:0164:30(1)---650
6ABC17918:3225:31---122
5ABC1782:565:56---508
4ABC1772:3214:10(2)(3)--332
3ABC1769:0913:2620:32--550
2ABC17510:4639:4891:49(3)--543
-AGC047(1)(1)----
1ABC17457:2553:51(3)--79

こうして眺めてみると、300-400 点台の問題がそこそこ解ければ色変も近いかなというイメージですね。

A 問題

やるだけ。

B 問題

実装が遅かったです。

コード

答えるのがkのほうだったのでans=max(ans,cnt)みたいな書き方から直すときにミスりました。
ちょっとダサいです。

n=int(input())
a=list(map(int,input().split()))
maximum=0
for i in range(2,1001):
  cnt=0
  for j in a:
    if j%i==0:cnt+=1
  if cnt>maximum:
    maximum=cnt  # これの書き忘れでタイムロス
    ans=i
print(ans)

C 問題

たかだか 18 桁か〜。うーん、全探索ｗ

nCrnCrが最大になるのはn=r/2n=r/2のときですね。18C9=48620{}_{18}C_9=48620でざっくり 5 万。
おまけして 20 桁に 5 万かけても高々10610^6回なので余裕で間に合います。

と思ってあとで解説見たらちゃんと場合分けしたり bit 全探索したりするみたい。
まあ、itertoolsでチートしましたが、やってることは bit 全探索と同じです。

コード

n=input()
l=len(n)
from itertools import combinations
for i in range(l,0,-1):
  for j in combinations(n,i):
    if sum(map(int,j))%3==0:
      print(l-i)
      exit()
print(-1)

D 問題

累積和。おわり。

もうちょっと丁寧に言うとiまでの累積和とiまでの最大値を管理してあげれば計算量落とせてハッピー。
これはすぐに思いつきました。

コード

n=int(input())
a=list(map(int,input().split()))
x=0
b=[]
y=0
c=[]
for i in a:
  x+=i
  b.append(x)
  y=max(y,x)
  c.append(y)
ans=x=0
for i,v in enumerate(b):
  ans=max(ans,x+c[i])
  x+=v
print(ans)

E 問題

この問題見たことある！あっ、HHKB の E 問題で見たやつだ〜〜。
しかも HHKB の問題より簡単。やるだけ。

（※実装に時間がかからないとは言っていない）

コード

4 方向について個別に見る。

壁があったら止める。壁がないならひたすらフラグを立てていく。
下と右に伸ばす方と上と左に伸ばす方は、ループを逆順に見てあげれば同じように書けます。

h,w,n,m=map(int,input().split())

grid=[['.']*w for _ in range(h)]
u=[[0]*w for _ in range(h)]
d=[[0]*w for _ in range(h)]
r=[[0]*w for _ in range(h)]
l=[[0]*w for _ in range(h)]

for _ in range(n):
  ia,ib=map(int,input().split())
  grid[ia-1][ib-1]='*'

for _ in range(m):
  ic,id=map(int,input().split())
  grid[ic-1][id-1]='#'

for i in range(h):
  for j in range(w):
    if grid[i][j]=='#':continue
    if grid[i][j]=='*' or d[i][j]==1:
      d[i][j]=1
      if(i+1<h and grid[i+1][j]!='#'):d[i+1][j]=1
    if grid[i][j]=='*' or l[i][j]==1:
      l[i][j]=1
      if(j+1<w and grid[i][j+1]!='#'):l[i][j+1]=1

for i in range(h-1,-1,-1):
  for j in range(w-1,-1,-1):
    if grid[i][j]=='#':continue
    if grid[i][j]=='*' or u[i][j]==1:
      u[i][j]=1
      if(i-1>=0 and grid[i-1][j]!='#'):u[i-1][j]=1
    if grid[i][j]=='*' or r[i][j]==1:
      r[i][j]=1
      if(j-1>=0 and grid[i][j-1]!='#'):r[i][j-1]=1

total=0
for i in range(h):
  for j in range(w):
    if(u[i][j]>0 or d[i][j]>0 or r[i][j]>0 or l[i][j]>0):
      total+=1

print(total)

F 問題

残り時間もうなかったので未着手。

まとめ

まさかの E 問題で進研ゼミ的なシチュエーションに遭遇するとは思わなかった。
サッサと緑になれるようにがんばります。

Thanaism © 2024 | Thanaism is based on Gatsby Casper