AtCoder Beginner Contest 171 備忘録

AtCoder Beginner Contest 171 の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 171 - AtCoder

今回はABCD4完でした。

・A問題:αlphabet

大小いずれかのアルファベットが与えられるので、それが大文字なら 'A'、小文字なら 'a' を出力する。
asciiコードで判定すると分岐が単純になる。
例えば 'A' であれば 65 となり 'a' であれば 97 となる。
なので与えられた文字のasciiコードから65を引いた値が26未満か否かを判定すればよい。
Pythonであれば ord() で文字からasciiコードへ変換可能である。

解答例(Python)
https://atcoder.jp/contests/abc171/submissions/14586400

・B問題:Mix Juice

1〜NまでN種類の果物があり、それぞれ1個あたりp1〜pN円である。ここからK種類の果物を1個ずつ買うときの最小の金額を求める。
金額を最小化したいので価格の安いものから選べば良い。

解答例(Python)
https://atcoder.jp/contests/abc171/submissions/14587096

・C問題:One Quadrillion and One Dalmatians

1〜1000000000000001までの番号のついた犬の名前を番号に従って以下のルールで名前をつける。

・1,2,・・・,26番には順に 'a','b',・・・'z'と命名する。
・27,28,・・・,701,702番には順に
　'aa','ab',・・・'zy','zz'と命名する。
・703,704,・・・,18277,18278番には順に
　'aaaa','aaab',・・・'zzzy','zzzz'と命名する。
・18279番以降も同様のルールに従って命名する。

入力 N が与えられるので N 番の犬の名前を答える。
10進数を2進数に変換する要領で計算することで求められる。
10進数を2進数に変換するには x を2で割った余りを記録しておき商が1になったら商と余りを求めた順と逆に並べる事で求められる。
同様にN を26で割った余りを記録し、N が26以下になったら順に並べて出力すればよい。
この時、数値から文字列に変換する為にPythonではchr()を使う。これはA問題のord()とは逆にasciiコードを文字に変換する。ただし、求めた余りは26以下なので変換する際に96を足す必要がある(この問題では 1 の時に 'a' となり、asciiコードで 'a' は97の為)。
また、余りが0になる場合は26として扱う必要があるので注意する。
余りを求めた後に商を計算する際は単純に26で割ってしまうとNが26だった場合商が1になってしまい1桁余計に増えてしまう為(本来は'z'だが'az'となってしまう)、(N-1)//26とする必要がある。

解答例(Python)
https://atcoder.jp/contests/abc171/submissions/14590102

・D問題:Replacing

N個の正整数A1〜ANとなる数列Aがある。この数列に対して以下の操作をQ回行う。

・値が Bi である要素を全て Ci に置き換える

全てのi(1≦i≦Q)に対して、i回目の操作が行われた後の数列Aの全ての要素の和 S を求める。
N,Q≦10^5 なので愚直に処理しては間に合わない。
そこでi回目の操作で S がどれだけ変化するかを計算することにする。その為にまず数列Aの要素の和を求めておく。こうすることでi回目の操作で変化する量を足すだけで S を求めることができる。
i回目の操作で変化する量は、(Ci-Bi)*数列AiにあるBiの個数で求めることができるので、数列A・Bi・Ciの最大値+1個の要素を持つリストを0で初期化して作成しておき、数列Aの要素をindexとして個数をカウントしておく。こうすることでBiの個数をO(1)で求めることができる。

解答例(Python)
https://atcoder.jp/contests/abc171/submissions/14591918