競プロ精進日記 #55
精進や復習で解いた問題を載せていきます。
yukicoder
No.205 マージして辞書順最小
入力された文字列に番兵を追加し、priority_queue に入れて操作します。
提出したソースコードNo.258 回転寿司(2)
dp をします。
pair 型の配列などでどの皿から取ったかを記録しておくことで復元ができます。
提出したソースコード
競プロ精進日記 #54
精進や復習で解いた問題を載せていきます。
Online Judge Verification Helper を導入していたら時間がなくなりました。。。
Library
yukicoder
- No.64 XORフィボナッチ数列
-> -> -> -> ... と繰り返すので
N を 3 で割った余りに応じて出力します。
提出したソースコード
競プロ精進日記 #53
精進や復習で解いた問題を載せていきます。
Codeforces Round #651 (Div.2)
- A. Maximum GCD
1 から順番に見ていき、ある数 x の倍数が n までに 2 個以上あるなら答えを x に更新します。
提出したソースコード
yukicoder
No.976 2 の 128 乗と M
変数 x に 1 を代入しておき、それに 2 をかけて、M の剰余をとることを 128 回繰り返します。
提出したソースコードNo.1047 Zero (Novice)
あらかじめ、 かつ のパターンと
かつ のパターンを弾きます。
あとは 10000 回程度もシミュレーションすれば十分です。
提出したソースコードNo.1072 A Nice XOR Pair
の時、 になることを使います。
map などに値の出現回数を記録しておき、数えていきます。
提出したソースコードNo.1077 Noelちゃんと星々4
dp をします。
提出したソースコードNo.1082 XORのXOR
式を変形すると 2 要素の xor を考えれば良いことがわかるので、全探索します。
提出したソースコード
AtCoder ABC171 参加記
AtCoder ABC171 に参加したので参加記を書こうと思います。
所感
A - E までの 5 完でした。
解いた問題の中では C 問題が最難関で泣きそうでした。
あったまったのでとても嬉しいです。
A - αlphabet
問題概要
- 英大文字または小文字が 1 文字入力される
- その文字が大文字か小文字かを答える
解説
a から z は順番に並んでいることを利用して、大文字か小文字か判定を行えば良いです。
提出したソースコード
B - Mix Juice
問題概要
- N 種類の果物の値段が与えられる
- その中から k 種類を選んだ時の最小コストを求める
解説
与えられた配列をソートして、小さい方から k 個の和をとります。
提出したソースコード
C - One Quadrillion and One Dalmatians /
問題概要
- a, b, ... z, aa, ab, ..., zz, aaa, aab, ..., zzz, ... というようなルールのもとで N 番目を求める
解説
今回の A - E までで最難関でした。
名前の文字数が増える時の最初の番号を求めて、その番号との差異 (変数 diff に代入します) を求めます。
番号 N の文字数が上記の計算で一緒にわかるため、あらかじめその文字数分 a を答えの文字列に代入しておきます。
その後、diff を 26 で割った余りを取って、26 で割るを繰り返して文字列を置き換えていきます。
答えの文字列を反転して出力すれば終わりです。
26 進法変換ですね。
提出したソースコード
D - Replacing
問題概要
- 長さ N の整数列が与えられる
- Q 回、全ての B という値を C という値に置き換える
- 各操作後の数列の和を求める
解説
あらかじめ与えられた数列の和を求めておき、map などで各数の個数を記録しておきます。
各クエリ毎に を引き、を足して答えを求めます。
B の個数を 0 にすることを忘れないようにしましょう。
提出したソースコード
E - Red Scarf
問題概要
- 長さ N の整数列 A が与えられる
- 別の長さ N の整数列 B があるが、値は不明である。
- A の i 番目の整数は i 番目以外の整数列 B の xor を取ったもの
- B の各要素を求める
解説
与えられた数列の xor をあらかじめ求めておき、
各数に対して上記の数との xor を求めていけば良いです。
提出したソースコード
競プロ精進日記 #51
精進や復習で解いた問題を載せていきます。
AtCoder
ABC157 E - Simple String Query
bit演算をしました。
提出したソースコードABC125 C - GCD on Blackboard
左右からの累積GCDを求めます。
提出したソースコード