はじめに
赤コーダーの @e869120 さんが先日素晴らしい記事を書かれました。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【上級編：目指せレッドコーダー！】
この中でも特に「中級編」は緑コーダーの僕にとってまさに Looks Good To Me でしたので、
下記のような宣言のもと、記事内の「精選100問」を解く日々が始まりました・・。
精選100問というのがあるのをようやく知りました！水コーダーになりたいので今日から毎日埋めます！！！！！！！！！
— johannyjm1 (@johannyjm1) March 27, 2020
気付けば10日突破！10問解いたということで、記事を書こうと思った次第です。
解いた問題の備忘録、および思考の整理がメインではありますが、読まれた方に何か気付きがあればとても嬉しいです。
注意
「競技プログラミング的」な記法が多くなると思います。ご了承頂けると嬉しいです。
具体的にはC++ですと
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
を最初にテンプレートとして記述しています。
1日目 AOJ ITP1_7_B How many ways?
$1$ から $N$ までの数の中から、重複無しで3つの数を選びそれらの合計が $X$ となる組み合わせの数を求める
- $3 ≤ n ≤ 100$
- $0 ≤ x ≤ 300$
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
while(1){ // 入力数が決まってないため無限ループを作る
int n, x;
cin >> n >> x; // 入力受け取り
if(n==0) return 0; // 3 <= n なので n==0 きたら終わり
int res = 0; // 満たすものがない時は0
for(int a = 1; a <= n-2; ++a){ // 全ての組み合わせを調べるループ、重複と入れ替えを除くやつ
for(int b = a+1; b <= n-1; ++b){
for(int c = b+1; c <= n; ++c){ // 制約がもっと厳しい場合はこのループをなくしてc=x-a-bが「a,bと異なること」「1以上n以下であること」を調べる
if(a+b+c == x) ++res; // 条件を満たす時結果をインクリメント
}
}
}
cout << res << endl; // 結果を出力。クエリ問題は << "\n" の方がいいですか？
}
return 0;
}
Python
while(True): # 入力数が決まってないため無限ループを作る
n, x = map(int, input().split()) # 入力受け取り
if(n==0): break # 3 <= n なので n==0 きたら終わり
res = 0 # 満たすものがない時は0
for a in range(1, n-1): # 全ての組み合わせを調べるループ、重複と入れ替えを除くやつ
for b in range(a+1, n):
for c in range(b+1, n+1): # 制約がもっと厳しい場合はこのループをなくしてc=x-a-bが「a,bと異なること」「1以上n以下であること」を調べる
if(a+b+c == x): res += 1 # 条件を満たす時結果をインクリメント。 ++res としないように
print(res)
【100日後に水コーダーになる緑コーダー 1日目】
— johannyjm1 (@johannyjm1) March 27, 2020
How many ways?
全探索、ささっと三重ループを書きましたが二重でいいですね。まあn~100なので・・
今更AOJ登録しました。入力の終わり方が慣れなかったりジャッジが速すぎてちびりそうになったりしました。https://t.co/N4g7dCDvRx
2日目 AtCoder Beginner Contest 106 B - 105
$1$ 以上 $N$ 以下の奇数のうち, 正の約数を ちょうど $8$ 個持つようなものの個数を求める
- $N$ は $1$ 以上 $200$ 以下の整数
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int divisor(int num){ // 約数の個数を返してくれる関数
int ret = 0;
for(int i = 1; i <= num; ++i){
if(num%i == 0) ++ret;
}
return ret;
}
int main() {
int n;
cin >> n;
if(n <= 105){ // 出力例1 に「ただ一つ」というヒントがあるので大人しく従います。
if(n == 105) cout << 1 << endl;
else cout << 0 << endl;
return 0;
}
int res = 1; // 105です
for(int num = 106; num <= n; ++num){
if(divisor(num)==8 && num%2==1) ++res; // 「約数の個数がちょうど8の奇数」をそのまま実装
}
cout << res << endl;
return 0;
}
Python
def divisor(num): # 約数の個数を返してくれる関数
ret = 0
for i in range(1, num+1):
if(num%i == 0): ret += 1
return ret
n = int(input())
if(n <= 105): # 出力例1 に「ただ一つ」というヒントがあるので大人しく従います。
if(n==105): print(1)
else: print(0)
exit()
res = 1
for i in range(106, n+1):
if(divisor(i) == 8 and i%2==1): res += 1 # 「約数の個数がちょうど8の奇数」をそのまま実装
print(res)
【100日後に水コーダーになる緑コーダー】
— johannyjm1 (@johannyjm1) March 28, 2020
2日目 105
1月に解いたはずの問題なのに全くやった覚えがない。しかし提出コードを見てみると内容ほぼ一緒。これはあるあるですか？
n<=200なので約数の個数は愚直にループを回しているけど制約増える場合は素因数分解を使おう。https://t.co/oduVa3xTGr
3日目 AtCoder Beginner Contest 122 B - ATCoder
文字列 $S$ の部分文字列のうち最も長い 「'A', 'C', 'G', 'T' 以外の文字を含まない文字列」の長さを求める
- $S$ は長さ $1$ 以上 $10$ 以下の文字列である。
- $S$ の各文字は英大文字である。
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
string s;
cin >> s;
int n = s.size(); // 文字列の長さを取得しておく
int res = 0; // 条件になければ0
for(int i = 0; i < n; ++i){ // Sの部分文字列を全探索するループ：重複を許す（i==jの時は1文字の部分文字列とする）が入替を許さないループ
for(int j = i; j < n; ++j){
string sub = s.substr(i, j-i+1); // i文字目からからj文字目までの部分文字列
int num = sub.size();
bool flg = true; // ACGT文字列フラグ
for(int k = 0; k < num; ++k){
char c = sub[k]; // 部分文字列の文字cのうち
if(c!='A' && c!='C' && c!='G' && c!='T') { // 一つでもACGT以外があったら
flg = false; // flgをfalseにして
break; // つぎにいく
}
}
if(flg) res = max(res, num); // ACGT文字列の長さnumの最大値を保持する
}
}
cout << res << endl;
return 0;
}
Python
s = input()
n = len(s) # 文字列の長さを取得しておく
res = 0 # 条件になければ0
for i in range(n): # Sの部分文字列を全探索するループ：重複を許す（i==jの時は1文字の部分文字列になる）が入替を許さないループ
for j in range(i, n):
sub = s[i: j+1] # i文字目からからj文字目までの部分文字列
flg = True
for c in sub: # Python的for文
if(c not in ['A', 'G', 'C', 'T']): flg = False # こちらも、in はこういう時便利です
if(flg): res = max(res, len(sub)) # ACGT文字列の長さnumの最大値を保持する
print(res)
【100日後に水コーダーになる緑コーダー】
— johannyjm1 (@johannyjm1) March 29, 2020
3日目 ATCoder
めっちゃ懐かしい！人生初参加ABC122のB問題です、部分文字列の全探索でバグらせがちです。難し目のB???https://t.co/iVB7BGwVMT
当時のぼくはPythonで割とイケてる感じで解いてた。退化？😇https://t.co/zUS9d1PDZE
割とイケてる実装。はたして？
Python その2
s = input()
s_str = '' # からの文字列を作る
for c in s: # sを1文字ずつ走査
if(c in ('A', 'C', 'G', 'T')): s_str += c # cがACGTどれかならs_strに追加
else: s_str += ' ' # それ以外の時はスペースを追加 → ACJKAJAGTみたいなのは'AC A AGT'みたいになる
if(s_str.split() == []): print(0) # ACGTが含まれない文字列はこちらになる
else: print(len(max(s_str.split(), key = len))) # ['AC', 'A', 'AGT']みたいになるのでこの配列の要素のうち「文字列の長さの最大値」を出力する
4日目 パ研合宿2019 第3日「パ研杯2019」 C - カラオケ
$N$ 人が $M$ 曲のどれかを歌う。番号 $i$ の生徒が曲 $j$ を歌うと $Ai,j$ 点を取る。
- $M$ 曲の中から $2$ つの曲を選ぶ（それぞれ $T1$ と $T2$ とする）
- それぞれの生徒が曲 $T1$ と曲 $T2$ の両方を歌う
- 各生徒の得点はその生徒が歌った $2$ つの曲の点数のうち高い方となる
- グループの得点は，生徒 $1,2,...,N$ の得点の合計となる
そのときグループの得点として考えられる最大の値を求める
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll n, m;
cin >> n >> m;
vector<vector<ll>> a(n, vector<ll>(m)); // (n, m) の2次元配列を宣言
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
cin >> a[i][j];
}
}
ll res = 0; // 制約より負の得点はないので0で初期化
for(int one = 0; one < m; ++one){ // 一曲目、決め打ち
for(int two = 0; two < m; ++two) { // 二曲目、決め打ち
ll sum = 0; // 得点の合計、0で初期化
for(int i = 0; i < n; ++i){
sum += max(a[i][one], a[i][two]); // 「2つの曲の点数のうち高い方」をそのまま実装
}
res = max(res, sum); // この一曲目・二曲目の選び方だとsum点。resに最大値を保持
}
}
cout << res << endl;
return 0;
}
Python
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)] # 行数しか指定要らない例のやつ
res = 0 # 制約より負の得点はないので0で初期化
for one in range(m): # 一曲目、決め打ち
for two in range(m): # 二曲目、決め打ち
sum = 0 # 得点の合計、0で初期化
for i in range(n):
sum += max(a[i][one], a[i][two]) # 「2つの曲の点数のうち高い方」をそのまま実装
res = max(res, sum) # この一曲目・二曲目の選び方だとsum点。resに最大値を保持
print(res)
【100日後に水コーダーになる緑コーダー】
— johannyjm1 (@johannyjm1) March 30, 2020
4日目 カラオケ
最初生徒ごとに曲を選べると誤読し「？？」となっていた。全探索とわかっているのでこれは実装するだけって感じですかね。
てかこんなコンテスト見たことなかった。いろんなコンテストがあるんですねえhttps://t.co/Foa0xbdYMU
5日目 AtCoder Beginner Contest 095 C - Half and Half
$A$ ピザ、$B$ ピザ、$AB$ ピザ $1$ 枚あたりの値段はそれぞれ $A$ 円、$B$ 円、$C$ 円
$A$ ピザ $X$ 枚と $B$ ピザ $Y$ 枚を用意するために最小で何円が必要か？
- $1≤A,B,C≤5000$
- $1≤X,Y≤105$
- 入力中のすべての値は整数である。
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int a, b, c, x, y;
cin >> a >> b >> c >> x >> y;
int res = a*x + b*y; // 条件を満たす買い方のうちABピザの枚数(*2)を全探索する。ABピザを一切買わない場合を一旦答えにする（これを大きい値にして、for ループを0からにしてもよい）
for(int i = 1; i <= max(x, y); ++i){ // 全部ABピザでまかなう時は x,yの内多い方分買うことになる
int ab = i*2; // ABピザを買う枚数奇数枚買うことはないので2倍
int cand = c*ab + a*max(0, x-i) + b*max(0, y-i); // i枚分はABピザになるので-i 負の値にはならない（あまりになる）ので0とのmaxをとる
res = min(res, cand); // 候補との最小値を保持
}
cout << res << endl;
}
Python
a, b, c, x, y = map(int, input().split())
res = a*x + b*y # 条件を満たす買い方のうちABピザの枚数(*2)を全探索する。ABピザを一切買わない場合を一旦答えにする（これを大きい値にして、for ループを0からにしてもよい）
for i in range(1, max(x, y)+1): # 全部ABピザでまかなう時は x,yの内多い方分買うことになる
ab = i*2 # ABピザを買う枚数奇数枚買うことはないので2倍
cand = ab*c + a*max(0, x-i) + b*max(0, y-i) # i枚分はABピザになるので-i 負の値にはならない（あまりになる）ので0とのmaxをとる
res = min(res, cand) # 候補との最小値を保持
print(res)
【100日後に水コーダーになる緑コーダー】
— johannyjm1 (@johannyjm1) March 31, 2020
5日目 Half and Half
この前のリンゴ問題(ABC160E)を少しだけ彷彿とさせるピザ問題。昔解いたときはO(1)でバグらせながら解いていた。今回は全探索ということでABピザの数を変えてき、バグらせながら解いた。（おい）https://t.co/FhSMb9y5YO
6日目 三井住友信託銀行プログラミングコンテスト2019 D - Lucky PIN
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n;
cin >> n;
string s;
cin >> s;
int res = 0;
for(int i = 0; i < 1000; ++i){ // PINの組み合わせは高々1000通りなのでこちらを全探索
char one = '0' + (i/100); // （左から数えて）一つ目
char two = '0' + (i%100/10); // 二つ目
char three = '0' + (i%10); // 三つ目。これらがこの順番にsに登場するかを調べる
bool flg1 = false; // 一つ目がある
bool flg2 = false; // 二つ目が一つ目より右側にある
bool flg3 = false; // 三つ目が一つ目、二つ目より右側にある
int ptr = 0; // 現在の走査位置を表すポインタ
for(int j = ptr; j < n-2; ++j){ // 一つ目を探すループ（n-2までみてなかったらあってもNG）
if(s[j] == one){
flg1 = true; // 一つ目があった
ptr = j+1; // 二つ目は一つ目のひとつ右から走査開始
break; // これをしないと一番右側の一つ目を採用しちゃう
}
}
for(int j = ptr; j < n-1; ++j){ // 一つ目より右から二つ目を探す
if(s[j] == two){
flg2 = true;
ptr = j+1;
break;
}
}
for(int j = ptr; j < n; ++j){ // 二つ目より右から三つ目を探す
if(s[j] == three) {
flg3 = true;
break;
}
}
if(flg1 && flg2 && flg3) ++res; // 条件を満たせばflgが全部trueとなりその時だけ結果をインクリメント
}
cout << res << endl;
return 0;
}
Python
n = int(input())
s = input()
res = 0
for i in range(1000): # PINの組み合わせは高々1000通りなのでこちらを全探索
one = str(i//100) # （左から数えて）一つ目
two = str(i%100//10) # 二つ目
three = str(i%10) # 三つ目。これらがこの順番にsに登場するかを調べる
flg1 = False
flg2 = False
flg3 = False
ptr = 0 # 現在の走査位置を表すポインタ
for j in range(ptr, n-2): # 一つ目を探すループ（n-2までみてなかったらあってもNG）
if(s[j] == one):
flg1 = True # 一つ目があった
ptr = j+1 # 二つ目は一つ目のひとつ右から走査開始
break # これをしないと一番右側の一つ目を採用しちゃう
for j in range(ptr, n-1): # 一つ目より右から二つ目を探す
if(s[j] == two):
flg2 = True
ptr = j+1
break
for j in range(ptr, n): # 二つ目より右から三つ目を探す
if(s[j] == three):
flg3 = True
break
if(flg1 and flg2 and flg3): res += 1 # 条件を満たせばflgが全部trueとなりその時だけ結果をインクリメント
print(res)
※ちなみにこの解法はPython3だとTLEになってしまうのでPyPy3で提出しましょう😭
6日目 Lucky PIN
— johannyjm1 (@johannyjm1) April 1, 2020
銀行コンは温まった覚えがあるので好き。でもEの帽子の問題意味わからな過ぎて解けた人頭おかしいと思っている。
PINの種類が高々1000通りなので全探索ができる。PINの数字が左から順番に出てこれば ++個数 こういうのってうまい実装あるんですかね・・？https://t.co/MOedHOP96T
7日目 第６回日本情報オリンピック 本選（オンライン） C - 最古の遺跡
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n;
cin >> n;
vector<int> x(n), y(n); // 座標
set<pair<int, int>> st; // 座標のセット、後で「この座標があるかどうか？」参照するため高速で動作する必要がある
for(int i = 0; i < n; ++i){
cin >> x[i] >> y[i];
st.insert(make_pair(x[i], y[i]));
}
int res = 0;
for(int i = 0; i < n-1; ++i){ // i,jの二重ループで「二本の柱＝正方形の1辺候補」を全探索
for(int j = i+1; j < n; ++j){
pair<int, int> vec1 = make_pair(x[j] - x[i], y[j] - y[i]); // 2本の柱からベクトルを作っておく
int s = (x[j]-x[i])*(x[j]-x[i]) + (y[j]-y[i])*(y[j]-y[i]); // 1辺がわかれば面積がわかるので先に計算しておく
if(s < res) continue; // 暫定最大面積に及ばなければこの後は見る必要がない
vector<pair<int, int>> vec2_cand(2); // 1辺が決まるとベクトルでいう始点から伸びるもう1辺は2通りしかない
vec2_cand[0] = make_pair(vec1.second, -vec1.first); // 2つ目のベクトル、候補1（ベクトル1に対して内積が0になるベクトルが二つある）
vec2_cand[1] = make_pair(-vec1.second, vec1.first); // もう一つ
for(auto vec2: vec2_cand){ // 二つの候補について調べる
if(st.find(make_pair(vec2.first + x[i], vec2.second + y[i])) != st.end()){ // ベクトル2が存在するか。※ベクトル1の始点を加えて座標に変換することを忘れない
pair<int, int> vec3 = make_pair(vec1.first + vec2.first, vec1.second + vec2.second); // もし存在するなら、ベクトル3はベクトル1 + ベクトル2で確定なのでそれが存在するかを調べる
if(st.find(make_pair(vec3.first + x[i], vec3.second + y[i])) != st.end()){
res = max(res, s); // ベクトル3の座標もあればそこに正方形を作れるので暫定TOPと戦う
}
}
}
}
}
cout << res << endl;
return 0;
}
Python
n = int(input())
xy = [tuple(map(int, input().split())) for _ in range(n)] # 「この座標が存在するか？」を高速に「setへのin」で確かめたいのでhash可能なtuple型で受け取る
st = set() # 座標をセットで保持
for i in range(n):
st.add(xy[i])
res = 0
for i in range(n-1): # i,jの二重ループで「二本の柱＝正方形の1辺候補」を全探索
for j in range(i+1, n):
vec1 = xy[j][0] - xy[i][0], xy[j][1] - xy[i][1] # 2本の柱からベクトルを作っておく
s = vec1[0]*vec1[0] + vec1[1]*vec1[1] # 1辺がわかれば面積がわかるので先に計算しておく
if(s < res): continue # 暫定最大面積に及ばなければこの後は見る必要がない
vec2_cand = (vec1[1], -vec1[0]), (-vec1[1], vec1[0]) # 1辺が決まるとベクトルでいう始点から伸びるもう1辺は2通りしかない（ベクトル1に対して内積が0になるベクトルが二つある）
for vec2 in vec2_cand: # 二つの候補について調べる
if(((vec2[0] + xy[i][0]), (vec2[1] + xy[i][1])) in st): # ベクトル2が存在するか。※ベクトル1の始点を加えて座標に変換することを忘れない
vec3 = vec1[0] + vec2[0], vec1[1] + vec2[1] # ベクトル3はベクトル1 + ベクトル2で確定なのでそれが存在するかを調べる
if(((vec3[0] + xy[i][0]), (vec3[1] + xy[i][1])) in st): # vec3 exists
res = max(res, s) # ベクトル3の座標もあればそこに正方形を作れるので暫定TOPと戦う
print(res)
7日目 最古の遺跡
— johannyjm1 (@johannyjm1) April 2, 2020
苦戦した。枝刈りしたn^3でTLE, 2つ決まったらベクトルの合成やん！→TLE, そもそも一つの辺決まったら2通りしか正方形ないやん！残りの頂点はにぶたんで探そう→なぜかTLE(!?!?!), 結局同じ解法をPythonのstr()つかったhash裏技で通しました。。。https://t.co/fbeVBElGSR
→ tuple も set に入れられるのでそちらに直しています。
8日目 square869120Contest #6 B - AtCoder Market
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll n;
cin >> n;
vector<ll> a(n), b(n);
rep(i, n) cin >> a[i] >> b[i];
ll res = 1LL << 60;
for(int i = 0; i < n; ++i){ // スタートとゴールの位置を「商品のあるマス」に決めうちし全探索このとき「s==g」は許容するが「g < s」は除外する
for(int j = 0; j < n; ++j){
ll s = a[i];
ll g = b[j];
if(g < s) continue;
ll cost = 0;
for(int k = 0; k < n; ++k){ // n人の買い物コストを計算していく
ll l = a[k]; // 左の商品と
ll r = b[k]; // 右の商品のスタート、ゴールとの位置関係で場合わけする
if(s<=l && r<=g) cost += g-s; // 商品が両方s〜gにある時
else if(l<=s && r<=g) cost += (s-l)*2 + g-s; // lの商品がsより左（lを買って一旦sに戻る）
else if(s<=l && g<=r) cost += r-s + r-g; // rの商品がgより右（rを買ってからgにいく）
else if(l<=s && g<=r) cost += (s-l)*2 + (r-g)*2 + g-s; // 商品が両方外側（遠回りする）
}
res = min(res, cost); // 暫定最小コストと戦う
}
}
cout << res << endl;
return 0;
}
Python
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
res = 1 << 60
for i in range(n): # スタートとゴールの位置を「商品のあるマス」に決めうちし全探索このとき「s==g」は許容するが「g < s」は除外する
for j in range(n):
s = ab[i][0]
g = ab[j][1]
if(g < s): continue
cost = 0
for k in range(n): # n人の買い物コストを計算していく
l = ab[k][0] # 左の商品と
r = ab[k][1] # 右の商品のスタート、ゴールとの位置関係で場合わけする
if(s<=l and r<=g): cost += g-s # 商品が両方s〜gにある時
elif(l<=s and r<=g): cost += (s-l)*2 + g-s # lの商品がsより左（lを買って一旦sに戻る）
elif(s<=l and g<=r): cost += r-s + r-g # rの商品がgより右（rを買ってからgにいく）
elif(l<=s and g<=r): cost += (s-l)*2 + (r-g)*2 + g-s # 商品が両方外側（遠回りする）
res = min(res, cost) # 暫定最小コストと戦う
print(res)
8日目 AtCoder Market
— johannyjm1 (@johannyjm1) April 3, 2020
サンプルから「スタートとゴールは品物のマスから選ぶのが最適」とエスパー。n~30 なので O(n^3) でも余裕、未証明でAC。でもこれコンテスト中にちゃんと証明する人いるんか？？いるんやろうなあ。https://t.co/eCR8blEoMO
9日目 第７回日本情報オリンピック 予選（オンライン） D - 星座探し
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int m;
cin >> m;
vector<int> xm(m), ym(m);
vector<pair<int, int>> vec(m);
for(int i = 0; i < m; ++i) {
cin >> xm[i] >> ym[i];
vec[i] = make_pair(xm[i] - xm[0], ym[i] - ym[0]); // x0, y0を基準に全ての座標の相対位置（ベクトル）を保存しておく
}
int n;
cin >> n;
vector<int> xn(n), yn(n);
set<pair<int, int>> xyn;
for(int i = 0; i < n; ++i) {
cin >> xn[i] >> yn[i];
xyn.insert(make_pair(xn[i], yn[i])); // 星の座標のペアを全てsetに入れ高速に参照できるようにしておく
}
for(int i = 0; i < n; ++i){
int x = xn[i]; // n個の星のうちi番目が星座の構成要素0番目であると仮定、全探索する
int y = yn[i];
bool flg = true; // 星座の構成要素が全てあれば守られるフラグ
for(int j = 0; j < m; ++j){
pair<int, int> nxt = make_pair(x+vec[j].first, y+vec[j].second); // i番目の星が星座の構成0番目だとするとj番目の構成要素はi番目の星+j番目の相対位置ベクトル
if(xyn.find(nxt) == xyn.end()) { // そんな星がない時は
flg = false; // フラグを折って
break; // 処理を中止する
}
}
if(flg){
cout << xn[i] - xm[0] << " " << yn[i] - ym[0] << endl; // 見つかったら平行移動分を表示してプログラムを終える
return 0;
}
}
return 0;
}
Python
m = int(input())
xym = [tuple(map(int, input().split())) for _ in range(m)] # listでもいい
vec = [(xym[i][0] - xym[0][0], xym[i][1] - xym[0][1]) for i in range(m)] # x0, y0を基準に全ての座標の相対位置（ベクトル）を保存しておく
n = int(input())
xyn = [tuple(map(int, input().split())) for _ in range(n)] # setに入れたいのでタプル
xyn_st = set()
for xy in xyn:
xyn_st.add(xy) # 星の座標のペアを全てsetに入れ高速に参照できるようにしておく
for i in range(n):
x = xyn[i][0] # n個の星のうちi番目が星座の構成要素0番目であると仮定、全探索する
y = xyn[i][1]
flg = True # 星座の構成要素が全てあれば守られるフラグ
for j in range(m):
nxt = x+vec[j][0], y+vec[j][1] # i番目の星が星座の構成0番目だとするとj番目の構成要素はi番目の星+j番目の相対位置ベクトル（この書き方だとtuple型で代入される）
if(nxt not in xyn_st): # そんな星がない時は
flg = False # フラグを折って
break # 処理を中止する
if(flg):
print(xyn[i][0] - xym[0][0], xyn[i][1] - xym[0][1]) # 見つかったら平行移動分を表示してプログラムを終える
exit()
9日目 星座探し
— johannyjm1 (@johannyjm1) April 4, 2020
最古の遺跡と似ている感じする。 std::set はランダムアクセスできずbinary_search は遅いかも？という知見を得たので .find() を使う作戦です。
一つ目の星を固定してそこからの相対位置関係を持っておく、あとは全探索で写真に星座の構成が全部あるかをみるhttps://t.co/TVTV8VOhQV
10日目 AOJ ALDS1_5_A Exhaustive Search
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i) cin >> a[i];
unordered_set<int> st; // aの組み合わせ足し算で作れる数字全てを保持する。高速で参照したいのでunordered_setを採用
for(int i = 0; i < (1<<n); ++i){ // bit全探索、2進数で表した時1になるaを足す
int sum = 0;
for(int j = 0; j < n; ++j){
if(i & (1<<j)) sum += a[j]; // 足す
}
st.insert(sum); // 作った数字を挿入、setなので重複は消える
}
int q;
cin >> q;
for(int _ = 0; _ < q; ++_){ // Python的な。idxに意味がないので _ にしてみました
int m;
cin >> m;
if(st.count(m)) puts("yes"); // unoredered_setの検索は.count()が使いやすいと聞きました
else puts("no");
}
return 0;
}
Python
n = int(input())
a = list(map(int, input().split()))
st = set() # aの組み合わせ足し算で作れる数字全てを保持する。Pythonのsetは早いぞ
for i in range(1<<n): # bit全探索、2進数で表した時1になるaを足す
sm = 0
for j in range(n):
if(i & (1<<j)): sm += a[j] # 足す
st.add(sm) # 作った数字を挿入、setなので重複は消える
q = int(input())
m = list(map(int, input().split()))
for i in range(q):
if(m[i] in st): print('yes')
else: print('no')
10日目 総当たり
— johannyjm1 (@johannyjm1) April 5, 2020
基本問題とあるので「bit全探索最初は意味分からんかったけど今なら2sで書けるわ😇」→TLE、n<=20 だけどクエリが200なのでそれはそうで、最近何かとお世話になる std::unordered_set さんに事前に作れる数字を全部入れておきクエリをO(1)で処理、無事AC！https://t.co/15JmcJolVH
11日目〜
11日目 AtCoder Beginner Contest 128 C - Switches
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> s(m); // 電球ごとに見るべきスイッチ、数が変わるので1軸目だけ決める
vector<int> k(m); // 電球ごとに見るべきスイッチの数、あとでみたいので電球ごとに保持
for(int i = 0; i < m; ++i){
cin >> k[i];
vector<int> sk(k[i]);
for(int j = 0; j < k[i]; ++j) cin >> sk[j];
s[i] = sk; // これのがpush_back(sk)より早いですか？
}
vector<int> p(m);
for(int i = 0; i < m; ++i) cin >> p[i];
int res = 0;
for(int i = 0; i < (1<<n); ++i){ // n個のスイッチのon/off状態をbit全探索
vector<int> on(n, 0); // スイッチの状態 off: 0
for(int j = 0; j < n; ++j){
if(i & (1<<j)) on[j] = 1; // bitが立っているところ→j番目が on: 1
}
bool all_on = true; // 全ての電球が点灯する時のみ守られるフラグ
for(int j = 0; j < m; ++j){ // 電球について調べるので j < m（上と違う。。）
int on_num = 0; // 点灯条件を愚直に実装
for(int l = 0; l < k[j]; ++l){ // 見るべきスイッチの数k[j]（kが既出のためl。。。）
if(on[s[j][l] - 1]) ++on_num; // 見るべきスイッチがonならon_num（対象スイッチのon数）をインクリメント
}
if(on_num%2 != p[j]) { // そのまま実装「見るべきスイッチのonの個数を2で割ったあまりがp[j]のとき点灯」なのでこれを満たさない時
all_on = false; // フラグが折れます
break; // フラグが折れたらこれより先は見る必要なし
}
}
if(all_on) ++res; // このスイッチのパターンで全て点灯、つまりフラグが守られたら結果をインクリメント
}
cout << res << endl;
return 0;
}
Python
n, m = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(m)] # ひとまず行ごと全部受け取っちゃう
p = list(map(int, input().split()))
res = 0
for i in range(1<<n): # n個のスイッチのon/off状態をbit全探索
on = [0 for _ in range(n)] # スイッチの状態 off: 0
for j in range(n):
if(i & (1<<j)): on[j] = 1 # bitが立っているところ→j番目が on: 1
all_on = True # 全ての電球が点灯する時のみ守られるフラグ
for j in range(m): # 電球について調べるので range(m)
on_num = 0 # 点灯条件を愚直に実装
for s in ks[j][1: ]: # 0番目は見るべきスイッチの数だが必要ないので1~ をみる
if(on[s-1]): on_num += 1 # 見るべきスイッチがonならon_num（対象スイッチのon数）をインクリメント
if(on_num%2 != p[j]): # そのまま実装「見るべきスイッチのonの個数を2で割ったあまりがp[j]のとき点灯」なのでこれを満たさない時
all_on = False # フラグが折れます
break # フラグが折れたらこれより先は見る必要なし
if(all_on): res += 1 # このスイッチのパターンで全て点灯、つまりフラグが守られたら結果をインクリメント
print(res)
11日目 Switches
— johannyjm1 (@johannyjm1) April 6, 2020
悪名高き(?) Switchesです。実装するだけといえばそれはそうなんですが問題文だったり入力だったりがリアルタイムで遭遇したくない格好をしています。添字も多くなりがちでバグらせがちです。誰が考えてんこの設定は！！！！アナログ回路で実装できるかな？https://t.co/eVIYzyJ8aM
12日目 AtCoder Beginner Contest 002 D - 派閥
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, m;
cin >> n >> m;
set<pair<int, int>> relations; // 大活躍のpair set あとで「知り合い関係があるか？」のチェックを高速に行う
for(int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
--x; // 入力が1-indexなのでデクリメントしておく
--y; // 同上
relations.insert(make_pair(x, y)); // x < yの制約なので (x, y)の挿入で十分
}
int res = 0;
for(int i = 1; i < (1<<n); ++i){ // 「n人がこの派閥に属するかどうか」をbit全探索する
int num = 0; // その派閥の人数
vector<int> faction; // 派閥の英語（今知りました）
for(int j = 0; j < n; ++j){
if(i & (1<<j)){
faction.push_back(j); // bitが立ったらこの派閥のメンバー。factionにpushする
++num; // bitが立っているところを数えたらその派閥の人数になる（後からfaction.size()しても良いが・・）
}
}
if(num < res) continue; // 派閥の人数が暫定トップに満たなければ以下の処理は必要なし
bool flg = true; // 派閥の条件を満たす時守られるフラグ
for(int j = 0; j < num-1; ++j){ // 派閥のメンバー間の関係を全探索
for(int k = j+1; k < num; ++k){
pair<int, int> relation = make_pair(faction[j], faction[k]); // あるメンバー間の関係pair
if(relations.find(relation) == relations.end()) { // が、知り合いsetの中に存在しなければ
flg = false; // フラグを折って
break; // 処理を終える
}
}
if(!flg) break; // 二重ループなので、こちらでも終わらせておく
}
if(flg) res = max(res, num); // この派閥が存在すれば暫定トップと戦う
}
cout << res << endl;
return 0;
}
Python
n, m = map(int, input().split())
relations = set() # 大活躍の tuple set あとで「知り合い関係があるか？」のチェックを高速に行う
for i in range(m):
x, y = map(int, input().split())
x -= 1 # 入力が1-indexなのでデクリメントしておく
y -= 1 # 同上
relations.add((x, y)) # x < yの制約なので (x, y)の挿入で十分
res = 0
for i in range(1, 1<<n): # 「n人がこの派閥に属するかどうか」をbit全探索する
num = 0 # その派閥の人数
faction = [] # 派閥の英語（さっき知りました）
for j in range(n):
if(i & (1<<j)):
faction.append(j) # bitが立ったらこの派閥のメンバー。factionにappendする
num += 1 # bitが立っているところを数えたらその派閥の人数になる（後からlen(faction)しても良いが・・）
if(num < res): continue # 派閥の人数が暫定トップに満たなければ以下の処理は必要なし
flg = True # 派閥の条件を満たす時守られるフラグ
for j in range(num-1): # 派閥のメンバー間の関係を全探索
for k in range(j+1, num):
relation = faction[j], faction[k] # あるメンバー間の関係tuple
if(relation not in relations): # が、知り合いsetの中に存在しなければ
flg = False # フラグを折って
break # 処理を終える
if(not flg): break # 二重ループなので、こちらでも終わらせておく
if(flg): res = max(res, num) # この派閥が存在すれば暫定トップと戦う
print(res)
12日目 派閥
— johannyjm1 (@johannyjm1) April 7, 2020
初見でUnionFind的な？と思いましたがお互いに知っている、みたいな条件とn<=12みたいな制約からまあbit全探索ですよね。となりました。ここでも std::set<pair<int, int>> が活躍しています。もっと簡潔な方法があるのでは？とも考えています。https://t.co/B6EpPC1Up7
13日目 第７回日本情報オリンピック 予選（オンライン） E - おせんべい
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int r, c;
cin >> r >> c;
vector<vector<int>> a(r, vector<int>(c)); // 盤面
vector<int> black(c, 0); // その「列」の黒いおせんべいの数を持つことでO(c)で出荷可能枚数の最大値を求める
for(int i = 0; i < r; ++i){
for(int j = 0; j < c; ++j){
cin >> a[i][j];
black[j] += a[i][j]; // 白は0 黒は1なのでそのまま足せば黒の枚数になる
}
}
int res = 0; // 最初はどの行も裏返さなかった場合の出荷可能枚数を調べる(bit全探索のループを0からにしても良いが・・)
for(int i = 0; i < c; ++i){
res += max(black[i], r - black[i]); // 任意の列を裏返せるので「max(裏返した時の黒枚数, 裏返さなかった時の黒枚数）」が「その列の出荷可能枚数の最大値」になる
}
for(int i = 1; i < (1<<r); ++i){ // 「ある列を裏返すかどうか」をbit全探索
vector<int> black_diff(c, 0); // その「列」の黒枚数がこの操作どれだけ変わるか
for(int j = 0; j < r; ++j){
if(i & (1<<j)){
for(int k = 0; k < c; ++k){
black_diff[k] += a[j][k] ? -1: 1; // 元々黒なら−1、白なら+1を加算
}
}
}
int sum = 0;
for(int j = 0; j < c; ++j){
sum += max(black[j]+black_diff[j], r-(black[j]+black_diff[j])); // どれだけ変わるかを反映させて同じように出荷可能枚数の最大値を計算する
}
res = max(res, sum); // 暫定トップと戦う
}
cout << res << endl;
return 0;
}
Python
r, c = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(r)] # 盤面
black = [0 for _ in range(c)] # その「列」の黒いおせんべいの数を持つことでO(c)で出荷可能枚数の最大値を求める
for i in range(r):
for j in range(c):
black[j] += a[i][j]
res = 0 # 最初はどの行も裏返さなかった場合の出荷可能枚数を調べる(bit全探索のループを0からにしても良いが・・)
for i in range(c):
res += max(black[i], r - black[i]) # 任意の列を裏返せるので「max(裏返した時の黒枚数, 裏返さなかった時の黒枚数）」が「その列の出荷可能枚数の最大値」になる
for i in range(1<<r): # 「ある列を裏返すかどうか」をbit全探索
black_diff = [0 for _ in range(c)] # その「列」の黒枚数がこの操作どれだけ変わるか
for j in range(r):
if(i & (1<<j)):
for k in range(c): # 元々黒なら−1、白なら+1を加
if(a[j][k]): black_diff[k] -= 1
else: black_diff[k] += 1
sm = 0
for j in range(c):
sm += max(black[j]+black_diff[j], r-(black[j]+black_diff[j])) # どれだけ変わるかを反映させて同じように出荷可能枚数の最大値を計算する
res = max(res, sm) # 暫定トップと戦う
print(res)
こちら、ツイートでは余裕wwなどと言っていますがPythonだと間に合いません・・PyPyのが10倍くらい早いのでそちらで
13日目 おせんべい
— johannyjm1 (@johannyjm1) April 8, 2020
片方の次元が小さかったこういうこともできるんやね！という問題。探索するたびにc(~10000)回分計算するので全部で10^7くらい？しかし割と余裕で間に合っています。
黒のおせんべいの数を保持し裏返す行によってどれだけ変化するかを併せて再び数える。https://t.co/syNxiqVyEG
14日目 square869120Contest #4 B - Buildings are Colorful!
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, k;
cin >> n >> k;
vector<ll> a(n);
for(int i = 0; i < n; ++i) cin >> a[i];
ll res = 1LL << 60; // 最小値が知りたいので答えの初期値はでかい数で
for(int i = 0; i < (i<<n); ++i){ // k 個のビルが条件を満たすとし、その選び方をbit全探索する。選んだビル数がk以外の時はcontinueという方法で
if(i%2 == 0) continue; // 先頭のビルを見ないのは不可能なので一つ目のbitは必ず立っている必要がありその必要十分条件は「奇数であること」（最初のbitが1）
vector<int> use_idx(n, 0); // どのビルに着目するか 0: 無視
int use_cnt = 0; // 着目するビルの数 kになる時だけ考える
for(int j = 0; j < n; ++j){
if(i & (1<<j)){
use_idx[j] = 1; // 1: 着目
++use_cnt; // ＋＋着目
}
}
if(use_cnt != k) continue; // k個のビルに着目することだけを考える
ll sum = 0; // 一つ目、先頭。いじる必要はないのでコストも0
ll mx = a[0]; // 先頭の高さが暫定最大の高さ
for(int j = 1; j < n; ++j){ // 二つ目からみていく
if(use_idx[j]){ // このビルが着目するビルならば
if(a[j] <= mx) { // もし暫定最大の高さがこのビル以上の高さならば
sum += mx+1 - a[j]; // このビルは最大＋１の高さまで最低伸ばす必要があり
++mx; // その高さが暫定最大の高さになる
}
}
mx = max(mx, a[j]); // 着目するビルかどうかにかかわらず暫定最大高さは更新される（これをif(use)内に書くとだめだよ。見ないからと言って透明にはならないので）
}
res = min(res, sum); // 全てのコストを計算したら暫定最安コストと戦う
}
cout << res << endl;
return 0;
}
Python
n, k = map(int, input().split())
a = list(map(int, input(). split()))
res = 1 << 60 # 最小値が知りたいので答えの初期値はでかい数で
for i in range(1<<n): # k 個のビルが条件を満たすとし、その選び方をbit全探索する。選んだビル数がk以外の時はcontinueという方法で
if(i%2 == 0): continue # 先頭のビルを見ないのは不可能なので一つ目のbitは必ず立っている必要がありその必要十分条件は「奇数であること」（最初のbitが1）
use_idx = [0 for _ in range(n)] # どのビルに着目するか 0: 無視
use_cnt = 0 # 着目するビルの数 kになる時だけ考える
for j in range(n):
if(i & (1<<j)):
use_idx[j] = 1 # 1: 着目
use_cnt += 1 # ＋＋着目
if(use_cnt != k): continue # k個のビルに着目することだけを考える
sm = 0 # 一つ目、先頭。いじる必要はないのでコストも0
mx = a[0] # 先頭の高さが暫定最大の高さ
for j in range(1, n):
if(use_idx[j]): # 二つ目からみていく
if(a[j] <= mx): # もし暫定最大の高さがこのビル以上の高さならば
sm += mx+1 - a[j] # このビルは最大＋１の高さまで最低伸ばす必要があり
mx += 1 # その高さが暫定最大の高さになる
mx = max(mx, a[j]) # 着目するビルかどうかにかかわらず暫定最大高さは更新される（これをif(use)内に書くとだめだよ。見ないからと言って透明にはならないので）
res = min(res, sm) # 全てのコストを計算したら暫定最安コストと戦う
print(res)
14日目 Buildings are Colorful!
— johannyjm1 (@johannyjm1) April 9, 2020
貪欲っぽいですが確かにbit全探索だと簡潔に書ける気がする。
一番左を必ず含んだK個のビルを選ぶ方法を全探索する。最小コストなので今のmaxを持っておきそれ+1まで選んだビルを伸ばす。選んでないビルでもmax更新されるの注意やで。https://t.co/bvvw5p87fr
15日目 AtCoder Beginner Contest 145 C - Average Length
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// ある座標とある座標の距離を計算して返す関数。
double calc_dist(pair<double, double> current, pair<double, double> nxt){
return pow((nxt.first - current.first) * (nxt.first - current.first) + (nxt.second - current.second) * (nxt.second - current.second), 0.5);
}
int main() {
int n;
cin >> n;
vector<pair<double, double>> xy(n); // next_permutaionを使いたいのでvectorに座標ペアを入れた。
for(int i = 0; i < n; ++i){ // x(n), y(n)のように別で持つ場合はインデックスの順列を作れば良さそう
double x, y;
cin >> x >> y;
xy[i] = make_pair(x, y);
}
sort(xy.begin(), xy.end()); // ここ重要です。「next_permutationは辞書順で次の順列を作る」ため、予め辞書順で一番すなわち昇順のソートをしておく必要がある。
int n_fact = 1; // 組み合わせがn!通りなので平均値を出すためにはn!で割りたい→事前に計算しておく。
for(int i = 1; i <= n; ++i) n_fact *= i; // そのままの実装。
double sum = 0.0; // 全ての組み合わせの距離をここに足していって、最後にn!で割る
do{ // 訪れる座標の順番を順列全探索する
pair<double, double> current = xy[0]; // この選び方における1番目の座標。始点にする
double dist = 0.0; // この選び方における合計距離
for(int i = 1; i < n; ++i){
pair<double, double> nxt = xy[i]; // 行先の座標。
dist += calc_dist(current, nxt); // 距離を計算して合計距離に足す。
current = nxt; // 行先を始点にして次の座標へ
}
sum += dist; // この選び方の合計距離を全体の合計距離に足す
} while(next_permutation(xy.begin(), xy.end()));
printf("%.10f\n", sum / n_fact); // 小数表示。入力がcinなのにprintf()はきもいですか？
return 0;
}
Python
from itertools import permutations # 順列全探索のためitertoolsのpermutationsをimport
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)] # C++のnext_permutationと異なり辞書順で次を作るわけでないのでソートは不要
n_fact = 1 # 組み合わせがn!通りなので平均値を出すためにはn!で割りたい→事前に計算しておく。
for i in range(1, n+1): n_fact *= i # そのままの実装。
sm = 0 # 全ての組み合わせの距離をここに足していって、最後にn!で割る
for itr in permutations(xy): # 訪れる座標の順番を順列全探索する
x, y = itr[0] # この選び方における1番目の座標。始点にする
dist = 0 # この選び方における合計距離
for nx, ny in itr[1: ]: # 組み合わせの2番目の要素以降の処理、中身をそのままnx, nyに入れる
dist += ((nx-x)**2 + (ny-y)**2) ** 0.5 # Pythonならではの記法？
x, y = nx, ny # これも。一気にcurrentにnxtを渡せる
sm += dist # この選び方の合計距離を全体の合計距離に足す
print(sm / n_fact) # 何もしなくても少数で出てくれます
15日目 Average Length
— johannyjm1 (@johannyjm1) April 10, 2020
いわゆるネクパミュ練習問題？？しかし答えが合わず「next_permutation()は辞書順で次の順列を作る」関数だということを知った・・。ちゃんとソートしてAC。https://t.co/onp1ApcFpD
この問題、順列全探索じゃなくても解ける。（解いた記憶はない）https://t.co/UIums4hy9I
おわりに
どんどん難しくなりそうで震えています。