Help us understand the problem. What is going on with this article?

javaでAtCoder Beginner Contest 156を解く

AtCoder Beginner Contest 156お疲れ様でした!
公式ページ

今回の自分の書いたコードはこちら
結果はA-DまでAC、Eはコンテスト終了後5分でACできました。悔しい:cry:

以下簡単に解説します。

問題A

引数にNとKが与えられ、
Kが10以下の場合にはNに100*(10-K)を足し算する問題。

100点問題っていう感じの難易度だったかと思います。

問題B

とある数字がK進法だと何桁かを出力する問題。
while文でぐるぐるまわして桁数をカウントしていけば大丈夫です。

while (n >= k) {
    n = n / k;
    digit++;
}

問題C

数直線上にN人の人がいて、その全員の移動距離の二乗和を最小にする点と二乗和を求める問題。
まずN人の人の中心となる座標を選定して(整数じゃないといけないのが注意)
あとは単純に二乗和を足し算しました。

N<=100となっていたので、計算量はあんまり気にしなくて大丈夫そうでした。

問題D

二項係数的な問題。以下の性質を使用します。

2^n = {}_n C _0 + {}_n C _1 + {}_n C _2 + ・・・\\
    = \sum_{k=0}^n {}_n C _k\\

すると、計算すべきは、

2^n - {}_n C _0 - {}_n C _a - {}_n C _b

となります。

問題E

法則を見つけられたのが終了10分前とかで、実装が間に合いませんでした、、
もともとN個の部屋に1人ずつ入っていて、1回移動が起こると、どこかの部屋が0になることに気づきました。

K個の部屋が0人の場合の組み合わせを計算してみました。すると、

{}_n C _k \times {}_{n-1} C _{n-1-k}

となります。具体的に言うと、n=6,k=2の場合は、

{}_6 C _2 \times {}_5 C _3

です。なので、この和をとって、

\sum_{i=0}^k \left( {}_n C _k \times {}_{n-1} C _{n-1-k} \right)

です。k=1のときとkが大きいときはまた別途考慮が必要でしたが、基本は以上で計算できました。
逆元を最初に計算して計算量の部分はうまく書けたのに、あとちょっとでした。

問題F

手つかずです。なんか入力も多くて難しい気がしたのでスルーしました。笑


レーティングは944→974。

全体的に少し難しかったように思えます。
E問題があともう少し・・・で手が届かず。でも、もう少しでE問題に手が届きそうだったので成長の実感は得られました!
次こそはE問題ACしたい・・・!

あと、TeX使って数式書いてみました。やっぱり美しいですね:chart_with_upwards_trend:

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした