しがない元高専生の競プロ日記

AtCoderとかいろいろ解いてく

Vtuber杯2021全問題解説記事

VTuber杯2021とは

atcoder.jp

www.youtube.com

1/14のあーだこーだーのゲストとして競プロ系VTuber

蟹江もなみさんときりみんちゃんさん、坂道輪さんがゲストとして呼ばれた際の企画として行われたLockout方式のコンテスト。

youtube.com

www.youtube.com

www.youtube.com

で、これは何

すべて既出の問題で推定パフォーマンスは灰~茶。

後発で受肉した&緑上位コーダーとして解かねば!ということでそれを解く配信をしたのですが...

















www.youtube.com








https://pbs.twimg.com/media/D0LACAaU8AAuE6m.jpg

















30分で解けるでしょ~とか思ってたら1時間15分弱かかってしまい、配信も気づいたら1時間半経ってました...

戒めのためにブログ形式で各問題の解説を残しておこうと思います。

なお、解答はすべてPythonの予定です。(C++はACした提出先リンクを張っておきます)

[追記]

また、YouTubeの私のチャンネルにてVTuber杯の全問題の解説動画を投稿しました。

もしよければ見て頂けると幸いです。

youtu.be

A - Crane and Turtle

atcoder.jp

鶴と亀の足の本数がそれぞれ2本、4本で動物の総数と足の総数が与えられるので正しい鶴と亀の組み合わせが存在するかを判定する問題。

鶴と亀の合計の数は決まってるのでその条件の中で足の数が合うかを全探索すればよいですね。

配信中では2重ループで鶴と亀の足を全探索しましたが1重ループでいいことに気づきました。

解答コードは以下の通りです。

Python解答コード

x, y = map(int, input().split())
# 鶴をa, 亀をbとしています
for a in range(x+1):
  b = x - a
  # 足の本数が一致しているか
  if 2*a + 4*b == y:
    print('Yes')
    exit()
print('No')

atcoder.jp

C++解答コード

atcoder.jp

B - Easy Linear Programming

atcoder.jp

$1$が書かれたカードが$A$枚、$0$が書かれたカードが $B$枚、$−1$が書かれたカードが$C$枚あり、丁度$K$枚取った時のカードの和の最大値を求める問題です。

基本的に優先順位は$A>B>C$の順番で取ってよく、更に$-1$を取るときは$a+b < k$の時(Cを絶対に取らないといけない)になります。

それ以外の場合、$B$は取っても影響はないので$Aを取る個数 - Cを取る個数$ となります。

Python解答コード

A, B, C, K = map(int, input().split())
if A+B < K:
  # Cを取る個数
  takenC = K - (A+B)
  print(A - takenC)
else:
  # A全部+Bいくらか と Aのいくらか、の条件を忘れずに!
  print(min(K, A))

atcoder.jp

C++解答コード

atcoder.jp

C - Echo

atcoder.jp

$N$文字からなる文字列$S$が与えられます。$S$を丁度半分に分割したときに同じ文字列ができますか?という問題。

Pythonsliceが便利なのでRTA?中はPythonで通しました。

C++s.substrがあるのでそれを使えばよいのですが、$N$が奇数の時に死ぬので条件分岐を忘れないようにしましょう(1WAした)。

Python解答コード

n = int(input())
s = input()
print('Yes' if s[:n//2] == s[n//2:] else 'No')

atcoder.jp

C++解答コード

atcoder.jp

D - Digits

atcoder.jp

$N$を$K$進数で表した時の桁数を求める問題。

$K$進数で表すとき、$i$桁以上かどうかは$i$桁全てが$K -1$で埋め尽くされているときの値以上かを考えればよくなります。

例: $N = 700$, $K = 5$のとき、

5進数で4桁以上 -> 4444の10進数表記が700以上かを判定すればよい

(4444)5 =(624)10 < 700

よって700の5進数表記は4桁以上

となる。

※(4444)5は5進数表記の4444という意味です。10進数に直すと624になります。

これを1桁づつ増やして検証していけばOK。

ちなみに$i$桁全てが$K -1$で埋め尽くされているときの10進数の数字は$K^{i} -1$になります。

Python解答コード

N, K = map(int, input().split())
digit = 0
while pow(K, digit) <=N:
  digit += 1
print(digit)

atcoder.jp

C++解答コード

atcoder.jp

E - Kagami Mochi

atcoder.jp

AtCoder Beginner Selectionでも紹介されている1問。

atcoder.jp

餅の半径が$N$個与えられるので鏡餅のように下から上に小さくなる、かつ同じ大きさの餅は選ばないとしたときの最大の段数を求める問題。

配信では与えられた配列の順番を崩してはいけないことに気付かずにLDS(最長減少部分文字列)のライブラリを張ろうとする一幕も。

答えはソートして小さい順に取っていくだけ。

Python解答コード

N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
now = -1
ans = 0
for a in A:
  if now < a:
    now = a
    ans += 1
print(ans)

atcoder.jp

C++解答コード

atcoder.jp

F - Train Ticket

atcoder.jp

$+$, $-$を間に当てはめて答えが$7$になる計算式を求める問題。

Pythonではevalという文字列をそのまま式として評価するやつがあるのでそれで一発でできます。

$+$, $-$を当てはめるのに条件分岐を書きまくるのは賢く見えないのでbit全探索を使うと良いです。

bit全探索についてはけんちょんさんがわかりやすく解説している記事があるのでダイレクトマーケティングしておきます。

けんちょんさんいつもお世話になっております。

qiita.com

Python解答コード

  • bit使うパターン
s = input()
for i in range(8):
  t = ""
  for j in range(3):
    t += s[j] + ['+', '-'][1 & i>>j == 0]
  t += s[-1]
  if eval(t) == 7:
    print(t + '=7')
    break

atcoder.jp

  • bit使わないパターン

Pythonだと文字列のListでそのままfor文に入れる方法もアリなので紹介しておきます。

s = input()
for a in ['+','-']:
  for b in ['+','-']:
    for c in ['+','-']:
      t = s[0]+a+s[1]+b+s[2]+c+s[3]
      if eval(t) == 7:
        print(t + '=7')
        exit()

atcoder.jp

C++解答コード

atcoder.jp

G - Alchemist

atcoder.jp

$N$個の配列$v$が与えられて、任意の2つの要素の平均を求めて使った要素を消して求めた値を$v$の中身が1つになるまで繰り返す。

最後に残った値が最大になるときの値を求める問題。

これは最大値となる値は$v$の1,2番目に小さい値を合成していくことで求めることができます。

Python解答コード

N = int(input())
v = list(map(int, input().split()))
v.sort()
ans = v[0]
# vの1番目の要素から見ていく(0番目じゃないよ!)
for vv in v[1:]:
  ans = (ans + vv) / 2
print(ans)

C++解答コード

atcoder.jp

H - 1-SAT

atcoder.jp

これまでの文字列の中に$S$と$"!"+S$は含まれるかを問う問題。

Pythonならdict型(defaultdict)、C++ならmap<string, int>当で実装できます。

Hashmapだと$\theta(1)$になるとかならないとか...

Python解答コード

from collections import defaultdict
N = int(input())
d = defaultdict(int)
for i in range(N):
  s = input()
  d[s] += 1
for s, v in d.items():
  if d.get('!' + s):
    print(s)
    exit()
print('satisfiable')

atcoder.jp

C++解答コード

atcoder.jp

I - : (Colon

atcoder.jp

今回のコンテストで最難関。

短針と長針の長さ$A, B$、現在の時刻$H, M$が与えられるので時計の長針と短針の位置を求めて頂点同士を結んだ長さを求めてくださいという問題。

数学ができると解けるが自分は競技プログラマーであるが数学者ではないので無理です。死にます。数学を避けてきた人生を悔やみます。

使うのはラジアン余弦定理

ラジアンとは(分かる人はスキップ)

ラジアンとは、「円(扇形)の孤の長さ(L)÷円の半径(r)」によって求められる値のことを指すらしいです。(出展)

180度を$\pi$として計算します。つまり360度は$2\pi$だし、60度は$\pi/3$。

余弦定理とは(分かる人はスキップ)

余弦定理は下の三角形$a,b,c$があった時に、

https://upload.wikimedia.org/wikipedia/commons/thumb/4/49/Triangle_with_notations_2.svg/270px-Triangle_with_notations_2.svg.png

$$ c^{2} = a^{2} + b^{2} - 2ab * \cos(\gamma) $$

が成り立つことを指します。つまり、$c$を求めたかったら

$$ c = \sqrt(a^{2} + b^{2} - 2ab * \cos(\gamma)) $$

となります。ほえ~

で、どう使うの?

今回の問題で長針と短針の位置を角度で求めます。求めた後に頂点同士を結んだ長さを求めるのですが、その長さを知るためには余弦定理が必要です。

更に、余弦定理で必須となる$\cos$関数、様々なプログラミング言語で実装されていますが、引数として与えるのはラジアンである必要があります。

つまり、これらの流れを整理すると、

  1. 入力を受け取る
  2. $H, M$を基に針の位置とその間の角度のラジアンを求める。
  3. 余弦定理を用いて$c$を出す
  4. AC

の流れです。

import math
A, B, H, M = map(int,input().split())
Hrad = (H / 12 ) * 2*math.pi
Mrad = M / 60 * 2 * math.pi
print(math.sqrt(A*A + B*B - 2*A*B*math.cos(abs(Hrad-Mrad))))

というわけで...











f:id:honehaniwa:20210114052735p:plain
WA(迫真)
















は???????????????

















これはなぜか、それは、短針は長針にあわせて動くからです。

つまり10:30になったら短針は10と11の丁度間に動いている、ということです。

これらを踏まえたコードを実装するとようやくACです。

Python解答コード

import math
A, B, H, M = map(int,input().split())
Hrad = ((H + M/60) / 12 ) * 2*math.pi
Mrad = M / 60 * 2 * math.pi
print(math.sqrt(A*A + B*B - 2*A*B*math.cos(abs(Hrad-Mrad))))

atcoder.jp

C++解答コード

atcoder.jp

J - Write and Erase

atcoder.jp

一応ボス問、茶色ぱふぉ。

先ほどのH問題でもあったmapdefaultdictを使う問題。

正直mapdefaultdictを知っていますか?僕は知っています。をするだけなのでするっと書けます。

被りの要素があったらその要素を±したりmod 2で見ればOK。

Python解答コード

from collections import defaultdict
N = int(input())
d = defaultdict(int)
for i in range(N):
  N = int(input())
  d[N] += 1
ans = 0
for i, v in d.items():
  if v%2 == 1:
    ans += 1
print(ans)

atcoder.jp

C++解答コード

atcoder.jp

完走した完走

RTA配信自体は楽しかった(結果は酷かったけど)

この解説記事、書き終えた現在の時刻は深夜5時40分、長針10、短針4の時の頂点の間の距離は$9.414796255572739$だそうです。

とても疲れた。

結構明日のバイトを破滅させて時間をかけて丁寧に書いたのでたくさん読んでくれたらなぁと思います。

終わりに

Youtubeのチャンネル登録Twitterのフォローよろしくお願いします!!!

www.youtube.com

twitter.com

ツカモさんにめざせ100人登録って言われちゃったので目指すしかないやんとなってます、今。