AtCoder Beginner Contest 121
こんにちは
今日も元気に引きこもっています 笑1
なんかそこそこアクセスいただいてるみたいで、ありがとうございます。大体Twitterから来ていただいてるみたいですね。
(間違えてリンク踏んじゃった人は、ほんとごめんなさい。)
でもリアクションが全然なくて寂しかったので、自分で自分の記事にスターをつける遊びをしていました。
(みんな「うんこ」とかでいいのでコメントよろしくお願いします。。。。。)
AtCoderをやるぞ
AtCoderとは、国内最大規模のプログラミングコンテストを運営している企業様です。
プログラミングコンテストというのは、なんか数学っぽい問題をプログラミングの力で解いて、その実装の早さと正確さ、実行速度で順位付けして、他者を殴ろうという大会です。うそです。2
詳しく知りたい人は、競技プログラミングとは？メリットや初心者にもおすすめな理由も解説などを見てください。
まあ、引きこもりにはうってつけのパズルゲームみたいなものです。
AtCoderさんの粋な計らいで、過去に開催されたAtCoderのコンテストの過去問は全て閲覧することができ、実際に解いて自動で正当を判定してくれるシステムが用意されています。ありがたい話
今回は、初心者用のコンテスト3であるAtCoder Beginner Contestの過去問、AtCoder Beginner Contest 121を解いたので、それについてごちゃごちゃした思考を書きます。もし解いたことない人は、1回やってみるといいかもね。知らんけど
また、内容はかなり初級者の人向け(色で言うと灰色から緑よりの茶色ぐらい？)なので、ガチプロ様はここでブラウザバックするのが賢明かもしれません。ごめんさなさい…ごめんさなさい…叩かないで…。
使用言語はPythonです。まぁ提出はPyPy3なんですけどね〜〜🐍
以下、各問題の解説ですが今回は4問しかありません。(今は6問もあるよ！大変！)
基本的には問題のアルファベットが大きくなるほどむずいです。
ABC121-A
あ、ABCはAtCoder Beginner Contestの略です。
問題はこちらから→A - White Cells
黒く塗られる部分は、1行がw個分、1列がh個分、二重に塗られる箇所がh × wなので、$$ Hw + Wh - hw $$ですわね
これを全体のマスの総数$$ H \times W $$から引けばよろしいので、下のように書けばいいですね。
H,W = map(int, input().split()) h,w = map(int, input().split()) print(H*W - (H*w + W*h - h*w))
ABC121-B
問題はこちらから→B - Can you solve this?
「１つの提出されたソースコードセットに対して、問題に正答するかどうかを判定し、正答だったら正答数に+1する」ということをN回やりましょう。ざこがよお(イキリ)
n,m,c = map(int, input().split()) ans = 0 b = list(map(int, input().split())) for i in range(n): a = list(map(int, input().split())) total = 0 for j in range(m): total+=a[j]*b[j] total+=c if total > 0: ans+=1 print(ans)
ABC121-C
問題はこちらから→C - Energy Drink Collector
これは実際に高橋君になった気持ちになると考えやすいです。
みなさん、同じものが手に入るならとりあえず安く売ってるお店から買っていきますよね？？今回はそれをコードに起こせばおkです。
n,m = map(int, input().split()) Drink = [[] for i in range(n)] for i in range(n): Drink[i] = list(map(int, input().split())) # 値段安い店順にソート Drink.sort(key=lambda x: x[0]) ans = 0 # 総額 count = 0 # 総数 ind = 0 # 回る店 while count < m: p,num = Drink[ind] # 価格と数 if count+num < m: # まだ栄養足りねえ count+=num ans+=p*num ind+=1 # 次の店へ continue else: ans+=p*(m-count) # 栄養足りた count=m print(ans)
価格が安い順にお店のリスト(Dorink)をソートしてますが、ここで「Drink.sort(key=lambda x: x[0])」をいう風にlambda式を用いて、ソートに用いる値を指定しているのが、唯一のポイントでしょうか。(偉そうに言ってますが、ググりました。ごめんなさい。)
こちらのブログが大変参考になります。
ABC121-D
問題はこちらから→D - XOR World
え〜〜知らんけど 笑
愚直にAからBまでを排他的論理和で計算していくと、確実に死にます(遅すぎて時間制約に引っかかる。)
しょうがないから、実験をします。これは、本当に大事で、こういうとっつきにくい問題は、簡単そうな値を入力として入れてみて実験をすると、「案外楽じゃん？」となることが多くあります。4
下は、ぼくが机の上で実験した結果です。(は？)
左から右につながっています。
なので、Aに適当な偶数を入れてみると、$$f(A, A+1) = A \oplus (A+1) = 1 $$となります。(絶対)
いい予感がしますね(高揚感)
そのまま実験を続けてみると、
$$f(A, A+2) = f(A, A+1) \oplus (A+2) = 1 \oplus (A+2) = A+3 $$
$$f(A, A+3) = f(A, A+2) \oplus (A+3) = (A+3) \oplus (A+3) = 0 $$
$$f(A, A+4) = f(A, A+3) \oplus (A+4) = 0 \oplus (A+4) = A+4 $$
ところで、Aが偶数だからA+4は偶数ですよね？と言うことで、これと最初の式より、f(偶数, 偶数+1) = 1なので、
$$f(A, A+5) = f(A, A+4) \oplus A+5 = f(A+4, A+5) = 1$$
$$f(A, A+6) = f(A, A+5) \oplus A+6 = 1 \oplus (A+6) = A+7$$
$$f(A, A+7) = f(A, A+6) \oplus A+7 = (A+7) \oplus (A+7) = 0$$
$$f(A, A+8) = f(A, A+7) \oplus (A+8) = 0 \oplus (A+8) = A+8 $$
はい、完全に理解しましたね。
f(A, X)は、Xの周期が4でいい感じにわかります。(具体的には上の考察画像の左側を見てください。)
問題は、Aが奇数の時ですが、その時は、$$f(A, B) =A \oplus f(A+1, B)$$
とすれば、上の規則を使ってf(A+1, B)を求めた後、Aとの排他的論理和を1回取って終わりです。うおおおおおおおおおおおお
と言うわけでこの問題はO(1)。カスがよお(イキリ)
a,b = map(int, input().split()) if a%2 == 0: if (b-a)%4 == 0: print(b) elif (b-a)%4 == 1: print(1) elif (b-a)%4 == 2: print(b+1) else : print(0) else: if (b-a-1)%4 == 0: print(a^b) # aとbの排他的論理和 elif (b-a-1)%4 == 1: print(a^1) # aと1の排他的論理和 elif (b-a-1)%4 == 2: print(a^(b+1)) # aとb+1の排他的論理和 else: print(a) # aと0の排他的論理和
結果
ブログを書くのは本当にしんどい。
てかこのABC121、1時間で全完したんですけど誰か褒めてくれませんか？すごくね？(簡単だったかもしれないけど)
と言うわけでさいなら〜
P.S. がちで知ってたら教えて欲しいんですが、jupyter notebookでコーディングするとき改行込みの入力をバッと入れる方法はないんですか。。。？？？
