ABC201

#はじめに
こんばんは

京都に住んでいる修士2年の大学院生です．
明日というか今日は朝からバイトなので心が憂鬱ですが、頑張ってこの記事を書きます．本日は土曜日ということで朝から勉強しようと思いつつ、のんびりしていたら夕方になっていました．とりあえずABC201には出場しようと思い、だらけきった体をたたき起こしパソコンに向かいました．

今回はこんな感じでRatingは上がてくれました．よかったです．しかし、一向にD問題以降は安定して解けないですね．このままでは緑まで上がるのに時間がかかりそう……

以下ABC201のリンクです．[https://atcoder.jp/contests/abc201]
#全体の感想
A、B、C問題はそこまで難しくありませんでした．しかし、BC問題で雑なコードを書いてしまい、時間をロスしてしまいました．

D問題は（列＋行）について、偶数の場合は高橋君、奇数の場合は青木君が動かすというのは分かって、動かすたびに最適解を求める関数でも書くのかなと思っていたら時間切れになりました．多分時間がいくらあってもできなかったとは思いますが……

#各問題の感想
###A問題
これはそのまま解きました．
等差数列かどうかを判別せよだったのでソートして確認だけしました．

a=list(map(int,input().split()))
a.sort()
if abs(a[0]-a[1])==abs(a[1]-a[2]) :
    print("Yes")
else :
    print("No")

###B問題
これはリスト内の2つ目の要素である高さでソートしました．
本番は思いついた方法で実装してしまったため、汚いコードになってしまいました．

n=int(input())
ans=[]
for i in range(n) :
    s=list(input().split())
    s[1]=int(s[1])
    a=s[0];b=s[1]
    s[0]=b;s[1]=a
    ans.append(s)
ans.sort()
print(ans[-2][1])

入力のところで以下のように書けばよかったですね．文字と数字を並べて書くのは久しぶりでしたので忘れてました．

for i in range(n) :
    s,t=input().split()
    ans.append([int(t),s])

もし[山の名前、山の高さ]の順番のままで山の高さをソートしたければ下のようにすればよかったですね．

「itemgetterを用いて2重リスト内の要素を並び替える」のは忘れないようにします……なんか忘れてしまうんですよね．だから太文字にしてます．

from operator import itemgetter
for i in range(n) :
    s,t=input().split()
    ans.append([s,int(t)])
ans.sort(key=itemgetter(1),reverse=False)

自分のために補足で、wh=[[8,8][2,2][5,3][2,1][4,2]]のリストについて、第１キーの昇順をメインに第２キーは降順にするには以下のコードになる

from operator import itemgetter
wh.sort(key=itemgetter(1),reverse=True)
wh.sort(key=itemgetter(0),reverse=False)

###C問題
これはなんか数学のような問題でしたね……

まずは、４つの数字の並び方について、１種類は１通り、２種類は１４通り、３種類は３６通り、４種類は２４通りと調べました．

後は、〇の書いているインデックスの数字はすべて使った上で、まだ残りの枠があればハテナから選んで使うという方針で解きました．

つまり、（〇の種類）＝n、（？から選んだ種類）＝r、（？の全種類）＝cとすると

ans=（n＋c 種類の並べ方） × （nCr （?からの選び方））

でハテナの選ぶ種類をfor文でまわしてansの和をとれば求まると思いました．
for文は5-nでまわせば問題なかったです．ただ、5-nがcを超えないかだけは気を付けました．

import itertools
s=list(input())
known=[]
unknown=[]
for i in range(10) :
    if s[i]=="o" :
        known.append(i)
    elif s[i]=="?" :
        unknown.append(i)
    else :
        continue
if len(known)>=5 or len(known)+len(unknown)==0 :
    print(0)
    exit()

def ncr(i) :
    return len(list(itertools.combinations(unknown,i)))

def comb(i) :
    if i==1 :
        return 1
    elif i==2 :
        return 14
    elif i==3 :
        return 36
    elif i==4 :
        return 24
    else :
        return 0

ans=0;n=len(known)
for i in range(5-n) :
    if i>len(unknown) :
        break
    ans+=comb(i+n)*ncr(i)
print(ans)

###D問題
答えを読むとそのコマからどの動きが最大の点数になるかを調べて動かし続けるといったものでした．
全体の感想でも言ったように、コマを動かす人は
高橋君＝（行数＋列数）が偶数の場合
青木君＝（行数＋列数）が奇数の場合
というのは自分でも分かりましたがそこからがダメでしたね．

今日は夜遅いのでまた解けたらここは更新しますね

###E,F問題
問題文すら読んでいない……

#最後に
そろそろD問題しっかり解けるようになりたいです！！（本当に）
ただD問題の難しさが水色くらいの時になると流石に厳しい……
茶色か緑色くらいでないと自分にはまだまだ厳しい感じではある

atcoder Problem の方で精進するしかないか、後はアルゴリズム勉強会の方のスライド問題を進めていかないとだめですね

それではまた