AtCoder Beginner Contest 009

A - 引越し作業

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

高橋君は引越し作業の真っ最中です。荷物をすべてダンボールにまとめ終え、ちょうどいま家の前にトラックが到着したところです。高橋君は N 個あるダンボールをすべてトラックまで運ぶ必要があります。

ダンボールはとても重いですが、高橋君は力持ちなので片手で 1 つのダンボールを持つことができます。つまり、家とトラックの間を 1 往復するときに最大でそれぞれの手にダンボールを 1 個ずつ、合計で 2 個のダンボールをいちどに持って運ぶことができます。

ダンボールの個数が多いため、高橋君は N 個すべてのダンボールを運びきるために家とトラックの間を最低何往復しなければならないのかが気になりました。

入力

入力は以下の形式で標準入力から与えられる。

1 行目には、ダンボールの個数を表す整数 N (1 ≦ N ≦ 1,000) が与えられる。

出力

ダンボールをすべて運びきるために必要な最低の往復回数を 1 行に出力せよ。

出力の末尾にも改行をいれること。

入力例1

出力例1

2 個のダンボールは 1 回の往復で運びきることができます。

入力例2

出力例2

たとえば、はじめの 2 回は 2 個のダンボールを運び、最後の 1 回で残った 1 個のダンボールを運びます。

入力例3

出力例3

ダンボールが 1 個しかない場合でも 1 往復はする必要があります。

B - 心配性な富豪、ファミリーレストランに行く。

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

私は富豪だ。それも大富豪と言っていいぐらいお金を持っている。欲しいと思ったものはまずこの有り余るお金を使って買うことができる。しかし、この底の尽きないように思えるほどのお金でさえ人の心を買うことはできない。いくらお金があろうとも、ひとたび多くの庶民の反発を買ってしまえば、これまでのように生きていくことは難しくなるだろう。

この度私は庶民の気持ちを理解するため、初めてファミリーレストランという場所を訪れた。メニューを広げ、料理の内容とその金額を確かめると、なるほど驚きの安さである。どの料理の金額も取るに足らないようなものだから、とりあえず最も金額が高いものを選ぼうかと考えた。

しかし、考えてみれば、私は何のためにファミリーレストランに来たのであったか。庶民の気持ちを理解しようというのに、金額のことを考えずに最も高いものを選ぼうなどと、まるで意味がないではないか。ファミリーレストランに来たうえ、これ見よがしに最も高い料理を注文したとなったら、私の悪評が広まってしまう可能性だってある。

とはいえ、せっかくだから高いものを選んでその味をみてみたいというのも確かである。そうだ、そういうことなら、この店で 2 番目に高い料理を注文することにしよう。そう思って料理の金額を書き出してみたが、料理の種類が多いために 2 番目に高いものを探すのはなかなか骨が折れる。自分で探すかわりに、プログラムを書いてなんとかできないだろうか？

おっと、プログラムを書き始める前にひとつ言っておくが、最も高い金額の料理が複数あるときには注意してもらいたい。というのは、たとえば 4 種類の料理があり、それぞれの金額が 100 円、200 円、300 円、300 円であったときには、2 番目に高いものというのは 200 円の料理になるということだ。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1
A_2
:
A_N

1 行目には、料理の種類の個数を表す整数 N (2 ≦ N ≦ 100) が与えられる。
2 行目から N 行では、それぞれの料理の金額が与えられる。N 行のうち i 行目には整数 A_i (1 ≦ A_i ≦ 1,000) が書かれており、これは i 番目の料理の金額が A_i 円であることを表す。すべての料理の金額が同じであることはない。

出力

N 個の料理のうち、2 番目に高いものの金額を 1 行に出力せよ。

出力の末尾にも改行をいれること。

入力例1

出力例1

問題文にも出てきた例です。この場合、最も高い料理が 300 円で、その次に高い料理は 200 円のものになります。

入力例2

出力例2

入力例3

出力例3

C - 辞書式順序ふたたび

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

文字列の辞書式順序による比較についてはご存知だろうか？知らない場合は ABC007 の B 問題にその定義が載っているので読むとよいだろう。

今回は、この辞書式順序が重要な役割を果たす問題を解いてもらいたいと思う。

まず、英小文字（a-z）のみからなる N 文字の文字列 S が与えられる。S = S_1,\,S_2,\,...,\,S_N の文字を並び替えて作れるような文字列 T = T_1,\,T_2,\,...,\,T_N のうち、辞書順で最小になるようなものを求めてほしい。

ただし、並び替え方には 1 つだけ制限がある。別に整数 K が与えられ、元から位置の変わった文字の個数を K 以下にしなければならない。つまり、S_i ≠ T_i となるような（文字が不一致となるような） i （1 ≦ i ≦ N）の個数が K 以下であるような並び替え方しかできない。

※この問題は普段の ABC の C 問題に比べ難しくなっています。下のボタンを押すことで、ヒントとしてこの問題を解くためのアイデアの説明を読むことができます。じっくり取り組んでみてください。

入力

入力は以下の形式で標準入力から与えられる。

N K
S

1 行目には文字列の文字数を表す整数 N (1 ≦ N ≦ 100) と、位置を変えてよい文字数の上限を表す整数 K (0 ≦ K ≦ N) が与えられる。
2 行目には英小文字のみからなる N 文字の文字列 S が与えられる。

出力

S の文字を並び替えて作れるような文字列で、しかも元から位置の変わった文字の個数が K 個以下であるようなもののうち、辞書式順序で最も小さくなるような文字列を 1 行に出力せよ。

出力の末尾にも改行をいれること。

入力例1

3 2
abc

出力例1

abc

位置の変わった文字の個数は 2 以下でなければならないので、まったく並び替えをしなくても構いません。

このケースでは、並び替えをまったくしない場合が最も小さくなります。

入力例2

7 2
atcoder

出力例2

actoder

まず、T の先頭の文字を a （元の文字列 atcoder のうち最も小さいアルファベット）にできるかについて考えます。
- 今回は元から S の先頭の文字が a であるため、T の先頭の文字を a にすることができます。（たとえば並び替えをまったくせず S = T とすれば、T の先頭の文字を a にできることが確かめられます）
- なので、T の 1 文字目が a に決まります。
次に、2 文字目を c にできるかについて考えます。
- T の最初の 2 文字が ac であるとすると、この時点で少なくとも c は元の位置から場所が変わっています。
- なので、S の 3 文字目以降である coder に対して、まだ T に使っていないアルファベット deort をうまく並べて、位置の変わった文字の個数を 1 以下にできるかどうかを考える必要があります。
- 今回は deort を並び替えて toder とすれば T = actoder となって、位置の変わった文字の個数が 2 で済ませられます。
- よって 2 文字目が c と決まります。
次に、3 文字目を d にできるかについて考えます。
- T の最初の 3 文字が acd であるとすると、この時点で c と d は元の位置から場所が変わっています。
- なので、4 文字目以降ではこれ以上元の位置から文字を動かしてはいけないことになります。
- しかし、まだ T に使っていないアルファベット eort をどのように並べても、S の 4 文字目以降である oder とぴったり一致させることはできません。
- なので、3 文字目を d にすることはできません。
d がだめだったので、3 文字目に e を使えるかを考えます。
- さきほどの d の場合と同じように、3 文字目を e にすることもできません。
e もだめだったので、3 文字目に o が使えるかを考えます。
- ...
...

このようにして最初の文字から順に、まだ使っていない文字のなかで最も小さいアルファベットが使えるかどうか？を順に試していくことで答えである actoder に辿り着くことができます。

入力例3

7 7
atcoder

出力例3

acdeort

K = 7 なので、好きなように並び替えをして構いません。問題文にもあるように、この場合はアルファベット順に並べることで最小の文字列を作ることができます。

入力例4

10 3
helloworld

出力例4

dehloworll

D - 漸化式

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

数列 A はすべての要素が 32 ビットの符号なし整数で表現でき、その値は次のようにして決まる。

はじめの K 項 A_1,\,A_2,\,...,\,A_K は入力で与えられる。
A とは別に K 項の数列 C_1,\,C_2,\,...,\,C_K （こちらもすべての要素が 32 ビットの符号なし整数におさまる）が入力で与えられ、K+1 項目以降の A の値はこの C を用いて次のように計算される。
- N ≧ 1 に対し A_{N+K} = (C_1\,AND\,A_{N+K-1})\,XOR\,(C_2\,AND\,A_{N+K-2})\,XOR\,...\, XOR\,(C_K\,AND\,A_N)
- ただし AND はビットごとの論理積、 XOR はビットごとの排他的論理和を表す。

この数列 A の M 番目の値 A_M を求めるプログラムを作成せよ。

入力

入力は以下の形式で標準入力から与えられる。

K M
A_1 A_2 ... A_K
C_1 C_2 ... C_K

1 行目には、はじめに決まっている項の数を表す整数 K (1 ≦ K ≦ 100) および数列の求める項の番号を表す整数 M (1 ≦ M ≦ 10^9) が与えられる。
2 行目には、数列 A の最初の K 項が順に与えられる。A の値はすべて 32 ビット符号なし整数におさまる。
3 行目には、数列 A の K+1 項目以降を計算するときに使う数列 C の要素が順に与えられる。C の値はすべて 32 ビット符号なし整数におさまる。

出力

A_M の値を 1 行に出力せよ。

出力の末尾にも改行をいれること。

入力例1

3 5
10 20 30
7 19 13

出力例1

実際に A の値を計算していくと次のようになる。

A_4 = (7\,AND\,30)\,XOR\,(19\,AND\,20)\,XOR\,(13\,AND\,10) = 30
A_5 = (7\,AND\,30)\,XOR\,(19\,AND\,30)\,XOR\,(13\,AND\,20) = 16

入力例2

5 100
2345678901 1001001001 3333333333 3141592653 1234567890
2147483648 2147483647 4294967295 4294967294 3434343434

出力例2

1067078691

入力例3

30 999999999
11627 5078 8394 6412 10346 3086 3933 668 9879 11739 4501 6108 12336 8771 2768 2438 2153 7047 5476 313 1264 369 12070 10743 10663 747 370 4671 5235 3439
114 3613 3271 5032 11241 6961 3628 150 12191 2396 7638 3046 11594 8162 11136 786 9878 2356 11660 1070 3649 10882 9746 1415 3307 7077 9319 9981 3437 544