ABC203

#はじめに
こんばんは

昨日は疲れてしまったので今日記事を書くことにしました。最近，暑くなってきましたね。京都も気温が28℃まで上がり，春の終わり梅雨の訪れを感じています。

アルゴリズムの勉強もしたいのですが，今月中に基本情報技術者試験を受けないといけないんですよね。なので，そちらが終わり次第アルゴリズムの勉強は本腰を入れることができるかなあと。

今回はこんな感じでRating耐えてくれました。1週間ぶりにコードを書いたのでこれはヤバい結果になるかなと思っていましたが，意外と何とかなりました。やはりどんな時でも毎週継続してABCコンテストは参加した方が良いですね。このまま下がりさえしなければ，今月中に緑行けそうです！

以下ABC203のリンクです[https://atcoder.jp/contests/abc203]

#全体の感想
さらっと見た感じD問題が苦手な深さ優先探索か幅優先探索のどっちかかなあ、と思ったのでA,B,C問題をすぐに終わらすことにしました。
A,B,C自体は難しくなく20分かからなくらいで終えました。そこから，80分かけてD問題を考えましたが，分からず...
中央値を求める問題でしたが，まずどこを池にするかの箇所で計算を簡単にしないといけないのかなと考えたりしてました。

#各問題の感想
###A問題
疲れていたので，脳死でそのままコードを書きました。

a,b,c=map(int,input().split())

if a==b :
    print(c)
elif a==c :
    print(b)
elif b==c :
    print(a)
else :
    print(0)

###B問題
n階でk室の部屋が各階に存在する。各部屋番号はi階j番目だとi0jとなる。
とのことでしたので，まずは各階の百の位を足して，一の位については各階k*(k+1)//2なのでこれを足していきました。
難しくなかったのでこれもすぐ解けました。

n,k=map(int,input().split())
ans=0

for i in range(n) :
    ans+=(i+1)*100*k+k*(k+1)//2
print(ans)

###C問題
友達の数が210**5なので，ソートしてからfor文で回してもO(410**5)で計算は間に合うだろうと思いました。
後は，友達のいる村までにかかるお金を計算し，所持金から引いて負になれば，そこまでにたどり着ける村の最大の番号を計算する．友達の村につく場合は，そこでもらえる金額分所持金を増やしました．
普通のfor文と実装力が問われている問題でした。

n,k=map(int,input().split())
cnt=[]

for i in range(n) :
    a,b=map(int,input().split()) #aは村番号,bはお金
    cnt.append([a,b])
cnt.sort()

flag=0
for i in range(n) :
    if flag+k<cnt[i][0] :
        print(flag+k)
        exit()
    k-=(cnt[i][0]-flag)
    k+=cnt[i][1]
    flag=cnt[i][0]
if k+flag>10**100 :
    print(10**100)
else :
    print(k+flag)

###D問題
解説を読んだら，どうやら二分探索と二次元累積和を用いるようですね。正直なことを言うと**「二次元累積和」**というワードは初めて聞きました。
この問題についてはもう少し詳しく勉強してから編集したいな...と思います。

N,K=map(int,input().split())
A=[]
 
for i in range(N):
  temp=list(map(int,input().split()))
  A.append(temp)
  
 
#2分探索法
ok=10**9
ng=-1
 
lim = int(K*K/2)+1

def ruise2D(border):
  # 2次元累積和
  s=[[0]*(N+1) for i in range(N+1)]
  for i in range(N):
    for j in range(N):
      s[i+1][j+1] = s[i+1][j]+s[i][j+1]-s[i][j]
      if(A[i][j] > mid):
        s[i+1][j+1] += 1
  
  for i in range(0,N-K+1):
    for j  in range(0,N-K+1):
      #累積和から2分探索。よくわかってない。
      if((s[i+K][j+K] -s[i][j+K] -s[i+K][j]+s[i][j])<lim):
        return True
  return False
  
 
while((ng+1)<ok):
  mid =(ng+ok)//2
  if(ruise2D(mid)):
    #基準より小さい物があれば、探索範囲の上側をカット
    ok=mid
  else:
    #基準よりすべて大きければ、探索範囲の下をカット
    ng=mid
print(ok)

###E,F問題
読む時間も解く時間もなかったですね...
前期中に果たしてE問題を解けるようになるのだろうか...

#最後に
後でAtcoder Problemの方でD問題の難易度を確認したら青レベルでした．しかし、ここが解けるかどうかで緑以降の伸びが変わってくると思います．なので，今月下旬の基本情報基礎の試験が終わり次第，アルゴリズムの勉強頑張ります！！
今月中には頑張って緑いくぞお～