1. 前書き
AtCoderBeginnerContest(ABC)の参加結果と内容の整理、および外部の解説記事を参考にした上で、自分なりに解法を整理していきます。
使用言語はPythonで行きます。本業ではJavaかRubyonRailsユーザーですが、計算速度の問題であったり、トレンドに乗っておくという意味でも（こちらが大きい）、Pythonに慣れていきたいと思います。
2. コンテスト内容
- コンテスト名
- AtCoder Beginner Contest 280
- 開催日時
- 2022/12/3(土) 21:00 - 22:40
- 実施区分
- バーチャル参加
- 2022/12/6(火)
3. 結果
| 区分 | 結果 | 所要時間 | 実行時間 |
|---|---|---|---|
| A問題 | AC | 4:36 | 22ms |
| B問題 | AC | 10:43 | 22ms |
| C問題 | AC | 30:28(3) | 128ms |
| D問題 | WA | - | - |
4. 解説
4-1. A - Pawn on a Grid
4-1-1. 問題文
上下左右に広がる H 行 W 列のマス目があり、各マスにはコマが置かれているか、何も置かれていないかのどちらかです。
マス目の状態は H 個の長さ W の文字列 S1,S2,…,SHによって表され、
Siの j 文字目が # のとき上から i 行目かつ左から j 列目のマスにはコマが置かれていることを、
Siの j 文字目が . のとき上から i 行目かつ左から j 列目のマスには何も置かれていないことを表しています。
マス目上のマスのうち、コマが置かれているようなものの個数を求めてください。
制約
- 1 ≤ H,W ≤ 10
- H,Wは整数
- Siは 「#」 と 「.」 のみからなる長さWの文字列
4-1-2. 入力形式
H W
S1
S1
⋮
SH
4-1-3. 解説
単純に、入力文字列の中の 「#」 の個数を数え上げれば良いです。
4-1-4. ソースコード
h,w = map(int,input().split())
ans = 0
for _ in range(h):
ans += input().count('#')
print(ans)
4-1-5. python文法の整理
該当要素の個数を数える count()
pythonでは、複数の要素をまとめて扱うことができる型を、 コレクション と言います。
その中でも、要素をインデックスの添字で参照できるものを シーケンス型 と言い、以下が該当します。
- リスト（list）
- タプル（tuple)
- 文字列(string)
そのシーケンス型の共通メソッドとして count() があります。
#使用法
[シーケンス].count([該当要素])
#使用例
str = 'abcba'
print(str.count('a')) -> 2
print(str.count('c')) -> 1
4-2. B - Inverse Prefix Sum
4-2-1. 問題文
整数 N と長さ N の数列 S=(S1,…,SN) が与えられます。
長さ N の数列 A=(A1,…,AN) であって、k=1,…,N の全てについて以下の条件を満たすものを求めてください。
- A1 + A2 + … + Ak = Sk
なお、このような数列 A は必ず存在し、一意に定まります。
制約
- 1 ≤ N ≤ 10
- -109 ≤ Si ≤ 109
- 入力は全て整数である
4-2-2. 入力形式
N
S1 ... SN
4-2-3. 解説
入力例1と出力例1を眺めると、法則性に気づくと思います。
入力例1
3
3 4 8
出力例1
3 1 4
法則性
S = (3, 4, 8)
A = (3, 1, 4)
とすると、以下の法則が成り立っています。
A1 = S1
A2 = 1 = S2 - S1
A3 = 4 = S3 - S2
つまり、一般化すると、
An = Sn - Sn-1
4-2-4. ソースコード
n = int(input())
s = list(map(int,input().split()))
ans = [s[0]]
for i in range(1,n):
ans.append(s[i]-s[i-1])
print(*ans)
4-2-5. python文法の整理
配列の最大値を検索 max()
#使用法
max([配列オブジェクト])
4-3. C - Extra Character
4-3-1. 問題文
文字列 S,T が与えられます。S は英小文字からなり、T は S に英小文字を 1 つ挿入して作られたことがわかっています。
挿入された文字は T の先頭から何番目の文字であるか求めてください。
複数の候補が考えられる場合はいずれか 1 つを求めてください。
制約
- 1 ≤ |S| ≤ 5 × 105
- Sは英小文字からなる
- TはSに英小文字を1つ挿入して作られた文字列である
4-3-2. 入力形式
S
T
4-3-3. 解説
入出力例1と2を眺めて考察していきます。
入力例1
atcoder
atcorder
出力例1
5
入力例2
million
milllion
出力例1
5
※3,4,5のいずれかで正解
考察結果
SとTに対して単純に、左から1文字ずつ比較していって、等しくない文字が出現した位置を出力すれば良さそうです。
ただし一点注意が必要で、Sの一番右側に文字が挿入されるケースでは特別な考慮が必要です。
※入出力例には無いので、より注意が必要
4-3-4. ソースコード
s = input()
t = input()
for i in range(len(s)):
if s[i] != t[i]:
print(i+1)
break
if i == len(s)-1:
print(len(t))
break