質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

PyPy

PyPy(パイパイ)は、RPythonで記述されたPythonの実装のひとつです。CPythonとの互換性に重点を置いて開発されており、コードを必要に応じて機械語にコンパイルする「JITコンパイル機能」を備えています。

Q&A

解決済

2回答

2026閲覧

AtCoder:square869120Contest #4 B - Buildings are Colorful!で1つだけWAしてしまう

nk1

総合スコア42

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

PyPy

PyPy(パイパイ)は、RPythonで記述されたPythonの実装のひとつです。CPythonとの互換性に重点を置いて開発されており、コードを必要に応じて機械語にコンパイルする「JITコンパイル機能」を備えています。

0グッド

0クリップ

投稿2021/04/26 12:00

編集2021/04/26 12:08

前提・実現したいこと

AtCoder:square869120Contest #4 B - Buildings are Colorful!で1つだけWAしてしまいます。
コードのどこが間違っているのでしょうか?

https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b

発生している問題・エラーメッセージ

一番最後のケース「sub3_in2.txt」がWAです。

該当のソースコード

pypy3

1n,k = map(int, input().split()) 2A = list(map(int, input().split())) 3mlst = [] 4 5if n == 1 or k == 1: 6 exit(print(0)) 7 8for i in range(2**(n-1)): 9 lst = [0]*(n-1) 10 for j in range(n-1): 11 if i>>j & 1: 12 lst[j] = 1 13 lst = [1] + lst 14 if k <= sum(lst): 15 B = A[0] 16 money = 0 17 for l in range(1,n): 18 if lst[l] == 1: 19 if B - A[l] >= 0: 20 money += B - A[l] + 1 21 B += 1 22 else: 23 B = A[l] 24 mlst.append(money) 25 26print(min(mlst))

試したこと

n==1やk==1のときにrangeの範囲がおかしくなるせいかと思ったのですが、そこを場合分けして除いても、やはりWAのままです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

text

14 3 21 10000 2 3

落としてるのが1ケースだけなのでエッジケースを想定してるのかもしれませんが、間違った解を出すのはそれほど特殊なケースではありません。
どういう意図でコードを書いてるのかがわからないので、問題の読み間違いなのか解法の間違いかコードの書き間違いなのか判断できませんが上のケースで気付けると思います。

投稿2021/04/26 13:27

yudedako67

総合スコア2047

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

nk1

2021/04/27 05:59

回答ありがとうございます! エッジケースでも全然ない、このケースでWAするんですね。 このコードの意図はビット全探索で、「1」のビルのみの色塗りをするというふうにコードを書いていましたが、「0」のビルが、それより右の「1」のビルより高いときに不具合が生じていました。 以下のように「0」のビルも考慮に入れたコードをかくことで解決しました! ありがとうございます! n,k = map(int, input().split()) A = list(map(int, input().split())) mlst = [] for i in range(2**(n-1)): lst = [0]*(n-1) for j in range(n-1): if i>>j & 1: lst[j] = 1 lst = [1] + lst if k <= sum(lst): B = A[0] money = 0 for l in range(1,n): if lst[l] == 1: if B - A[l] >= 0: money += B - A[l] + 1 B += 1 else: B = A[l] #ここ! else: B = max(B, A[l]) mlst.append(money) print(min(mlst))
guest

0

pypy3

1n,k = map(int, input().split()) 2A = list(map(int, input().split())) 3mlst = [] 4 5 6 7for i in range(2**(n-1)): 8 lst = [0]*(n-1) 9 for j in range(n-1): 10 if i>>j & 1: 11 lst[j] = 1 12 lst = [1] + lst 13 if k <= sum(lst): 14 B = A[0] 15 money = 0 16 for l in range(1,n): 17 if lst[l] == 1: 18 if B - A[l] >= 0: 19 money += B - A[l] + 1 20 B += 1 21 else: 22 B = A[l] 23 #ここ! 24 else: 25 B = max(B, A[l]) 26 27 mlst.append(money) 28 29print(min(mlst))

投稿2021/04/27 05:59

編集2021/04/27 06:02
nk1

総合スコア42

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問