2024-06-03

みらくらぱーく！

問題解くことさぼりすぎ。

2024/6/2
- A - Partition

2024/6/2

AtCoder Regular Contest 179に参加した。

atcoder.jp

A - Partition

atcoder.jp

問題

整数 $N,K$ が与えられる。長さ $N$ の整数列 $X$ の累積和を、初期値 $0$ で長さ $N+1$ の整数列 $Y$ とする。整数列 $X$ は次の条件を満たすとき良い数列であると言う。

の累積和の要素の任意の未満の値は、任意の以上の値よりも前に現れる。
- 正確には、 $X$ の累積和を $Y$ として、 $0\le i,j\le N$ なる任意の整数組 $(i,j)$ について、 $(Y_{i}\lt K$ かつ $Y_{j}\ge K)$ ならば $i\lt j$ が成り立つ。

長さ $N$ の整数列 $A$ が与えられる。 $A$ の要素を自由に並べ替えることで $A$ を良い数列にできるかどうか判定し、できる場合は並び替えた後の $A$ としてあり得るものをひとつ出力せよ。

制約

$1\le N\le 2\times 10^{5}$
$-10^{9}\le K,A_{i}\le 10^{9}$

方針

$K>0$ のとき、 $K\le 0$ かつ $\sum_{i=1}^{N}A_{i}\ge K$ のとき、 $K\le 0$ かつ $\sum_{i=1}^{N}A_{i}\lt K$ のときで場合分けして、 $A$ をソートする

int n, k; cin >> n >> k;
vector<int> a(n);
rep(i, 0, n) cin >> a[i];
ll sum = accumulate(all(a), 0LL);
if (k <= 0 && sum < k){
  cout << "No" << endl;
  return 0;
}
cout << "Yes" << endl;
sort(all(a));
if (k <= 0) reverse(all(a));
rep(i, 0, n){
  cout << a[i];
  if (i < n - 1) cout << ' ';
}
cout << endl;
return 0;

2024-06-03

辞書的なもの

気温が $25^\circ C$ を越える日が増えていて、春の終わりを感じています。

2024/4/26
- Chapter 1 C++とは
- Chapter 2 基本文法
  - 演算子

2024/4/26

gihyo.jp

今日、[改訂第5版]C++ポケットリファレンスが発売された。著者は、高橋晶、安藤敏彦、一戸優介、楠田真矢、湯浅剛介。予約注文していたものが届いたので早速読んでみた。以下で内容を、特に、新たに知ったことや注意点について纏めていきたい。

Chapter 1 C++とは

C++は、新機能を追加する際は、C言語や過去のC++のバージョンに影響を及ぼさないようにしている。
C++23では、16ビット浮動小数点数型std::float16_tや、文字列フォーマット付きの出力関数std::println()などが追加された。

Chapter 2 基本文法

演算子

$\lt =\gt$
三方比較演算子「 $\lt =\gt$ 」(C++20)。2値について「より小さい」「等しい」「より大きい」「比較不能」のいずれかの結果を返す。<compare>ヘッダのインクルードが必要。演算子の戻り値を0と比較する。

時間を見つけて読み進めて行きたい。

2024-04-14

朝起きれん

暑くなってきたので扇風機つけてます。

2024/4/13
- 競プロ典型90問
  - 018 - Statue of Chokudai（★3）
- AtCoder Beginner Contest 349
  - E - Weighted Tic-Tac-Toe
2024/4/14
- ランニング

2024/4/13

競プロ典型90問

今日も競プロ典型90問を解いた。

atcoder.jp

018 - Statue of Chokudai（★3）

atcoder.jp

問題

平面 $x=0$ 上に高さ $L$ の $T$ 分で一周する円形の観覧車がある。以下のように一定の速さで動く。

$0$ 分後に座標 $(0,0,0)$ にある
$\frac{T}{4}$ 分後に座標 $(0,-\frac{L}{2},\frac{L}{2})$ にある
$\frac{T}{2}$ 分後に座標 $(0,0,L)$ にある
$\frac{3T}{4}$ 分後に座標 $(0,\frac{L}{2},\frac{L}{2})$ にある

像は座標 $(X,Y,0)$ にある。以下のような $Q$ 個の質問が与えられる。

$E_i$ 分後の像への俯角を求めよ。

制約

$1\le Q\le 1000$
$90$ 度までの度数法で出力
相対誤差または絶対誤差が $10^{-7}$ 以下となる

方針

三角関数を使って座標や角度を求める。

double t, l, x, y; cin >> t >> l >> x >> y;
double pi = acos(-1);
int q; cin >> q;
while (q--){
  double e; cin >> e;
  double a = 2 * pi * (e / t);
  double Y = -l / 2 * sin(a), Z = l / 2 *(1 - cos(a));
  cout << fixed << setprecision(10) << atan2(Z, hypot(x, y - Y)) / pi * 180 << endl;
}

ポイント

C++ではatan2という関数があり、2辺の長さ $x,y$ を引数としてラジアン単位の角度 $\theta$ を求めることができる。

cpprefjp.github.io

また、hypotという関数では平方和の平方根を求めることができる。hypotはhypotenuse((直角三角形)の斜辺)の略らしい。

cpprefjp.github.io

三角関数を使う問題をほとんど解いたことがなく、幾何が得意でないので難しかった。解説やほかの人の提出コードを見てなんとか分かった。

AtCoder Beginner Contest 349

atcoder.jp

E - Weighted Tic-Tac-Toe

atcoder.jp

問題

$3×3$ の白いマス目があり、マス $(i,j)$ は $A_{i,j}$ である。先攻、後攻が以下の操作を交互に行う。

プレイヤーは白マス $(i,j)$ を選び得点 $A_{i,j}$ を得る。先攻はマス $(i,j)$ を赤に後攻は青に塗る。

各操作後判定を行う。

赤（青）マスが縦・横・斜めのいずれかの方向に3連続するなら先攻（後攻）が勝利する。
白マスがなければ得点の合計が高い方が勝利する。

両者が勝利のために最適に行動するときどちらが勝つか判定せよ。

制約

$|A_{i,j}|\le 10^{9}$
$\sum_{i=1}^{3}\sum_{j=1}^{3}A_{i,j}$ は奇数

方針

DFS。メモ化。

ポイント

特にない。問題の理解はすぐにできたが、実装が重くて解けなかった。

2024/4/14

ランニング

10:42開始。西武池袋線沿いを通り練馬駅を経由して新江古田駅で折り返し。久々に運動して疲れた。大通りを通って行ったので信号で止まることが多かった。いい感じのルートを探しておきたい。

距離: $11.74km$
時間: $1:17:56$
ペース: $6m38s/km$
平均心拍: $162bpm$

2024-04-12

3連休です！

近頃、競プロ典型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

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!

2024-04-04

新年度になりました

今年は花粉大丈夫かもしれない。

2024/4/3
最近の購入品
限られた時間

2024/4/3

ゲームフリーク Programming Contest 2023

atcoder.jp

問題

$N$ 個の点と $M$ 個の無向辺がある。辺 $i$ は点 $A_i$ と点 $B_i$ を結び、長さは $C_i$ である。
任意の点から始めて、同じ点を通らずに別の点へ移る時の最長経路を求めよ。

制約

$2\le N\le 10$
$1\le M\le\frac{N(N-1)}{2}$

方針

DFS。計算量は $O(NN!)$ 。 $10!=3628800$ 。

int n, m;
cin >> n >> m;
vector<vector<int>> g(n, vector<int>(n, -1));
for (int i = 0; i < n; i++){
  int a, b, c;
  cin >> a >> b >> c;
  --a; --b;
  g[a][b] = g[b][a] = c;
}
vector<int> p(n);  //1
iota(p.begin(), p.end(), 0);  //1
int ans = 0;
do {
  int sum = 0;
  for (int i = 0; i < n - 1; i++){
    if (g[p[i]][p[i + 1]] == -1) break;
    sum += g[p[i]][p[i + 1]];
  }
  ans = max(ans, sum);
} while (next_permutation(p.begin(), p.end()));  //2
cout << ans << endl;
return 0;

ポイント

2でnext_permutationを使うために、1で要素が昇順にソート済みである配列を用意している。

限られた時間

AtCoder Problemsの問題を解くことに多くの時間を費やしているので、なかなか本を読む時間がない。睡眠時間を削っても大丈夫なスーパーマンではないし、仕方ないね。健康第一。

2023-12-31

2023年の振り返り

1年の振り返りをしてみようと思う。

1~3月

大学卒業

3月末の卒業式。学位記を受け取って帰っただけ。当日は桜が咲いていて良い感じだった。
大学では独り暮らしやアルバイトなど社会人として自立するための前準備を多く経験した。家にこもってゲームをしていることが多かったが、おそらく最後であろう学生生活を満喫できたと思う。

引っ越し

東京での就職にあたって引っ越しを計画。初め、品川辺りで新居を探していたが、良い感じのものが無かったので違う場所にすることに。新宿に電車一本で行ける場所を調べたところ練馬に決定。新居の周辺は住宅街であまりうるさくなく今のところ過ごしやすいように感じている。道が少し狭いくらいか。隣の住人は最近引っ越したっぽい。その人はベランダに掃除機を置いていて、それを見て驚いたことを思い出した。

4~7月

就職

4月、新宿や秋葉原にオフィスを構えているIT企業に入社。社長は40歳半ばくらいで麻雀が好きらしい。自分が好きな役は三色同順です。

研修

入社から2ヶ月間は研修を受けて、その間に2つの資格を取得した。これらの資格を更新するには3~5年程で再受験が必要らしい。会社の研修が終了してからプロジェクト参画(8月)までの間に、この他にあと2つの資格を取得した。知らないことを勉強することが楽しいと感じることが増えた。

8~12月

プロジェクト参画

8月からデータセンターでネットワーク監視や顧客対応をする業務に就いている。業務に慣れ、新人教育にも携わるようになった。ネットワークの勉強を家でしたり自分で環境を構築して動かしたりすることはできるが、実際に使われている大規模な構成に触れるこの機会を大切にして多くのことを学んでいきたい。

プログラミング

以前から興味があり、応用情報技術者試験の午後問題対策も兼ねて、8月ごろからAtCoderでプログラミングに触れ始めた。初学者用の勉強をした後は本を読んだり過去問を解いたりコンテストに参加したりしている。2024年4月の応用情報技術者試験の勉強に時間をかけたいのでプログラミングの勉強やコンテストへの参加は少なくなると思うが、長く続けたいと思っている。

Markdown記法練習

Code - コードの挿入

#include <iostream>
using namespace std;
int main(){
  int n;
  cin >> n;
  for (int i = 0; i < n; i++){
    cout << i + 2 << endl;
  }
  return 0;
}

sample code

puts 'Hello, World'

2023-12-17

下書きそのまま出し

2023/11/25(土)

ABC330B

----------------

std::clamp (c++17)

【概要】値を範囲内に収める。vの値を[low, high]の範囲に収める。

【戻り値】vの値がlowより小さければlowを返す。vがhighより大きければhighを返す。そうでなければvを返す。

【備考】clamp(v, low, high)はmin(max(v, low), high)と同値。

(2023/11/26 07:45 cpprefjpより)

----------------

clampは、｢留め金｣、｢締め具｣といった意味らしい。

『アルゴリズムイントロダクション第3版総合版』(T.コルメン他)を購入。1000ページ以上ある本。

DFSを習得するべく本やnoteを読んでいる。

2024/6/2

A - Partition

2024/4/26

Chapter 1 C++とは

Chapter 2 基本文法

2024/4/13

競プロ典型90問

018 - Statue of Chokudai（★3）

AtCoder Beginner Contest 349

E - Weighted Tic-Tac-Toe

2024/4/14

ランニング

2024/4/9

002 - Encyclopedia of Parentheses（★3）

007 - CP Classes（★3）

2024/4/10

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

2024/4/11

GitHub Copilot

2024/4/3

最近の購入品

限られた時間

1~3月

大学卒業

引っ越し

4~7月

就職

研修

8~12月

プロジェクト参画

プログラミング

Markdown記法練習

Code - コードの挿入