3連休です！ - ma24mag0のブログ

近頃、競プロ典型90問に取り組んでいます。

atcoder.jp

2024/4/9
- 002 - Encyclopedia of Parentheses（★3）
- 007 - CP Classes（★3）
2024/4/10
- 響け！ユーフォニアム３ #1 - あらたなユーフォニアム
2024/4/11
- GitHub Copilot

2024/4/9

002 - Encyclopedia of Parentheses（★3）

atcoder.jp

問題

「正しい括弧列」が定義されている。長さ $N$ の正しい括弧列を辞書順に出力せよ。

制約

$1\le N\le 20$

方針

bit全探索。オーダーは $O(2^{N}N)$ 。2種類の括弧の数の差を管理。

int n; cin >> n;
rep(i, 0, (1 << n)){
  string s = "";
  int cnt = 0;
  per(j, n, 0){
    if ((i & (1 << j)) == 0) s += '(', cnt++;
    else s += ')', cnt--;
    if (cnt < 0) break;
  }
  if (cnt == 0) cout << s << endl;
}

ポイント

$「\And」$ は $「==」$ よりも演算の優先順位が低いので注意。

007 - CP Classes（★3）

atcoder.jp

問題

$i(1\le i\le N)$ 番目の基準値は $A_{i}$ である。
$j(1\le j\le Q)$ 番目の値が $B_{i}$ であるとき、最小の $|a-b|$ を出力せよ。

制約

実行制限時間: 3 sec.
$1\le N,Q\le 300000$
$0\le A_{i},B_{i}\le 10^{9}$

方針

sortして、lower_boundで二分探索。オーダーは $O((N+Q)\log N)$ 。

int n; cin >> n;
vector<ll> a(n);
rep(i, 0, n) cin >> a[i];
a.push_back(-100100100100100100); //1
a.push_back(100100100100100100); //1
sort(all(a));
int q; cin >> q;
rep(i, 0, q){
  ll b; cin >> b;
  auto itr = lower_bound(all(a), b) - a.begin();
  cout << min(a[itr] - b, b - a[itr - 1]) << endl;
}

ポイント

1で、全ての基準値 $A_{i}$ よりも $B_{i}$ が大きい場合を考慮する。

2024/4/10

響け！ユーフォニアム３ #1 - あらたなユーフォニアム

3年生編がついに始まった！とても嬉しい！響け！ユーフォニアムの制作に関わってくださっている方々、深く感謝申し上げます。本当に本当にありがとうございます。今回も今後もNetflixで視聴する予定。これからの毎週の更新が楽しみで、それに伴って毎日の生活が輝きそう。
第1話は、響け！シリーズのおさらいと新たな出会い。黒沢ともよさんが演技上手過ぎる。黄前久美子が隣で生きています。
恐らく編入生の銀色のユーフォニアムを吹いてた黒江真由（くろえまゆ）は演奏上手そう。低音パートだとユーフォニアムとコントラバスは強そうで、チューバは弱そう。クラリネットは南中の経験者が、パーカッションは聖女の経験者が入りそう。全国大会金賞いけそう？
あの、並んで歩いてて、肩ぶつけ合う描写いいですよね。学生の距離が近い感じ。お互いにわかってるから、前もって踏ん張るし、「ずるい」と言う。秘密の共有までいかなくとも、同じ場所で同じ時間を過ごすことで互いに通じ合う部分が生まれる。いいね。
部の目標は満場一致で「全国大会金賞」に。そして、次の曲が始まるのです。

TVアニメ響け！ユーフォニアム３はNHK Eテレで毎週日曜17:00から放送中！その他各種配信サイトでも順次配信中！

anime-eupho.com

2024/4/11

GitHub Copilot

GitHub JapanのツイートにあったGitHub Copilot Enterpriseの説明動画を見た。組織内のナレッジを活用することに重点を置いているらしい。GitHub.comに直接チャットを組み込むことでプライベートリポジトリのソースコードに対しても最適な提案をしてくれる機能や、pull requestでの変更の概要をAIが作成してくれる機能などがある。GitHub Copilot Enterpriseは企業で開発を行うときに利用されることを想定しているようなので、個人としては今のところ使う機会はなさそう。月額39米ドルでの提供。
ちょっと話が変わって、Mermaid記法というものを知った。動画内でCoplilotに対して「この部分をMermaid記法を用いて書いて」みたいな感じで投げてた。Mermaidは、Markdownテキストでグラフやチャートを記述できるJavaScriptのライブラリらしい。こんな感じ。

sequenceDiagram
  participant A
  participant B
  A->>C:Hello C, how are you?
  loop Healthcheck
    C->>C:Fight against sleepiness
  end
  Note right of C:Not want to go out <br/>zzz
  C-->>A:Sleepy.
  C->>B:How are you?
  B-->>C:Very good!