Vtuber杯2021全問題解説記事
- VTuber杯2021とは
- で、これは何
- A - Crane and Turtle
- B - Easy Linear Programming
- C - Echo
- D - Digits
- E - Kagami Mochi
- F - Train Ticket
- G - Alchemist
- H - 1-SAT
- I - : (Colon
- Python解答コード
- C++解答コード
- J - Write and Erase
- 完走した完走
- 終わりに
VTuber杯2021とは
1/14のあーだこーだーのゲストとして競プロ系VTuberの
蟹江もなみさんときりみんちゃんさん、坂道輪さんがゲストとして呼ばれた際の企画として行われたLockout方式のコンテスト。
で、これは何
すべて既出の問題で推定パフォーマンスは灰~茶。
後発で受肉した&緑上位コーダーとして解かねば!ということでそれを解く配信をしたのですが...
配信お疲れさまでした!
— 𝐓𝐓 (@TT_beginner) 2021年1月13日
VTuber杯2021 Any% RTAは1:14分27秒でした!
chokudaiさん許しません!!!!! pic.twitter.com/c9HECJJKnE
30分で解けるでしょ~とか思ってたら1時間15分弱かかってしまい、配信も気づいたら1時間半経ってました...
戒めのためにブログ形式で各問題の解説を残しておこうと思います。
なお、解答はすべてPython
の予定です。(C++はACした提出先リンクを張っておきます)
[追記]
また、YouTubeの私のチャンネルにてVTuber杯の全問題の解説動画を投稿しました。
もしよければ見て頂けると幸いです。
A - Crane and Turtle
鶴と亀の足の本数がそれぞれ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')
C++解答コード
B - Easy Linear Programming
$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))
C++解答コード
C - Echo
$N$文字からなる文字列$S$が与えられます。$S$を丁度半分に分割したときに同じ文字列ができますか?という問題。
Python
のslice
が便利なのでRTA?中はPython
で通しました。
C++
はs.substr
があるのでそれを使えばよいのですが、$N$が奇数の時に死ぬので条件分岐を忘れないようにしましょう(1WAした)。
Python解答コード
n = int(input()) s = input() print('Yes' if s[:n//2] == s[n//2:] else 'No')
C++解答コード
D - Digits
$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)
C++解答コード
E - Kagami Mochi
AtCoder Beginner Selectionでも紹介されている1問。
餅の半径が$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)
C++解答コード
F - Train Ticket
$+$, $-$を間に当てはめて答えが$7$になる計算式を求める問題。
Python
ではeval
という文字列をそのまま式として評価するやつがあるのでそれで一発でできます。
$+$, $-$を当てはめるのに条件分岐を書きまくるのは賢く見えないのでbit全探索を使うと良いです。
bit全探索についてはけんちょんさんがわかりやすく解説している記事があるのでダイレクトマーケティングしておきます。
けんちょんさんいつもお世話になっております。
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
- 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()
C++解答コード
G - Alchemist
$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++解答コード
H - 1-SAT
これまでの文字列の中に$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')
C++解答コード
I - : (Colon
今回のコンテストで最難関。
短針と長針の長さ$A, B$、現在の時刻$H, M$が与えられるので時計の長針と短針の位置を求めて頂点同士を結んだ長さを求めてくださいという問題。
数学ができると解けるが自分は競技プログラマーであるが数学者ではないので無理です。死にます。数学を避けてきた人生を悔やみます。
使うのはラジアン
と余弦定理
。
ラジアンとは(分かる人はスキップ)
ラジアンとは、「円(扇形)の孤の長さ(L)÷円の半径(r)」によって求められる値のことを指すらしいです。(出展)
180度を$\pi$として計算します。つまり360度は$2\pi$だし、60度は$\pi/3$。
余弦定理とは(分かる人はスキップ)
余弦定理は下の三角形$a,b,c$があった時に、
$$ c^{2} = a^{2} + b^{2} - 2ab * \cos(\gamma) $$
が成り立つことを指します。つまり、$c$を求めたかったら
$$ c = \sqrt(a^{2} + b^{2} - 2ab * \cos(\gamma)) $$
となります。ほえ~
で、どう使うの?
今回の問題で長針と短針の位置を角度で求めます。求めた後に頂点同士を結んだ長さを求めるのですが、その長さを知るためには余弦定理が必要です。
更に、余弦定理で必須となる$\cos$関数、様々なプログラミング言語で実装されていますが、引数として与えるのはラジアンである必要があります。
つまり、これらの流れを整理すると、
の流れです。
- Python解答コード
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))))
というわけで...
これはなぜか、それは、短針は長針にあわせて動くからです。
つまり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))))
C++解答コード
J - Write and Erase
一応ボス問、茶色ぱふぉ。
先ほどのH問題でもあったmap
やdefaultdict
を使う問題。
正直map
やdefaultdict
を知っていますか?僕は知っています。をするだけなのでするっと書けます。
被りの要素があったらその要素を±したり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)
C++解答コード
完走した完走
RTA配信自体は楽しかった(結果は酷かったけど)
この解説記事、書き終えた現在の時刻は深夜5時40分、長針10、短針4の時の頂点の間の距離は$9.414796255572739$だそうです。
とても疲れた。
結構明日のバイトを破滅させて時間をかけて丁寧に書いたのでたくさん読んでくれたらなぁと思います。
終わりに
Youtubeのチャンネル登録とTwitterのフォローよろしくお願いします!!!
ツカモさんにめざせ100人登録って言われちゃったので目指すしかないやんとなってます、今。