競プロで2つの格子点を通る直線を一意に表したい

競プロをやってると、2つの格子点(a, b), (c, d)を通る直線を考えたいことがよくあります。

そのときに、複数の直線集合の中から同一の直線をグルーピングしたい場合というのもよくあります。

そういうときに、同じ直線は同じ表現になり、異なる直線は異なる表現になるような表現があると便利です。

そういう方法を紹介します。

表現方法

簡単です。直線を、次のような形で表します。

• ax + by + c = 0
• ただし、gcd(a, b) = 1
• (gcd(0, x) = gcd(x, 0) = x とする)

よくある直線の表現ですが、gcd(a, b) = 1という条件が加わっています。

この条件を加えることで、全ての(2つの格子点を通る)直線は一意に表すことができます。 (証明は省略します)

作り方

格子点(p, q), (r, s)を通る直線の表現を計算してみましょう。

まず、dx = r - p, dy = s - q とおくと、a = -dy, b = dx です。

すると、c = -a - b となります。

よって、(a, b, c) = (-dy, dx, -a - b) と求まりました。

使用例

(a, b, c)の値は直線によって一意なので、(a, b, c)をtupleにしてmapなどで持つと、いい感じに同一な直線のグルーピングができます。

例題: ABC220-G Isosceles Trapezium

法線を求める問題ですが、考え方は同じです。

Xcode(v12.5) で 'bits/stdc++.h' file not found が出たときの対処法

「さて、今日もいつも通り競プロするか。
とりあえずAtCoder Problemsを開いてXcodeを立ち上げて…」

"'bits/stdc++.h' file not found"
 

「え！？！？！？！？！？！？？！？！！！
昨日までは何事もなかったじゃんか！何よ、もう知らない！」 

という経験を10回くらいしてきたので、備忘録として書いておきます。

正直インターネットで色々調べてみるとこれ関連の記事はいっぱい出てくるので、この記事の存在意義とはって感じはしますが、まぁそういう記事をまとめたものだと思ってください。

あとMacのバージョンとか環境によって対処法は違うと思うので、この記事で解決しなかったら「bits/stdc++.h file not found xcode」とかでググって他の記事も参照すると良いと思います。

環境

• macOS Big Sur 11.2.3
• Xcode 12.5

対処法

基本的な対処法は、

1. bits/stdc++.hに該当するファイルをインターネットで見つける
2. 自分のXcodeのヘッダファイルの参照先を見つける
3. そこにbitsフォルダを作って、その中に1.のファイルを突っ込む

です。
1.は Xcodeでbits/stdc++.hをインクルードする - Qiita とかに書いてありますし、3.はこの通りやるだけなので、大事なのは2.です。

インターネット力を駆使して、自分のXcodeでヘッダファイルの参照先はどこなのかをひたすら探しましょう。

パターン1 (失敗)

Xcodeでbits/stdc++.hを使う方法などの記事を見ていると、bits/stdc++.hを

• /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1

の位置に投入するという話がいくつか見受けられました。*1

ただ、自分はこれでもXcodeのエラーが治らなかったので、他の情報を調べました。

パターン2 (成功)

C++のヘッダの場所についてもう少しググってみると、ヘッダファイルは

• /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX.sdk/usr/include

の位置から読み込んでいる、という話も見つかりました。*2

試しにこちらにbits/stdc++.hを入れてみたところ、Xcodeのエラーが無事消えました。

脚注

*1:https://qiita.com/Atsu30/items/6a4c4c070dd76a236fdc など

*2:https://stackoverflow.com/questions/28759427/xcode-c-header-files-directory

AGC010-D Decrementing を解いた

問題リンク

atcoder.jp

問題

2人が数列 に交互に次の操作をする。

1. のうち 以上の要素を選んで を引く
2. を のgcdで割る

操作できなくなった方が負けのとき、勝つのは先手と後手のどちらか。

思考

操作2がないとすると、答えは の偶奇で決まる。

操作2を入れて考えると、 の偶奇が変わるのは偶数で割るときだけ。
→ の偶奇に注目すればいい！

解答

N≧3のとき

操作2がなければ先手が勝てるとき

先手の番で偶数を奇数にすれば、奇数が常に1個以上ある = 操作2によって総和の偶奇が変化しない状態にできる。
→ 先手必勝

操作2がなければ後手が勝てるとき

奇数が2個以上のとき、後手の番で偶数を奇数にすれば、奇数が常に1個以上ある = 操作2によって(以下略)な状態にできる。
→ 奇数が2個以上のときは後手必勝

奇数が1個のときは先手はその1個を偶数にするしかない。
→ 奇数が1個のときは再帰的に解く

N=2のとき

{奇, 奇} のとき、先手は奇数を増やせないので話が少しややこしそう。

よくわからないので実験したところ、綺麗な市松模様になった。
→ 答えは操作2がないときと同じ

N=1のとき

確定なので cout << "Second" << endl;

提出コード

//#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
constexpr lint mod = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountll((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
#define rep(i, n) for(int i = 0; i < int(n); i++)
#define rep2(i, l, r) for(int i = int(l); i < int(r); i++)
#define repr(i, n) for(int i = int(n) - 1; i >= 0; i--)
#define repr2(i, l, r) for(int i = int(r) - 1; i >= int(l); i--)
constexpr int inf9 = 1e9; constexpr lint inf18 = 1e18;
inline void Yes(bool condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int x, y; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) cout << (i == start ? "" : " ") << (*i); if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint P(int n, int r){ if(r < 0 || n < r) return 0; return (fact[n] * inv[n - r] % mod); } lint C(int p, int q){ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }
template<class itr, class itr2> bool next_sequence2(itr first, itr last, itr2 first2, itr2 last2){ itr now = last; itr2 now2 = last2; while(now != first){ now--, now2--; (*now)++; if((*now) == (*now2)){ (*now) = 0; }else{ return true; } } return false; }
template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b){ if(b < a){ a = b; return 1; } return 0; }
inline int at(lint i, int j){ return (i >> j) & 1; }
random_device rnd;
bool is_in_board(lint y, lint x, lint H, lint W){ return (0 <= y && y < H && 0 <= x && x < W); }
lint inv2 = power(2, mod - 2, mod);

struct io_init {
    io_init() {
      cin.tie(nullptr); cout.tie(nullptr);
      std::ios::sync_with_stdio(false);
    }
} io_init;

#define int lint

bool solve3(int n, vector<int> a){
    int s = 0;
    for(int x: a) s += x - 1;
    if(s % 2 == 1){
        return true;
    }
    
    int odd = 0;
    for(int x: a) odd += x % 2;
    if(odd >= 2){
        return false;
    }
    
    int g = 0;
    rep(i, n){
        if(a[i] == 1) return false;
        if(a[i] % 2) a[i]--;
        g = gcd(g, a[i]);
    }
    rep(i, n){
        a[i] /= g;
    }
    return !solve3(n, a);
}

signed main(){
    int n;
    cin >> n;
    vector<int> a(n);
    cins(all(a));
    if(n == 1) cout << "Second" << endl;
    else if(n == 2) cout << ((a[0] + a[1]) % 2 ? "First" : "Second") << endl;
    else cout << (solve3(n, a) ? "First" : "Second") << endl;
}

(やばい、オーバーフローにハマってたのがバレる...)

Submission #21519251 - AtCoder Grand Contest 010

音楽のコードを隣り合う音が半音何個分離れているかで考える記事

この記事は何？

音楽のコード(和音)を、隣り合う音が半音何個分離れているかで考える記事です。

例えば、メジャーコードはルート音、第3音、第5音、ルート音(1オクターブ上)の間がそれぞれ半音4個分、3個分、5個分なので、4-3-5と表記します。

転回形を考えるときにでも使ってください。

追記(2021/2/1): 音の間隔を半音の個数で数えるのに馴染み深くない人のために、一般的な表記と半音の個数の対応表も下の方に載せました。

追記2(2021/2/1): 似たようなことを考えている人が他にもいたので、参考の項に載せておきます。

細かいルール

コードのルート音は全てCで表記します。ルート音がどこでも隣り合う音の間隔は同じなので、ルート音は正直気にしなくていいです。

ルート音からオクターブ以上離れてる音があるC9みたいなコードについては、ルート音のオクターブ以内に入るまで下げます。

対応表

コード	半音表記	備考
C	4-3-5
Cm	3-4-5
Cdim	3-3-6	Cm(♭5)に同じ
Caug	4-4-4	C(#5)に同じ
Csus4	5-2-5
Csus2	2-5-5

コード	半音表記	備考
C7	4-3-3-2
Cm7	3-4-3-2
CM7	4-3-4-1
Cm7(♭5)	3-3-4-2
Cdim7	3-3-3-3	Cdimと書かれることも
C6	4-3-2-3
Cm6	3-4-2-3
Cadd9	2-2-3-5

コード	半音表記	備考
C9	2-2-3-3-2	C7(9)の略
CM9	2-2-3-4-1	CM7(9)の略
C11	4-1-2-3-2	C7(11)の略
C13	4-3-2-1-2	C7(13)の略

参考 - 半音表記表

一般の表記	半音表記	備考
完全1度	0
増1度・短2度	1
長2度	2
短3度	3	マイナーコードの間隔
長3度	4	メジャーコードの間隔
完全4度	5
増4度・減5度	6
完全5度	7	頻出する第5音の間隔
短6度	8
長6度	9
短7度	10	セブンスの間隔
長7度	11	メジャーセブンスの間隔

参考

コードネーム一覧 - Programming Field
https://www.pg-fl.jp/music/chord.htm

【ギター】コードネームの仕組みを知ろう！Part1【音楽理論】 | みゅーろぐ
https://manic.biz/gt-chord-name1/

コードの応用：sus、dim、aug、add、テンションコードの解説｜Junya Watanabe Official Site
https://watanabejunya.com/chord-advance-tension/

似たようなことを考えている人

表記が1-indexedなのでこの記事とは1ずつずれていることに注意。

• 数字で考える音楽理論 - 桶谷 弘美
  https://osaka-shoin.repo.nii.ac.jp/?action=pages_view_main&active_action=repository_view_main_item_detail&item_id=3665&item_no=1&page_id=3&block_id=24

この記事よりもっと数学的に(厳密に)定義している。

• 公理的音楽論 - カナンの数学ノート
  http://canaan1008.hatenablog.com/entry/2018/06/20/010914

AtCoder Regular Contest 104

まえがき

ARCなんてめちゃめちゃ久しぶりですね...。前回のARCから2年も経ってるらしいですよ。

というか、2年前とperfが変わってなくてショック受けました。

コンテストリンク

atcoder.jp

A問題

一瞬迷いますが、落ち着いて(A+B)/2と(A-B)/2を出力すればおkです。

軽く腕ならしするつもりで[AC]していきましょう。

提出コード

B問題 

解法

Tに含まれる'A'と'T'、'C'と'G'の個数が同じの時に条件を満たします。

N≦5000なので、愚直にシミュレーションしても間に合います。

提出コード

感想

制約がN≦200000でも、Zero-Sum Rangesみたいにすれば簡単に解けます。N≦5000なのはwriterさんの優しさでしょうか。

C問題

これすき

解法

ある人がk階上がるとき、その間に乗り降りする人も全員k階上がるので、結局「ある階からk-1階上の階までの人がみんなk階上がる」ってことになります。

すると、その集団で最初の人が乗る前と最後の人が降りる後にはエレベーターはすっからかんになります。

そうすると、

　dp[i]=エレベーターがi階目を出発する時にすっからかんになりうるかどうか

というbool値を持つDPが書けて、状態O(N)遷移O(N)遷移時間O(N)でO(N^3)時間になって無事ACです。

提出コード

感想

コンテスト中の自分は、「ある人Aがk階上がるとき、その間に乗る人もみんなk階上がるから、Aさんが乗る階からk-1階上の階までの人はみんなk階上がるよね」と、Aさんが乗ってる間に人が降りる可能性を無視して脳内考察してました。

どっちみち同じ結論になるのでまぁ結果オーライなんですが、危ない危ない...。

D問題

こっからACできなかった問題です。

解法

まず真っ先に常套テク、全体をxズラして平均を0にします。

ズラした後の数を正と負に分けると、それぞれのグループで選んだ数の和が同じになればいいので、

　dp[i][S] = 1, 2, ... iのそれぞれをK個以下選んでSにする方法の個数

が求まればSをO(N^2K)通り全探索で解けます。

このDPは累積和を使って遷移してあげると状態O(N^3K)遷移O(1)でO(N^3K)時間で解けます。

感想

コンテスト中は、常套テク以降の方針を決めあぐねて5乗高速化とか6乗高速化とかしてました(もちろん軒並み失敗)。

正と負にグループ分けもちょっと考えましたが、それ以降が思いつかなくてEに移ってました。

E問題

解法

X_iを座圧すると全要素がN以下になるので、座圧後の数列は高々6^6=46656通りです。

X_iのLISを考える代わりに座圧後の列のLISを考えてもLISの長さは変わらないので、

　Σ(X_iのLISの長さ) = Σ(座圧後のLISの長さ)×(座圧してその列になるX_iの個数)

と変形できます。

座圧後の数列を一つ固定すると、そのLISの長さは全探索で求まり、(座圧してその列になるX_iの個数)はDPで求まる...らしいです。[要出典]

感想

コンテスト中はDPではなく多項式をこねて考えてましたが、時間内に実装しきれませんでした。

僕が思いついた多項式解法は実質DP解法の下位互換みたいなものなので、完全に考察不足って感じでしたね...。

あとがき

C(600)は相性良くてすんなり解けたのに、D(700)とE(700)でだだ詰まりしてボコボコになりました。

Dを解き続けるのがいいムーブだったのかな......わからん

蛇足

コンテスト中はMegalovaniaの100分耐久をBGMにしてました。

100分耐久はいいぞ〜

www.youtube.com

wine導入時にYour bison version is too old. Please install bison.と言われた

　macOS Catalinaでwineを導入する途中、$ ./configure --enable-win64を実行したら

configure: error: Your bison version is too old. Please install bison version 3.0 or newer.

と言われてしまった。

　bisonのバージョンが古いとのことなので、早速現在のbisonのパスとバージョンを確認。

$ which bison
/usr/bin/bison
$ bison --version
bison (GNU Bison) 2.3
...  

　確かに、エラー通りbisonのバージョンは3.0未満のようだ。しかし、bisonを3.0以降の新しいものにする方法は分からなかったので、Google先生に頼ることにした。

　エラー文をそのままコピペし、"Your bison version is too old."とググったら、あるブログにたどり着いた。
Dinker Charak's Blog - Running Windows Programs on Mac OS X Using WineHQ - March 11, 2020 21:16

　どうやら、/usr/local/Cellar/bison/(バージョン)/bin下に新しいbisonがあるようだ。/usr/local/Cellar/bisonに行って確認する。

$ cd /usr/local/Cellar/bison
$ ls
3.7.1

　確かにあった。そして、/usr/local/Cellar/bison/3.7.1/binに行ってみるとちゃんとbisonがあった。

　あとはそこにパスを通せばよい。

$ export PATH=/usr/local/Cellar/bison/3.7.1/bin:$PATH
$ which bison
/usr/local/Cellar/bison/3.7.1/bin/bison

　無事にパスが通ったようだ。

　そして、

$ ./configure --enable-win64
...
configure: Finished.  Do 'make' to compile Wine.

　無事に$ ./configure --enable-win64が完了。めでたしめでたし。

追記

調べたら、そもそもCatalinaではwineは動かないみたいですね。残念。

yukicoder No.1087 転倒数の転倒数

yukicoder.me

Writer解とは解法が違うらしい。

問題

$N, K$ が与えられます。

次の条件を満たす $N\times N$ の行列 $S$ が存在するか判定し、存在するなら一つ構築しなさい。

• $S$ の $i$ 行目の転倒数を $A_i$ とする。
• $S$ の $i$ 列目の転倒数を $B_i$ とする。
• $[A_1, ..., A_N]$ の転倒数 $+\ [B_1, ..., B_N]$ の転倒数が $K$ である。

制約

• $1≦N≦1000$
• $1≦K≦10^9$

解法

$N(N-1)< K$ のときは明らかに不可能です。逆に、これ以外のときは可能です。

以下では、これを実際に構築します。なお、以降では全て0-indexedになります。

突然ですが、$a=\{0, ..., N-1\}$ の順列とし、$S$ を $S_{i, N-1-a_i}=10^6, $ それ以外は $0$ とします。

例えば、$a=[2,1,3,0]$ のときはこんな感じです。

\begin{pmatrix} 0 & 10^6 & 0 & 0 \\ 0 & 0 & 10^6 & 0 \\ 10^6 & 0 & 0 & 0 \\ 0 & 0 & 0 & 10^6 \end{pmatrix}

このとき、$A$ と $B$ は共に $\{0, ..., N-1\}$ の順列になります。

この解法の肝は、このように $S$ を作ると $a$ の転倒数と $A$ の転倒数と $B$ の転倒数が全て等しくなることです。

これは、次のように証明できます。

• まず、よく考えると $a=A$ なので、$a$ の転倒数と $A$ の転倒数は等しくなります。
• $A$ の転倒数は、「$S$ 中の $10^6$ のペアであって、片方がもう片方の左上にあるものの個数」と言い換えることができます。
• $B$ の転倒数も、「$S$ 中の $10^6$ のペアであって、片方がもう片方の左上にあるものの個数」と言い換えることができます。
• よって、$A$ の転倒数と $B$ の転倒数は等しくなります。

これによって、$K$ が偶数のときは $a$ の転倒数を $K/2$ にすることで条件を満たす $S$ が構築ができます。

以降では、$K$ は奇数とします。

まずは、$a$ の転倒数が $(K+1)/2$ になるように $a$ を作ります。このとき、$a$ 内の $0$ の位置が $1$ の位置より右に来るように $a$ を作ります。

( $(K+1)/2≧1$ より、数列 $a$ をそういう風に作ることは可能です。)

今度は、$T_{i,j}=i+j$ となる $N\times N$ 行列 $T$ を考えます。

例えば、$N=4$ のときはこんな感じです。

\begin{pmatrix} 0 & 1 & 2 & 3 \\ 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 6 \end{pmatrix}

この $T$ は、どの隣接する $2$ 項を交換しても、それに対応する行または列の転倒数のみが $1$ 増える、という特徴があります。

そして、$S_{i,j}=\max(T_{i,j}, $ さっきまでの $S_{i,j})$ とします。

例えば、$a=[2,1,3,0]$ のときはこんな感じです。

\begin{pmatrix} 0 & 10^6 & 2 & 3 \\ 1 & 2 & 10^6 & 4 \\ 10^6 & 3 & 4 & 5 \\ 3 & 4 & 5 & 10^6 \end{pmatrix}

そして、$a_x=0$ となるような $x$ について、$S_{x,1}$ と $S_{x,2}$ をswapします。

\begin{pmatrix} 0 & 10^6 & 2 & 3 \\ 1 & 2 & 10^6 & 4 \\ 10^6 & 3 & 4 & 5 \\ \color{red}{4} & \color{red}{3} & 5 & 10^6 \end{pmatrix}

こうすると、$B$ は変わらずに、$A$ の $0$ だった項が $1$ になります。

すると、変える前には $A$ 内の $0$ の位置は $1$ の位置より右にあったので、$A$ の転倒数は $1$ 減ります。

変える前の $A$ の転倒数 $+\ B$ の転倒数は $(K+1)/2\times 2=K+1$ だったので、変えた後の $A$ の転倒数 $+\ B$ の転倒数は $K$ となり、条件を満たす $S$ が構築できました。

例外

ただし、このアルゴリズムは $K$ が奇数のときに「$S_{x,1}$ と $S_{x,2}$ は共に $10^6$ ではない」という前提条件を必要としています。

この前提条件は $N≦2$ のときに崩れるので、このアルゴリズムは $N=2,K=1$ で落ちます。

このときだけ場合分けしてやりましょう。例えば、

\begin{pmatrix} 3 & 2 \\ 0 & 1 \end{pmatrix}

などです。

提出コード

解説にすると長いけど、頭の中で解法を整理してる時間はもっと短い。むしろ解法を思いつくまでの時間が長すぎる。

余談：この提出を貼って気がついたけど、yukicoderが500000提出に到達したみたい。おめでとう！

yukicoder.me