怠惰の累積和

技術/競プロ/怪文書/虚無

AtCoder Beginner Contest 148

 

A - Round One

問題概要

 1,2,3の中から異なる2数が与えられるので残りの1つを出力せよ。

atcoder.jp

 

解法

 6からAとBを引くとできるし、A^Bでもできる。どっちも天才解法。思いつくのには1333年くらいかかりそう(適当)。僕はif文3つ書きました。やるだけ。

atcoder.jp

 

B - Strings with the Same Length

問題概要

 文字列が2つ与えられるので先頭から交互に出力せよ。

atcoder.jp

 

解法

 for文を使えますか?僕は使えます。やるだけ。

atcoder.jp


C - Snack

問題概要

 パーティーにA人かB人どちらかが参加する。どちらの人数が来ても均等にお菓子を配り切れるような最小のお菓子の個数を求めよ。

atcoder.jp

 

解法

 LCMですか?LCMですね。ライブラリーを貼るだけ。やるだけ。

 

atcoder.jp

 

D - Brick Break

問題概要

 数列中から任意の個数の要素を取り除いて出来上がった数列が1から等差1の等差数列になるようにするとき、取り除く要素の個数の最小値を求めよ。

atcoder.jp


解法

 いわゆるスターリンソート(cfを参照)。先頭から順に見ていき、答えを求めるだけ。やるだけ。

cf)https://qiita.com/Sirloin/items/c9e5c74be3366df65bce

atcoder.jp

 

E - Double Factorial

問題概要

 整数nについて、関数f(n)n<2なら1、otherwiseならf(n)=nf(n-2)を満たすとき、f(n)の結果の数値は末尾に0が何個続くか求めよ。

atcoder.jp


解法

 10=2*5なので、f(n)=nf(n-2)=n*(n-2)*f(n-4)=...=n*(n-2)*(n-4)*(n-6)*...の中の素因数のmin( (2の個数の総和),(5の個数の総和) )で決定される。

 n*(n-2)*(n-4)*(n-6)*...のように降順に並んでいるとき、明らかに素因数としての5の個数の総和のほうが素因数としての2の個数の総和よりも少ない。よって、nまでに5が何個含まれるかどうかを調べることで答えがわかる。ただし、nが奇数の場合、n*(n-2)*(n-4)*(n-6)*...の中に素因数2は含まれないので、答えは必ず0となる。実質中学受験算数。

atcoder.jp

 

F - Playing Tag on Tree

問題概要

 高橋くんと青木くんが木の上でどちらも同じ頂点に来るまで鬼ごっこをする。高橋くんはできるだけゲームを遅く、青木くんはできるだけ早く鬼ごっこを終わらせようとするように動くとき、ゲーム終了までに青木くんが動く回数を求めよ。

atcoder.jp


解法

 両者の戦略を考慮すると、木上の頂点のうち、高橋君の初期位置からの最短距離が青木君の初期位置からの最短距離よりも短い頂点の集合のうち、最短距離が最も遠いものの最短距離が答えとなることがわかる。よって、dijkstraを2回行ってやると解ける。atcoder.jp