ABC280振り返り - 成長観察日記

長野県のめっちゃ暗いビジホで挑んだ！さむかった笑

また90分椅子をあたためつづける回！くやしー300越えたかったな
3度目の3完で、安定して茶パフォ出せるようになってきた！

A問題

atcoder.jp

問題概要

#と.がいくつか与えられる。#は何個あるか

考察

配列の中の#の数はcount()で数えられる
ということはforで二次配列の中の # をcount("#")で数えて、足していこう

コード

#入力
h,w = map(int,input().split())
a = [input() for _ in range(h)]

#配列内の#の数を数えるためのans
ans = 0
#それぞれの配列の#の数をansに足していく
for i in a:
  ans += i.count("#")
 
print(ans)

感想

直前にこれを解いており、既視感で解けた。
こういう謎の運を発揮して試験に合格してきたなー

B問題

atcoder.jp

問題概要

ここに累積和(※)の数列がある。さていくつずつ足されたでしょうか？
※足し算の途中計算結果だと思うとわかりやすい。例えば[1,2,3]の累積和は[1,3,6]であり、1,1+2=3,1+2+3=6である。

考察

累積和の逆をやればよいのか、なんか度数分布を埋めるやつでやったな…
引き算していこう

コード

#入力
n = int(input())
s = list(map(int,input().split()))
 
#初期値セット
a = [s[0]]
 
#引いた数を格納していく
for i in range(1,n):
  a.append(s[i]-s[i-1])
 
#あんパック出力
print(*a)

感想

「やった」という感覚だった。
数学力つよめておくの本当に大事ね。

C問題

atcoder.jp

問題概要

文字列SとTがある。TはSの「どこか」に1文字が足されたものである。日本語の例だと
S「なまけもの」
T「なまいけもの」
文字が足されてるのは何番目？

考察

SとTを一文字ずつ比較しよう
追加されたのが最後だったパターンや、元々が2文字だったパターンに気をつけよう
そのために、絶対入力されない文字を足して、SとTの文字数を揃えておこう

コード

#入力 文字数足して数を揃えておく
s = input()+"Z"
t = input()

# いちおう長い方の長さに合わせてループ
for i in range(len(t)):
  if s[i] != t[i]: #違う文字があったら
    print(i+1) #iに+1して出力(インデックスは-1されてるので)
    exit() #出力したら強制終了

感想

はじめてコンテスト中にREしてふええってなった…でもわりとすぐに「n=2のパターンだ」と気付けて手元で実験、4分後無事にAC

D問題

atcoder.jp

問題概要

kの倍数になるn!は何？nを教えてくれ。

考察

そもそも階乗ってなんだっけ…
n = 4だったら 4 * 3 * 2 * 1 の計算結果だ
ということは、kの約数の中にnがいそう。だってその数を掛けないとkの倍数にならないし。
あとn!は必ずk以上になるな。そりゃそうだ倍数だし。
素数は必ずk=nになりそう、約数がそれしかないし。
シミュレーションしか思いつかぬ…（爆死タイムアップ）

コンテスト後「つまりは探しにゆこう…僕らの…"最大公約数"を…」

youtu.be

まず、素因数分解を考える

k = 30の場合

30の因数は 30 / 2 / 3 / 5 = 1 >> [2,3,5]
つまり 2 * 3 * 5 = 30 = 5 * 3 * 2 * 1
階乗にするには4が足りないぞ！4入れたら1 * 2 * 3 * 4 * 5で階乗になるのでnは5ですね！（あっ）

1 * 2 * 3 * 4 * 5 = 30 * 4

掛け算の逆は割り算であることを利用　ていうか因数分解するから割り算する
例えば　1 * 2 * 3 * 5 = 30 と 30 / 2 / 3 / 5 = 1 は逆の関係
1,2,3...のうち、k=30の因数にないものを飛ばしたい
足りなかったから30に掛けた4の部分のこと
n/n = 1 の部分を見つけに行きたい

上記のご要望を叶える
「30と1,2,3...それぞれの共通成分」つまり「GCD（最大公約数）」で割り続けると、n/n = 1 が出てきてくれる

計算してみると

30と1のGCD は 1 >> 30/1 = 30
30と2のGCD は 2 >> 30/2 = 15
15と3のGCD は 3 >> 15/3 = 5
5と4のGCD は 1 >> 5/1 = 5
5と5のGCD は 5 >> 5/5 = 1

今こうやって見ると、最大公約数が1になった部分は因数ではないため 30 * 4 = 1 * 2 * 3 * 4 * 5となるからこの方法使ってるのかな。
まだよくわからない領域だ。なんて検索すれば出てくるのかもわからない。
緑diff、自力ACできるのは何ヶ月後なのだろうか…

コード

#gcd使うためにmathライブラリインポート
import math

#入力
k = int(input())
i = 0

#入力値の2*10**6までループ
while i < 2e6:
  i += 1
  k //= math.gcd(k,i)
  if k < 2:
    print(i)
    exit()
 
print(k)

感想

整数問題は奥が深くてすてきだ

来週(今週)のburiodenは

平日は意味がわからないくらい仕事が爆破しているけれど、土日は精進に集中できる！やったー！！
がんばるー！！！

バチャ精進、気が引き締まって良いです。たのしいよ。