草体にぼ日記

だらだらと

2月22日(23?)日の精進 & コンテスト振り返り。

まえがき

こんにちは、春休みに入ってしまったので毎週の楽しみがコンテスト以外なにもない状態になってしまいました。

ちょっとまって、これだと毎日大学に行くのが楽しみだった。みたいになってますね。それは偽です。

競技プログラミング以外なにもしなくていいこの春休みの残り一ヶ月。爆精進していきましょう!!!

さて、今日はABC156がありましたので、それの感想と今日の精進録を付けていきます。

今日学んだこと

  • 人間関係と精進量には負の相関関係がある(とはいえ人付き合いは楽しい)

->ほどほどにね

コンテスト感想

本番は3完で、パフォーマンスは980くらい、レートは微増でした。(良い)

さて、前回はA,B、C実装が重たそうでDに行く。D解けなくてCに戻る。ということをしてしまって、タイムが落ちて冷えそうになってしまったので、今回はAから順に解いていくことにしました。

結果的にはDもEも僕のレートぐらいの人だと難しめの問題なので、3完早解きで冷えることのない回でしたので、Cまで解いた後にEに行ったのは(結果論ですが)問題ありませんでした。

これがDまで早解き回だと撃沈ですね。 解法が分かるけど実装が難しそうっていう問題は説いたほうが良さそうです。

今回、Cまで順番に解いたと言いましたが、実は嘘で、B,C,Aの順番に提出しました。 理由は後ほど述べます。

ABC 156 A-Beginner

[if文,日本語]

 解き方

Nが10以上の場合はRを出力, そうでない場合は内部レーティングを計算して出力する。 という問題ですね。

k < 10 のとき
表示レーティング = 内部レーティング - 100 * ( 10 - K) 
式変形をして

内部レーティング = 表示レーティング + 100 * ( 10 - K) 

こうなります。僕はこれを、内部レーティングが与えられて表示レーティングを出すものと勘違いしていたため、サンプルが合わず、サンプル間違ってね??ってなってしまい、Aを提出せずB,Cに進んでました。

日本語を読むのは日本に住んでからまだ20年しか経っていない僕には難しいですね。

ABC 156 B-Digits

[K進数,whileループ] 10進数で表された整数Nは、K進数だと何桁で表せるか. ちょっとウッってなりましたけど、殴りました。

解き方

進数変換を考えました。

2進数に変換する時、整数Nが

a0 ~ ak は1か0
N = (2^0 * a0) + (2^1 * a1) + (2^k * ak) 

このように表せる時、10進数の整数Nは ak ak-1 ... a0 で表せますよね。

例えば N = 14のとき

14 = (2^0 * 0) + (2^1 * 1) + (2^2 * 1) + (2^3 * 1)
   = 0 + 2 + 4 + 8 

よって、14(10) = 1110(2) 
(k)はk進数であることを意味します。

このような考え方を元に、K進数では、何桁使えばNを表せるか考えます。

この時重要なのが Nを表すには何桁必要か

と考えるのではなく Nを表すのにA桁必要な時、A桁ではいくつの整数までを表すことが出来るかを考えると楽です。

例えば、5を二進数で表すと101となりますが、これは 11(2)では3までしか表せなくて、 111(2)なら7まで表せる。

だから5は3桁で表せる。というふうに考えた方が楽です。

よって、K進数で1桁なら0、1,2,…、k-1k-1までを。 2桁ならK * K - 1まで表せる。 これをwhileループを使って求めて貰います。

ちょっと日本語が怪しいので要約すると

K進数で、a桁使って表せる最大の数は Ka - 1です.

(例、二進数では、3桁なら 23 - 1 = 8 - 1 = 7まで表せる)

int main() {
    int N , K ;
    cin >> N >> K ;
    int count = 0 ; 
    ll pos = -1;//count桁で表せる数の最大
    while(pos < N){
        count ++ ;
        pos = pow(K,count) - 1 ;
    }
    cout << count << endl;
}

なんか考察が無駄に長いですね…

ABC 156 C-Rally

[全探索]

1 <= N <= 100
1 <= Xi <= 100

座標の値はたかだか100個なので、 座標1のとき、2の時、...,100の時と何も考えずに全探索しちゃえばいいです。

O(N2)ですね。

ちなみにこれ、まともに考えようとすると、X0 ~ Xnの平均値を見ればいいんですかね?中央値?知らない。

ABC156 E- Roaming

[nCm,操作,組み合わせ、数え上げ、日本語]

[問題文] n 個の部屋がある建物があります。 部屋には 1 から n までの番号が付いています。 建物の各部屋から、他の任意の部屋に移ることが可能です。 ここで、建物のある部屋 i にいる人が、別の部屋 j ( i ≠ j) に移ることを 人の移動 と呼ぶことにします。 最初、建物の各部屋には人が 1 人いました。 このあと現在までに、人の移動がちょうど k 回起きたことが分かっています。 現在、建物の各部屋にいる人の数の組合せとして、ありえるものは何通りでしょうか。 ( 10 9 + 7) で割った余りを求めてください。

競技日本語コンテストですね。

大事な文章が一つあります。

建物の各部屋にいる人の数の組み合わせとして、ありえるものは何通りでしょうか

こいつです。

何がいいたいかというと、部屋1,2,3があります。a,b,c君の3人がいます。 この時

1の部屋に0人 2の部屋にb,c君 ,3の部屋にa君がいる。っていう状況と

1の部屋に0人、2の部屋にa,b君、3の部屋にc君がいる。とい言う状況は数え上げとしてはどちらも同じだということです。

中にいる人が誰かは問題になっていません。

解き方

0人の部屋に出来るところがいくつあるか

まず、全部の部屋(n部屋)を全部0人の部屋にすることは出来ません。 n人は全員路頭に迷うことになってしまうからです。

よって、0人の部屋は最大でも(n-1)部屋しか出来ない。

さらに、最初各部屋には1人ずついて、一回の操作で0人の部屋を一つ作ることが出来るので、 k回の操作でk個0の部屋を作ることが出来ます。(k < n のとき)

以上より、 0人の部屋は、 min(n-1,k)(以下、このminを取った数字をkとする)部屋以下なら作ることが出来ます。

よって、0人の部屋の個数をzとして z = 0 、z =1 , ..., z = k の時それぞれに対して、そのような部屋の組は何通りあるかを数えて行きます。

(ちなみに、k <= (n-1) < 2 * 105なので計算量は問題ありません)

Q . z = i 、すなわち、0人の部屋をi個作る時、そのような部屋の組み合わせが何個あるか。

まず、n個ある部屋の中から、どのi個の部屋を0人の部屋にするかを決めます。 nCi通りです。

次に、0にするi個の部屋を移動させるのですが、この、0人になる部屋にいた人たちは、(n-i)部屋の中から好きな部屋に移動します。

移動後を考えます

a[j] := 移動後、j番目の部屋にいる人の数とします。

テキトウに

0 , 1 , 2, 0 , 0 , 3 , 4 , 0 , 0 , 0

こんな感じの人数分布になってるとします(この時、z = 4 , n = 8)

0以外の場所、すなわちa[1],a[2],a[5],a[6]だけ考えます。この4つ(n - z)

a[1] , a[2] , a[5] , a[6]は全部1以上であって、a[1] + a[2] + a[5] + a[6] = 8でないといけません。

そのように分けるのが何通りあるかを数えればいい。

多分これは ( n - 1 ) C (z)です。

まあなんか別に僕が分かってるから書かなくてもいいんだけど、一応説明しますか。 a[1] + a[2] + a[5] + a[6] = 8

a[1] >= 1 , a[2] >= 1 , a[5] >= 1 , a[6] >= 1

この条件を満たすようなa[1],a[2],a[5],a[6]の組は何通りあるか。

○○○○○○○○ 

このように8つの○と

| | |

3つの|すなわち仕切りを用意しました。

したら、○の間の7箇所から3箇所選んで仕切りを入れます。

○|○○○|○○|○○

こんな感じ。 この図はa[1] = 1, a[2] = 3 , a[5] = 2 , a[6] = 2に対応してます。 よって、8人を4部屋に分ける(ただし、どの部屋も一人以上いる)これは、n-1 C zで求められます。

補足、 厳密には(n-1) C (n-z-1) = (n-1) C ( n-1 - ( n- z - 1) ) = (n-1) C (z) って感じで式変形

(意味: 仕切りをおける場所n-1箇所に、 0人にならない部屋の数-1 ( n - z - 1)個仕切りを置く。

あとがき

まあ、文章が狂ってても俺が分かればヨシ!!

最近のコンテストは良問揃いでうれしいですね。

本番で通せないのは悔しいけど、解説見て学ぶものが多い回って気がするので。

水色なりたいにゃ〜♡