(本当はコンテスト参加の翌日に記事を上げるつもりだったのですが、色々あってコンテストから1週間後の投稿となってしまいました。)
Cまでしか解けませんでした(Cも5分オーバーで提出したので、実質２完)
ざっくり問題とどのように解いたかをまとめます。
言語はpythonです。
問題文の詳細は下記のリンクより確認していただけると幸いです。
https://atcoder.jp/contests/keyence2019
A問題
数字が4つ与えられるので、それを並び替えて1974という数字の列を作れるかという問題でした。
方針としては入力された数字に1,9,7,4があるかどうかを判定します。一個でもなかったら答えはNOです。
提出したコードは下記のとおりです。
n = list(map(int, input().split()))
if (1 in n) and (9 in n) and (7 in n) and 4 in n:
print("YES")
else:
print("NO")
B問題
問題は文字列が与えられて、その文字列から連続した部分文字列(空でも可)を一度だけ取り除いて"keyence"という文字列になるかという問題です。
久しぶりだったせいで、調べながらやってていたらかなり時間が掛かってしまいました。
入力される文字数が100以下なので、全通り試します。
考え方としては初めに何文字余計な文字が入っているか計算します。(”keyence”は7文字なので、入力された文字列の長さ - 7）
余計な文字は連続しているので、入力された文字から下記のように余計な文字列を取り除きます。
図の残った青で出来る文字列が"keyence"と一致するかを確認し、一致する場合があればYES、無ければNOを出力します。
ちなみに上記の余計な文字列をずらす操作は入力された文字列の長さに関わらず、8回やれば全パターンを調べることが出来ます。
提出したコードは以下の通りです。
S = input()
len_S = len(S)
dif = len_S - 7
for i in range(8):
temp = S[0:i] + S[dif+i:]
if temp == "keyence":
print("YES")
exit()
print("NO")
C問題
C問題は高橋君の試験の準備度Aiと試験を合格するための準備度Biの数列が与えられるので、全部の試験に合格できるようにしたい。高橋君の準備度の総和を変えずに準備度を変えた場合の最小変更回数を求めよ的な問題です。(かなりざっくりした説明となってしまったので、正確な問題はコンテストページから見てください)
考え方としてはまずAiの総和とBiの総和を求めます。Biの総和の方が大きかったらどうあがいても全部の試験に合格することが出来ないので、-1を出力します。
そうでなければ、合格できない試験がいくつあるかを数えます。
ここで、合格できない試験とはAi-Biをした際にマイナスとなった箇所です。
マイナスとなる個数を変数countを用意し、保存します。
次にどうすれば少ない回数で全部合格できるようになるかを考えます。
まず、合格できていない試験を全部合格させるには、いくつの準備度が必要か考えます。
これはAi-Biのマイナスとなった箇所の総和で求められます。ここで、この総和をSumA_Bとおきます。
これを補うために、合格できる試験から準備度をもらうのですが、
最適な選び方は合格できる試験(Ai-Biの0より大きい箇所)を降順でソートし、SumA_Bより大きくなるまで、大きいほうから足していきます。足した個数＋先ほど求めたcountが答えとなります。
注意しなければいけないのは、何もしなくても試験に合格できる場合(Aiの総和＝Biの総和)は0と出力するようにしなければいけません。
一応今回AC出来たのは以下のコードです。(焦って提出してぐちゃぐちゃなので、リンクを貼っておきます)
C提出コード
ブログにまとめていて思ったのですが、C問題の提出コード嘘解法な気もするので、もし間違っている箇所があればご指摘お願いいたします。
0 件のコメント :
コメントを投稿