精進4日目:キーエンス プログラミング コンテスト 2019 A, B, C 問題の復習
A一完で惨敗… orz
B問題でテンパりました。くよくよしても仕方ないので、ちゃんと復習して次に備えます。
A問題
考え方
昇順にソートして、"1479" になっていれば "YES" で、それ以外は "NO"。
python3で実装したコード
割愛。
B問題
考え方
- 入力文字列の、0から番目の部分文字列を切り出す。
- 入力文字列の、から末尾までの部分文字列を切り出す。
- 上記ふたつをドッキングして、"keyence" になる組合せがあれば "YES"、なければ "NO" を出力する。
ドはまりしたポイント
"keyence" の前後に文字がくっつく場合の処理方法を考え出したら、ドツボにはまりました。実のところ、前後半それぞれ切り出してくっつければ、"aakeyence" や "keyencezz" のように中抜け以外の条件でも分類できますね…とりあえず動かしつつ試行錯誤できればよかったのですが、手が動きませんでした。
python3で実装したコード
S = input()
ans = "NO"
for i in range(len(S)):
for j in range(i, len(S)+1):
t = S[:i] + S[j:]
ans = "YES"
break
print(ans)
C問題
考え方
公式解説が非常にわかりやすかったです。31分あたりからどうぞ。
- <となっている準備度はすべて変更が必要。
- ↑で変更が必要な準備度の総量を求める。
- 変更不要な準備度を降順に並べて、大きい方から不足分を賄えるだけの個数を数える。
python3で実装したコード
def compare(lstA, lstB):
"""
このままだと落第するテストと、そのままでも通過するテストに分類。
:lstA: 高橋くんの準備度のリスト
:lstB: 合格水準の準備度のリスト
:lst_fail: 各落第するテストの、準備度不足量リスト
:lst_pass: 各通過するテストの、準備度余裕量リスト(降順に並べる)
"""
lst_fail = [b - a for a, b in zip(lstA, lstB) if a<b]
lst_pass = sorted([a - b for a, b in zip(lstA, lstB) if a>=b], reverse=True)
return lst_fail, lst_pass
def change_count(lst_fail, lst_pass):
"""
不足量を解消するために、余裕量リストから準備度を分配する必要がある要素を数える
:lst_fail: 各落第するテストの、準備度不足量リスト
:lst_pass: 各通過するテストの、準備度余裕量リスト(降順に並べる)
:cnt: 余裕量リストのうち、分配が必要な要素の個数
"""
sum_short = sum(lst_fail)
cnt = 0
scores = 0
for score in lst_pass:
if scores >= sum_short:
break
else:
scores += score
cnt += 1
return cnt
N = int(input())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_fail, lst_pass = compare(lst_A, lst_B)
cnt_f = len(lst_fail)
cnt_p_change = change_count(lst_fail, lst_pass)
if sum(lst_A) < sum(lst_B):
print(-1)
else:
print(cnt_f + cnt_p_change)
むすび
「なにをコードとして書くか」がわかれば、C 問題くらいまでなら実装できる。きちんと日本語を理解して、やることを書き下せるようにしよう。