Hugkunバチャコン 2022/12/29 1〜7問 解いてみた

バチャコンはこれ↓です

Hugkunバチャコン 2022/12/29

• コードは雑めです。ゆるしてー
• 競技プログラミングの勉強一切したこと無いので、テクニックは知らないよ。ごめんねー

1問目 ABC275_A問題(diff=14)

提出コード

import numpy as np
 
n = int(input())
h = list(map(int,input().split()))
print(np.argmax(h)+1)

• np.argmax()を知っていればすぐに解ける問題ですね。
• numpy使ったことない人は地道にforで回したかも？

2問目 ABC045_A問題(diff=26)

提出コード

a = int(input())
b = int(input())
h = int(input())
 
print(int((a+b)*h/2))

• 台形を求める問題です。台形の面積=（上底+下底）×高さ÷２ですね。
• Pythonですとfloatになってしまうので、問題に合わせてintにキャストしています。

3問目 ABC068_B問題(diff=110)

提出コード

n = int(input())
c = 0
while n>0:
    n//=2
    c+=1
print(2**(c-1))

• 「最も2で割れる回数が多いもの」イコール「2のべき乗」の数になります。
• 単純に２で割っていって、割った回数でべき乗にすれば求まります。

4問目 ABC127_C問題(diff=237)

提出コード

n, m = map(int,input().split())
l_max, r_min = map(int,input().split())
for i in range(1,m):
	l_i, r_i = map(int,input().split())
	l_max=max(l_i,l_max)
	r_min=min(r_i,r_min)
    
result = (r_min+1) - l_max
print(max(0,result))

• 問題文が最初理解できなくて困りましたｗ
• わかってしまえば簡単ですね。
• 行単位で最小値$L_{i}$〜最大値$R_{i}$の範囲が入力されるので、$L_{max}$と$R_{min}$を求めて差分を出力すればOKです。

5問目 ABC125_B問題(diff=61)

提出コード

n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
total = 0
 
for i in range(n):
  sub = v[i]-c[i]
  total += max(sub, 0)
  
print(total)

• コストあたりの価値の最大値を求める問題ですが、要するに $V_i - C_i $ がプラス値のものだけ集計すればいい問題です。
• 上記のように差をとって、プラスのときだけ加算すればOKです。

6問目 ABC251_C問題(diff=246)

提出コード

n = int(input())
max_text, max_value, max_i = "", -1, 0
text_all = set()
for i in range(n):
    text_i, value_i = input().split()
    value_i = int(value_i)
    if text_i not in text_all:
      text_all.add(text_i)
      if max_text != text_i and max_value < value_i:
        max_text = text_i
        max_value = value_i
        max_i = i + 1
        # print(max_text)
 
print(max_i)

• 投稿されたテキストをチェックしながら得点の最も高いものを返す問題です。
• 最大の得点とその位置 $ i $ を求めるには変数は１つずつで良いのですが、テキストはすべて保持しておく必要があります。
• 最初listを使ってチェックしていたのですが速度が遅くTLEになってしまったため、set()で書き直したところ通りました。
• listの計算量O(n)か、setの計算量O(1)か、で通るかどうかが決まる良問ですね。面白かったです。

7問目 ABC150_C問題(diff=422)

提出コード

def factorial (n):
  val = 1
  for i in range(n, 1, -1):
      val *= i  
  return val
 
def factorial_order (n, sequence):
  count = 0
  best_seq = list(range(n))
  for i, seq_i in enumerate(sequence):
      seq_i -= 1
      seq_i = best_seq.index(seq_i)
      seq_count = seq_i*factorial(n-i-1)
      count += seq_count
      best_seq.pop(seq_i)
      # print(f'i={i}, seq_i={seq_i}, seq_count={seq_count}, count={count}')
  return count + 1
 
n = int(input())
pn = factorial_order(n,list(map(int,input().split())))
qn = factorial_order(n,list(map(int,input().split())))
print(abs(pn-qn))

• 「辞書順で」を置き換えると、最善の順列（辞書順で１番目の順列）以外を選択した時にそれよりも後ろの組み合わせの数（階乗で求まる)ｘ辞書順分順位がずれていくので、それを足し合わせることで辞書順を求めることができそうです。
• factorial()は階乗を求める関数になります（math.factorial()と一緒ですが何となく自分で関数作りました。)
• factorial_order()は辞書順で後ろの組み合わせの数を掛けた数を足し合わせながら、辞書順を求める関数です。
  • 最初にbest_seqに最善の順列を入れておきます
  • sequenceは1スタートの値になっているので0スタートの値に変えつつ、index()で辞書順を求めます
  • 求めた辞書順に後ろの数の組み合わせの数を乗じて足し合わせる数を求めます（seq_countに入れています）
  • count(辞書順を算出する変数)にseq_countを足しておきます。
  • 最後にbest_seqからsequenceから取り出した値を削除します。
• $P_i$と$Q_i$の両方を求めたら、あとは差分をとって絶対値にするだけですね。

感想

• 簡単な問題が多いので、Hugkunの学生メンバーでもこれくらいはサラッと書いてくれると安心しますね。

Hugkun競プロ twitterアカウント

• あんまりつぶやいていませんがｗ 参加希望される方は以下にDMくださいねー。
  https://twitter.com/Hugkun_Kyopro