はじめに
AtCoderを解く方法について、様々なアプローチで挑戦しているものの、E問題までを行ったり来たり。
で、時々D問題で止まり、挫折中断を繰り返す日々を送るこの頃。
AtCoderで上位の色を目指すのではなく、アルゴリズムの理解と問題→解法の発想技術を身に付けるにはどうすれば良いのか日々検討中。
ということで、今回のアプローチはAtCoderの変数を机上確認出来るレベルに落として、具体例で試してみること。
プログラミングなので、正答コードであれば、変数の範囲を増やせばいいだけだしね。
とりあえず、AtCoder本戦みたいに変数の範囲を巨大なものにするのではなく、アルゴ式の基礎問題のように変数の範囲を絞って、解法を確認しながら地味に回答していくことにします
既存投稿一覧ページへのリンク
C問題
入力例01
def pick_elements_by_step(lst, s, t):
return lst[s-1::t]
def max_consecutive_count(lst):
# リストが空の場合は0を返す
if not lst:
return 0
# 最大連続数と現在の連続数を1で初期化
max_count = 1
current_count = 1
# 2番目の要素から順にループ
for i in range(1, len(lst)):
# 直前の要素と同じ場合、連続数を増やす
if lst[i] == lst[i-1]:
current_count += 1
# 最大連続数を更新（必要なら）
max_count = max(max_count, current_count)
else:
# 連続が途切れたのでカウントをリセット
current_count = 1
# 最大連続数を返す
return max_count
def solve(n, h, ac_ans):
ans = -1*10**18
for i in range(1,n+1):
for j in range(1,i+1):
temp_lst = pick_elements_by_step(h, j, i)
_ans = max_consecutive_count(temp_lst)
if _ans > ans:
ans = _ans
_i = i; _j = j
_temp_lst = temp_lst
print(f"{_j}番目の要素から{_i}飛ばしの要素を抽出したときのリスト{_temp_lst}、{ans}個の連続した値を得られる")
if __name__=="__main__":
n = 37
h = [5, 6, 3, 8, 12, 20, 3, 22, 13, 8, 18, 3, 23, 18, 15, 23, 1, 12, 23, 14, 23, 23, 7, 9, 23, 20, 18, 5, 17, 13, 1, 15, 11, 6, 12, 7, 15]
ac_ans = 5
solve(n, h, ac_ans)
解法ざっくり
入力サンプル01
- step.01: 与えられたリストを1飛ばし、2飛ばし、3飛ばし・・・と追っていく。
- step.02
step.01のリストに対して、等間隔で連続している最大数を求める。
この問題普通に難しいよね。。。
E問題
入力例01
input.txt
29
21 14
21 19
21 25
21 9
19 24
19 5
24 16
19 11
24 1
5 20
16 4
11 23
9 29
16 6
16 15
4 13
5 8
21 17
6 2
6 7
17 3
11 28
11 12
24 26
1 10
5 27
5 18
8 22
解答グラフ
隣接するノードの次数を見て、いい感じに作れる「ユ木」を作れば解けそうな気がするので、もう数題ダミーデータで試してみることにします。
入力例01
input.txt
29
29 19
29 7
29 2
29 18
2 20
20 21
7 13
18 5
2 17
17 22
19 6
17 9
13 24
24 8
29 28
19 12
21 4
28 11
4 1
20 26
17 15
7 27
1 3
4 10
28 16
19 25
18 14
14 23
解答グラフ
