うまい寿司が食いたい。

うまい寿司が遠慮なく食べれるようになるまで,進捗とか垂れ流すブログ

ABC111で学んだこと。

昨日(2018/9/29)行われた,ABC111に参加した。
ただ,集中力が散漫でレートが落ちてしまったので,きっちり復習したいと思います。

AtCoder Beginner Contest 111 - AtCoder

以下,学んだことをまとめます。

A問題

猫のすぬけは文字を書く練習をしています。 すぬけは今日、数字の 1 と 9 を書く練習をしていたのですが、 間違えて 1 と 9 をあべこべに書いてしまいました。
すぬけが書いた 3桁の整数nが与えられます。
nに含まれる 1 という桁をそれぞれ 9 に、 9 という桁をそれぞれ 1 に置き換えて得られる整数を出力してください。

https://beta.atcoder.jp/contests/abc111/tasks/abc111_a

要するに,三桁の整数の9と1を入れ替えてくださいという問題

僕の回答はかなり間に合わせ的な回答で,

N = str(input())
print(N.replace('1','4').replace('9','1').replace('4','9'))

pythonの組み込み関数であるreplaceでとりあず,1を適当な数字(ここでは4)に入れ替えて,9を1に入れ替えました。
そして,最後に適当な数字を9に入れ替えるという方法を取りました。

ACになったコードを提出順にしてみて見てみます。

d={'1':'9', '9':'1'}
print(''.join(d[c] for c in input()))

kyunaさんの回答

1を9,9を1にする辞書を作っておいて,inputをkeyとして読み取る方法でした。
join関数の使い方をよく把握してなかったので,これは勉強になりました。

l=list(input())
for i in range(len(l)):
    if(l[i]=='9'):
        print(1,end="")
    else:
        print(9,end="")

ankush_sharma_GL さんの回答

for文とif文を組み合わせれば良いというのと,最後の改行をなくすために,end=""を入れればよいということがわかりました。

for文とif文を組み合わせるのと,join関数を使う方法として,

a = list(input())
for i in range(3):
    if a[i] == "1":
        a[i] = "9"
    else:
        a[i] = "1"
print("".join(a))

RyoTeiさんの回答
というものもありました。そのままだと,listオブジェクトになるので,joinが必要なんですね。よくわかりました。

賢いな,と思った回答としては,

n=int(input())
print(1110-n)

aytkdkさんの回答
がありました。これは本当に賢いと思います。

B問題

黒橋君は,AtCoder Beginner Contest (ABC) にまだ参加したことがありません.
次に行われる ABC は第 N 回です. 黒橋君は,初めて参加する ABC を第 x 回としたときに,x の十進法表記でのすべての桁の数字が同じであるようにしたいです.
黒橋君が初めて参加する ABC としてふさわしいもののうち,最も早いものは第何回でしょうか?

ゾロ目の大会に参加したい,という要請になります。 僕の回答は,if文の仕様がなぜかごっちゃになって冗長なコードになっていました。 いまから思えば,もっと簡単にかける気がしています。

n = input()

if int(n[0]) <= int(n[1]):
    if int(n[0]) == int(n[1]) and int(n[0]) >= int(n[2]):
        temp=int(n[0])
        print(temp*100+temp*10+temp)
    else:
        temp=int(n[0])+1
        print(temp*100+temp*10+temp)
else:
    temp=int(n[0])
    print(temp*100+temp*10+temp)

僕の回答 だいぶ反省をしています。

n = int(input())

a = -(-n//111)

print(a*111)

tokuさんの回答
多分これが正解なんじゃないでしょうか?
111で割って切り上げて,その値を111倍する。シンプルかつわかりやすいです。

切り捨てを使う方法として

n = int(input())
print(111 * (int((n-1)/111)+1))

minefyさんの回答
がありました。

この辺りを参考に,切り捨て・切り上げのことは頭に置いておきます。

C問題

数列 a1, a2,..,an が以下の条件を満たすとき、 /\/\/\/ と呼ぶことにします。
- 各 i=1,2, ...,n−2 について、ai=ai+2
- 数列に現れる数はちょうど 2 種類
偶数長の数列 v1,v2,...,vn が与えられます。 要素をいくつか書き換えることでこの数列を /\/\/\/ にしたいです。
書き換える要素の数は最小でいくつになるか求めてください。

回答できませんでした。

import collections

n = int(input())
v = list(map(int, input().split()))

if len(set(v)) == 1:
    print(int(n/2))

else:
    odd = v[0::2]
    even = v[1::2]
    if len(set(odd)) > 1:
        odd_c = collections.Counter(odd).most_common()[1:]
        values, odd_counts = zip(*odd_c)
        odd_num=sum(odd_counts)
    else:
        odd_num=0
        
    if len(set(even)) > 1:
        even_c = collections.Counter(even).most_common()[1:]
        values, even_counts = zip(*even_c)
        even_num=sum(even_counts)
    else:
        even_num=0
        
    print(odd_num+even_num)

僕の回答

これでWAでした。
理由は簡単で,最も多く出てくる数が同じ場合を考えてなかったためです。

1 2 1 2 1 1 2 1 3 1
このときに両者ともにすべての数字を1に変えるような操作の数を出力するようにしています。
コードも冗長であまりよろしくなさそうです。

さて,正解のコードを見る前に実装しながら学んだことを書いておきます。 まず

import collections

これを学びました。参考:ABCを解きながらググったサイト, 便利と書いていたQiitaの記事
具体的な中身は参考のサイトを見ればよいのですが,このcollections.Counter()関数を使うことで,リスト内に出てくる数のカウントをしてくれます。
ただ,このままですと出てきた順にしか出力されないので,.most_common()をつけてあげることで,頻度順に並びます。大変便利ですね。

次に,

 odd = v[0::2]
 even = v[1::2]

このリストの書き方です。
1つ目の引数から,2つ目の引数だけスキップして読み取ることができます。
これのお陰で,偶数リスト,奇数リストの作成が簡単にできました。

ここまでで,

  • 偶数,奇数番目だけのリストを作成することができる。
  • リスト内の要素を頻度順に出すことができる。

ようになりました。

これらを使ってどのように正解を導いているのか正答を見ていきます。

from collections import Counter


def solve(V):
    n = len(V)
    ac = Counter(V[::2]).most_common(2)
    bc = Counter(V[1::2]).most_common(2)

    if ac[0][0] != bc[0][0]:
        return n - ac[0][1] - bc[0][1]
    else:
        if len(bc) == 1 or len(ac) == 1:
            return n // 2
        else:
            return n - max(ac[0][1] + bc[1][1], ac[1][1] + bc[0][1])


if __name__ == "__main__":
    n = int(input())
    l = input()
    print(solve(l.split(" ")))

mitsuo0114さんの回答
ソートして,現時点で一番速いものを選びました。

most_common(n)でn番目までの要素を出してくれます。
今回の問題では「奇数番目の最頻値=偶数番目の最頻値」のときに二番目に出てくる要素の数を知る必要があるので,most_common(2)まで書けばよかったんですね。

次に,if文は三通りに分かれています

    if ac[0][0] != bc[0][0]:
        return n - ac[0][1] - bc[0][1]
  • hoge.most_common()[0][0]は,「最頻値が何か」
  • hoge.most_common()[0][1]は,「最頻値が何回出てきたか」

を出してくれます。

つまり上のコードでは,最頻値が同じでない場合に,全体から偶数のリストと奇数のリストの最頻値の数を引いています。
これで,入れ替えるべき数がわかるんですね。

    else:
        if len(bc) == 1 or len(ac) == 1:
            return n // 2

最頻値の数が同じとき,偶数リストと奇数リストの数字が完全に同じときに,こちらの数を返すようにしています。

        else:
            return n - max(ac[0][1] + bc[1][1], ac[1][1] + bc[0][1])
 ```
最後のelse文です。ここの解読に一番時間がかかりました。<br>
 - 偶数リストの最頻値と奇数リストの二番目の頻度で出てくる値の和
 - 偶数リストの二番目の頻度で出てくる値と奇数リストの最頻値の和
を取っています。<br>

この和の大きいほうが,入れ替えなくても良い数を最大化するものですので,`max()`関数を使うことで回答になります。<br>

読むと納得できますね。

# D問題

たどり着かなかったので,今回はありません。