ABC115
やる気あんのかって感じですね。5ヶ月ぶりのコンテストです。10分ほどCF感を体験させてくれるAtCoderに圧倒的感謝しながら解きました。嫌味ではなくTLが面白かったです。
久しぶりの(ほんとにこの間ほとんどpythonは書かずたまーにjavascriptをちょっと書くくらい)コンテストだったので「標準入力とは…?」という感じでしたが、まあやってれば思い出すのは自転車みたいなあの感じに似てます。 終了ギリギリ9分前の滑り込みでDを通して全完でした。 以下問題の中身と提出コード
A - Christmas Eve Eve Eve
問題文:
A: Christmas Eve Eve Eve - AtCoder Beginner Contest 115 | AtCoder
提出:
https://abc115.contest.atcoder.jp/submissions/3739852
意訳:22から25の数値Dが入力されるので、22ならChristmas Eve Eve Eve,以降25をChristmasとしてクリスマスまでの日数分Eveを半角で区切って出力しなさいというもの。
AtCoderのA問題は標準入力と四則演算とif文が書ければ通せる問題(とどこかでみた)なのでかなり簡単、プログラミング自体が初心者の人向けと思っていました。
A問題にしてはわりと難しいです。
最初ifで書こうかな、でもめんどくさいしな、でもAだしな、でもEve追加するだけのほうが楽だしな なんて微妙に悩みました。結局25-D回"christmas"に"Eve"を追加する方法でACしましたがツイッターを見てるとifの人が多い…かも?
a = int(input()) s = [] s.append("Christmas") b = 25 -a for i in range(b): s.append("Eve") print(" ".join(s))
B - Christmas Eve Eve
問題文:
https://abc115.contest.atcoder.jp/tasks/abc115_b
提出:https://abc115.contest.atcoder.jp/submissions/3741452
意訳:N個のプレゼントを買いたい高羽氏は半額券を持っているので最も高価な商品に使いたい。総額はいくらでしょう。
単純に一番高い商品の価格を半分にして計算。 手順が3つあり、
- 全ての値を受け取る
- 合計金額を計算する
- 一番高い商品の値段を半額にする
が必要です。このうち最大値は入力を全て受け取るまでわからないので、入力を受け取りながら合計金額を計算し、最後に最大値の半分を合計から引きました。 ちなみにpythonにはsumという便利なやつがいて、これにリストやらを入れると合計を返してくれます。受け取るついでに全部足したのでsumは使いませんでしたが、合計値の変数名にsumが使えないのでいつもsuとかにしてます。同じ理由でmin maxもmiとかmaとか 音ゲーかな
n = int(input()) p = [] su = 0 for i in range(n): p.append(int(input())) su += p[-1] ma = max(p) su -=int(ma/2) print(su)
C - Christmas Eve
問題文:https://abc115.contest.atcoder.jp/tasks/abc115_c
提出:
https://abc115.contest.atcoder.jp/submissions/3742439
意訳:N個の中からK個選んだとき最小の差を出力
単純にソートして0個目からN-K個目までを順に見ていって、i個目とi+K-1個目の差の最小値をとればそれが答え。i+K個だとK個先のものをみてしまうので注意(こういう0-indexと1-indexが絡むの嫌い)
ソートをすることで今見ている2つの値は必ずそのK個の中で最も差が大きくなります。
ちなみにこれもpythonのリストは[0:3]で0番目から3個取ってくる、などができるので便利です(書いてる今思い出した)
n,k = list(map(int,input().split())) a = [0]*n for i in range(n): a[i] = int(input()) a.sort() ans = 9999999999999999999 for i in range(len(a)-(k-1)): x = a[i+k-1] - a[i] ans = min(ans,x) print(ans)
D - Christmas
問題:
https://abc115.contest.atcoder.jp/tasks/abc115_d
提出:
https://abc115.contest.atcoder.jp/submissions/3747754
意訳:意訳しにくいというか問題文を簡単に説明する的な感じでここ書いてるんですけど問題文読んだほうがわかりやすいです。
Lレベルのバーガーを作ります。レベル0はパティ一枚で、レベルが上がるごとにパン 前のレベルのバーガー パティ 前のレベルのバーガー パン となります。 NレベルバーガーのX層目(パンかパティ一枚につき一層)までを食べるとき、パティを何枚食べるでしょう。
これどこかに似たような問題があって、かなり昔に解いたことがあったのでそのソースなんとか改造してやろうと思ったら一時間くらいかかったのでやめました。
解説 (本家の解説は読んでないので自己流です)
簡単のためバーガーは上下ではなく左右に伸びると考えます。
灰色の部分は一つ前のレベルのバーガーです。実際に目で見るとわかりますが、バーガーは常に左右対称です。
レベル0以外のバーガーは全て最初と最後の層がパンであることがわかります。
これでまずXが1のときに答えが0になることがわかりました。
そしてパティの総数はレベルが1上がるごとに前のレベルの二倍+中央に追加する1枚であることがわかります。
また、バーガーの層の総数は前の層の総数の二倍+追加されるパン2とパティ1の3であることもわかります。
これで各層のパティの総数とバーガーの総数を簡単に求められることがわかります。
(競プロなので)パティの総数をa,バーガーの層の総数をsuとすると、
a[i] = a[i-1]*2 + 1 su[i] = su[i-1]*2 + 3
となります。それぞれの0番目は両方1で初期化します。
X=そのバーガーの層の総数のとき、答えは当然そのレベルのパティの総数です。
また、Xがバーガーの中央だった場合には前のレベルのパティの総数+中央のパティが答えになることがわかります。
これでまずXがそのレベルで追加された層だった場合に答えがいくつかがわかるようになりました。
次にそれ以外の場所にXがある場合について考えます。
これを見るとレベル2バーガーの9番目はレベル1バーガーの2番目ということがわかります。
言い換えると、中央以外の場所は前のバーガーのどこかに含まれるということですね。
これをたどると
このようにレベル0、パティ1枚の状態まで辿れました。
この操作を繰り返すことでどのレベルからでも必ずレベル0,もしくはそのレベルで追加された層に当たるため、答えが出ることがわかりました。
具体的な処理
現在のレベルを見て答えに追加するかの処理→レベルを1落としXの位置も変更する が基本の流れになります。
N=2,X=9のとき、Xが中央(7)より後ろにあるので前半に含まれているレベル1のパティの総数(3)を答えに足し、中央にあるパティを足すので現在の答えは4になります。
Xの位置はまずレベル1の層の総数(5)を引き、更に追加したパンとパティ(2)の合計7を引くのでX=2になります。
レベル2でやることが終わったのでレベルをひとつ落としN=1になり、例と同じN=1,X=2になりました。
レベル1の総数は5で、Xは2なのでバーガーの前半にいます。
バーガーの前半には前のレベルのバーガーが全て含まれている保証がないので、何もせずレベル1で追加したパン(1)をXから引き、レベルも1落とします。 N=0,X=1はパティです。Nが0になったときは答えに1を足してループや再帰から抜けます。これで解くことができました。
n,x = list(map(int,input().split())) a = [0 for i in range(n+1)] a[0] = 1 su = [0 for i in range(n+1)] su[0] = 1 for i in range(1,n+1): a[i] = a[i-1]*2 + 1 su[i] = su[i-1]*2 + 3 ans = 0 i = n jouken = False while True: if i == 0: if x ==1: ans += 1 break if x==1: break if x == su[i]: ans+=a[i] break if x == int(su[i]/2) +1: ans += a[i-1] +1 break elif x < int(su[i]/2)+1: i -= 1 x -= 1 elif x > int(su[i]/2)+1: i -= 1 ans += a[i]+1 x -= su[i] x -= 2 print(ans)
無限ループ書くときって結構勢いでバーっと書いてあとから考えて終了条件とか書きますよね?僕はそうなので当然joukenという変数を作ります。そしてコンテスト中は間に合うかどうか怪しいレベルなので自明にどこにも使ってないjoukenが存在を忘れられただ寂しく佇んでいることがよくあります。
あともう毎回x -= 1+1が足されそうで中々こう書けないのでいい加減挙動を覚えろ
半年前にブログ作ってた
こんなタイトルですが始めて続いたのが一ヶ月程度なのでほんともうクソ野郎です。 今日からちゃんと書きます。というか自分の実力がわからないので適当そうな問題いくつかやって測りたいと思います。 あとこれ以前に書いた記事は「今からがんばります!」という挨拶記事だったので恥ずかしすぎて消しました。半年頑張ってない。