競技プログラミングのための精進履歴をブログ形式で残していこうと思います。
目標は AtCoder 水色！
今のレートは茶色です。
本日の精進ツリーは以下のとおり。
今日は ABC170 までの茶 Diff 埋めがやっと終わりました！
精進ツリー
ABC173: D – Chat in a Circle
ABC173 より、D – Chat in a Circleを解きました。
難易度は茶色。
正直初見では手も足もでず、解説動画を見てようやく問題の趣旨が理解できました。
(初見だとインプットした順番に並べる必要があるのかと思ってた。)
感想としては、解法の正当性の証明を意識して練習していく必要があることを強く感じました。
・逆順ソートで大きい順に加算していけばいいのでは？(勘)
↓
・サンプル全部通った！やった！！
↓
・WA
という流れをやらかしてました。
結果的には、上記のロジックだと挿入する要素が 3 つを超えると厳密に成り立たなくなることがわかりました。
提出コードはこちら。
実装力が低くて C++ だと実行時エラーが無限に発生していたので、 Python で AC。
N = int(input())
A = list(map(int,input().split()))
"""
NOTE:
・最大の心地よさを持っているノードは始めに入れるのが良い
→ 以降は、大きい順に入れていく
要素は2分木で定義(両端に最大の値を置く)
→ 実際に木構造を作る必要なし
大きい順に入れた場合、適切に挿入していくことで、一つの大きい値を最大2回加算することができる
・適切に挿入先を選び取って行けば、常に得点の最大値は一つ前に入れた値と同じになる？
→ ならない
"""
"""
LOGIC:
1. 入力を降順にソートする
2. 先頭以降の要素2つが、その手前の最大要素の心地よさを得る(2こめ以降)
= 先頭から真ん中までのデータを足したもの * 2 にするとよい
"""
# 1. 入力を降順にソートする
A.sort(reverse=True)
ans = 0
if N % 2 == 0:
center = int(N / 2)
for a in A[1:center]:
ans += a
ans *= 2
else:
center = int((N-1) / 2)
for a in A[1:center]:
ans += a
ans *= 2
ans += A[center]
ans += A[0]
print(ans)
ABC171: D – Replacing
ABC171 より、D – Replacing を解きました。
難易度は茶色。
灰色に近い茶色ということもあり、楽勝でした。
計算量が O(QN) で、制約は 10^5 だったので、全部素直に実行しても解けそうな気はしましたが、要素の出現個数のカウントで解きました。
Python ライブラリの collections.Counter() をイメージして実装したら普通に解けました。
解いた後で解説記事を読んだところ、このような「各値が何個あるのか」という情報を表したものを「バケット」と呼ぶ見たいです。
バケットソートなどで使われるようです。
提出コードはこちら。
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using namespace std;
#define MAX 100010
#define NIL -1
using lint = long long int;
using P = pair<lint, lint>;
/*************************************************************************************
NOTE:
・単純に実行すると、O(QN)
数字の置き換えと加算 : N 回 * 操作の回数 : Q
・制約 10^5 なのでギリギリいけるのでは？
・と思ったけどやっぱりやめて要素のカウントで実装する
*************************************************************************************/
/*************************************************************************************
LOGIC:
1. 入力されたAの要素の個数を配列に格納(ついでに初期状態の総和も取得)
2. B と C の差分 * 個数 を総和に加算したものをさらに加算
3. 変換前の個数を 0 にし、その個数を変換後の個数に加算
*************************************************************************************/
lint arr[MAX];
int main()
{
lint N, Q;
cin >> N;
// 初期化
for (lint i = 0; i < MAX; i++) arr[i] = 0;
// 1. 入力されたAの要素の個数を配列に格納
lint sum = 0;
rep(i, N)
{
lint a;
cin >> a;
arr[a]++;
sum += a;
}
// 2. B と C の差分 * 個数 を総和に加算したものをさらに加算
// 3. 変換前の個数を 0 にし、その個数を変換後の個数に加算
cin >> Q;
rep(i, Q)
{
lint B, C;
lint tmp;
cin >> B >> C;
tmp = C - B;
sum += tmp * arr[B];
arr[C] += arr[B];
arr[B] = 0;
cout << sum << endl;
}
return 0;
}
ABC171: E – Red Scarf
同じく ABC171 より、E – Red Scarfを解きました。
難易度は緑に近い茶色。
正直初見では全然わかりませんでした。
XOR の和の性質についてちゃんと理解していなかったので、結構感動しました。
XOR和の性質ちゃんと理解してなかったけどまじで感動した。 pic.twitter.com/RZgw7C1cK9
— かしわば (@yuki_kashiwaba) March 2, 2021
XOR の性質をきちんと理解していて、問題の意図をしっかり読み解ければそこまで難しい問題じゃないという印象です。
今回は勉強不足でしたので、精進しましょう。
XOR の性質についてはこのページが参考になりました。
提出コードはこちら。
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using namespace std;
#define MAX 100010
#define NIL -1
using lint = long long int;
using P = pair<lint, lint>;
/*************************************************************************************
NOTE:
・全然わからんｗ
自分以外の全要素のxor結果が自分のスカーフに書かれることまではわかった
・XOR 和の性質を利用して方程式を作る
*************************************************************************************/
/*************************************************************************************
LOGIC:
1. N が偶数なので、1 ^ 2 ^ ... ^ N = a1 ^ a2 ^ ... aN という式が成り立つ
2. i1 ^ i2 ^ ... iN = a1 ^ a2 ^ ... aN となる整数の組を探す
3. sum から各 ai をそれぞれ XOR して引いた値が答えになる
*************************************************************************************/
int main()
{
lint N;
cin >> N;
vector<lint> data;
lint a, sum;
// 1. N が偶数なので、1 ^ 2 ^ ... ^ N = sum(a1..aN) という式が成り立つ
cin >> sum;
data.push_back(sum);
for(int i = 1; i < N; i++)
{
cin >> a;
sum ^= a;
data.push_back(a);
}
// 2. i1 ^ i2 ^ ... iN = a1 ^ a2 ^ ... aN となる整数の組を探す
// 3. sum から各 ai をそれぞれ XOR して引いた値が答えになる
for (int i = 0; i < N - 1; i++)
{
a = data[i];
cout << (sum ^ data[i]) << " ";
}
cout << (sum ^ data[N-1]) << endl;
return 0;
}
