AtCoder Beginner Contest (ABC) 236 Pythonで参戦しました。A,B,C解説あり
前回
こんにちは。めりーです。
遊戯王マスターデュエルがついにサービス開始しましたね。
卒論が書き終わってなかったのにマスターデュエルのせいで時間が溶けていくという悪夢・・・。
でも楽しいからやめられないジレンマ状態です。
そんなこんなで参戦したAtCoder Beginner Contest (abc) 236 です。
結果はA、B、C問題の3完で、パフォーマンスは669でした。
また、今回のコンテストの結果で、レートが394になったので、もう少しで茶色になれる!!
というわけでC問題まで解説していきます。
言語はPython、提出はPyPyです。
目次
A問題 chukodai
chukodai
問題文
文字列Sのa文字目とb文字目を入れ替えてくださいという問題。
文字列を受け取って、そのまま文字列を入れ替えればよさそうです。
というわけで方針は、
1. 入力
2. a文字目とb文字目を入れ替え
3. 出力
という感じでいけそうです。
実際のコードがこちら
s = list(input()) a,b = map(int,input().split()) a -= 1 b -= 1 t = s[a] s[a] = s[b] s[b] = t print("".join(s))
入力でsを受け取るときにlistで受け取っておかないと、その後の入れ替え部分でエラーが起きます。
なので、注意が必要です。
a -= 1 b -= 1
でa、bそれぞれマイナスにしているのは、listで1番最初の文字は0番目と数えるためです。
もともとのa、bは最初の文字を1と数えているため、ここを変更しないと、齟齬が発生します。
print("".join(s))
最後に出力部分のこいつです。
"".join()
を使わずにそのままsを出力すると、以下のようになります。
['c', 'h', 'u', 'k', 'o', 'd', 'a', 'i']
なので、"".join()
で、連結して文字列にする必要があります。
B問題 Who is missing?
Who is missing?
問題文
1からNまでの整数が書かれたカードがそれぞれ4枚ずつ、合計4N枚あります。
そのなかから1枚引いて、残ったカードが与えられます。
引かれたカードは何でしょう。
という問題。
入力されていったものを数えていって、3つしかなかったものが答えになりますね。
それを出力して終わりです。
Pythonで各要素の個数を数えるのは、collectionsが有効なライブラリです。
一応まとめると、
1. 入力
2. 数える
3. 出力
でできます。
実際のコードがこちら
import collections n = int(input()) a = list(map(int,input().split())) c = collections.Counter(a) print(c.most_common()[-1][0])
collectionsの説明だけ。
c = collections.Counter(a)
で、オブジェクトを生成します。
こいつを出力すると、以下のようになります。(入力例1の場合。)
# 入力例1の場合 c = collections.Counter(a) print(c) # 以下出力結果 Counter({1: 4, 2: 4, 3: 3})
このように、各要素とその個数を保持しているオブジェクトができます。
さらに、c.most_common()
では、出現回数順に(要素,出現回数)
を並べたものです。
入力例1の場合は以下のようになります。
# 入力例1の場合 c = collections.Counter(a) print(c.most_common()) # 以下出力結果 [(1, 4), (2, 4), (3, 3)]
つまり、1が4つ、2が4つ、3が3つあることが出力されます。
そして、今回必要な情報は、一番少ない要素数のもの(要素数3のもの)なので、c.most_common()[-1]
で、(3,3)
が出力されます。問題で出力すべきなのは要素数ではなく、要素名なので、c.most_common()[-1][0]
を出力して終了です。
C問題 Route Map
Route Map
問題文
N個の駅が存在します。
各駅に特急列車が止まるか判別してください。
という問題。
各駅について特急が止まるかをチェックするリストを作って、各駅を全探索してチェックリストを更新して最後にチェックリストに従って出力すれば完成です。
方針としては、
1. 入力
2. チェックリストを作る
3. 駅について全探索する
4. 駅に特急が止まるならリストを更新
5. チェックリストに従って出力
というやりかたで行けます。
実際のコードがこちら
n,m = map(int,input().split()) s = list(input().split()) t = list(input().split()) ans = [0]*n t_n = 0 for i in range(n): if s[i] == t[t_n]: ans[i] = 1 t_n += 1 for j in ans: if j: print("Yes") else: print("No")
コードの解説を
ans = [0]*n
で、チェックリストを作成してます。
今回は、このチェックリストの要素が0であれば特急は止まらない、1であれば特急は止まるということにしてます。
for i in range(n): if s[i] == t[t_n]: ans[i] = 1 t_n += 1
全探索パートです。
各駅(s
)について全探索します。
ここで、ポイントなのは、in
を使ってlist内に要素があるかをチェックすると、実行が遅くなります。(ただし、set
なら問題ない)
そこで、t_n
という変数を使います。
この問題では、駅の順番が共通しています。
なので、チェックする駅を1つに限定できます。
入力例1でいうと、「tokyo」「akiba」の順番です。「akiba」「tokyo」の順番はあり得ません。なので、「tokyo」が出てこないうちは絶対に「akiba」は出てきません。よって、「tokyo」が出ていないときは、各駅と「tokyo」を比較すれば良いだけです。
その比較する駅を管理するための変数がt_n
です。
なので、この部分でやっていることは、全ての駅を全探索してまだ出ていない特急が止まる駅の最小の要素と比較することです。
もし、比較して一致する場合は、ans
、t_n
を更新します。
for j in ans: if j: print("Yes") else: print("No")
最後の出力部分です。
ans
を全探索して、その結果によって出力を変化させます。
ans
は「1」か「0」なので、bool型として扱えます。
1だった場合は"Yes"を、0だった場合は"No"を出力して終了です。
bool型なので、if j:
だけで表せるので、スマートですね。
今回の解説はこんな感じです。
次回のコンテストでは茶色になれたらいーなーーって思ってます。
それでは!!