ABC 253 C 勉強メモ
コードは公式解説ページの実装例より
TODO
st.eraseの部分をイマイチ理解出来ていないのであとで調べる
コード
#include <bits/stdc++.h>
using namespace std;
int main() {
int q;
cin >> q;
// multiset は要素をキーにアクセスできるコンテナ。
// 小さいものから大きいものにソートされる (Compare, で指定できる)
// find() -> キーに一致した要素の最初のイテレータ S[1, 1, 1] なら S[0] のが返る的な
// count() -> キーに一致した要素の個数
// c++ イテレータ -> 反復子、++で進む [0, 1, 2, ..., N] で1のイテレータ i -> i++ -> 2 を指す
// c++ 逆イテレータ -> 反復子、++で戻る [0, 1, 2, ..., N] で1のイテレータ i -> i++ -> 0 を指す
// イテレータ はポインタのようなもの。*はそれの指す値 (C言語のポインタと同じ)
multiset<int> st;
while (q--) {
int t; // query type
cin >> t;
if (t == 1) {
int x;
cin >> x;
st.insert(x);
} else if (t == 2) {
int x, c;
cin >> x >> c;
// min(c, xの個数)
// c が 0になったが x がまだある -> c で打ち止め
// c は 1以上あるが x がもう無し -> 削除対象がなくなったので打ち止め
// 多重集合内に要素なし -> 削除できないのでwhile 内を処理しない
// st.count() の計算量
// 要素数を N, st に含まれる x の個数を k とすると
// O(k + logN)
// -> 2分探索 + カウント を行っていると思われる
// 以下は 計算量が O(log N) になるための工夫で st.find() を使用している
while (c-- and st.find(x) != st.end()) {
// [注意!]
// multiset<int> st = {3, 3, 3, 4}; に
// 普通に st.erase(3) とかすると
// { 4 }, になり、3の要素すべてが削除されてしまう。
// イテレータへの理解が必要
st.erase(x);
}
} else {
// rbegin() -> 末尾の逆イテレータ, *つけてるので最大値
// begin() -> 先頭の イテレータ, *つけてるので最小値
cout << *st.rbegin() - *st.begin() << endl;
}
}
}
「アルゴリズムとデータ構造」の勉強方針、AtCoder について
なぜ勉強するのか
- この分野を今までできちんと勉強したこと無い
- プログラミングをする上で最低限の実力として身につけていないとまずいと個人的に感じている
- 計算量等は知識として持っているが、実際に意識してコードが書けているかは微妙なところ
- AtCoder のレートが高い人に憧れを感じるので
- 簡単には伸びない力で、時間をかける必要があると、思うので
- 将棋でいう「読み」の力の類だと思う。長手数の詰将棋を解き続けることで伸ばしていくような。
現在の実力
以前何回か AtCoder の ABC に参加した際に、A, B 問題はスムーズに解けるが他は無理、程度の実力。 C 問題は少し解けたりもしたが、AtCoder Problems での Difficluty で 300 ぐらいのが解けたぐらい。 またアルゴリズムの力に直結する数学力についても、受験勉強の経験が無いので期待できないと言ったところ。 (ただし劣等感やアレルギーを感じている英語と違って、むしろ好きだと感じている)
直近の勉強の方針
- AtCoder & AtCoder Problems を活用する
- AtCoder Problems で Difficluty を見た時に 400 - 1200 (茶 - 緑あたり)の問題を「解説の理解や写経」を中心に行う
- 詰将棋。答えを見たほうが伸びる方式
- 数学的な話題 (多重集合や漸化式、etc.) については、Webや書籍で調べながらで、かつ時間をかけながらなら、なんとか理解はできるので
- 問題を最初に読み、解けそうだと思ったならやってみる
- 買い揃えた書籍 (けんちょん本、螺旋本、蟻本と青チャート)は上記をやりつつ、解説に出てきたテクニックの理解や習得に活用
- 言語は C++ と、普段仕事で使っている Python3 も使いつつといった感じ
- 「コンテストには必ず参加する！」のような気合はいれない
- 気合を入れすぎると、「疲れてやめる 〜 復帰するまでの間が長くなる」までのこれまたいつものパターンになるので
一行でまとめると以下
「解説を読みつつ、理解したことをブログにメモする」
Ubuntu 20.04 LTS でホームディレクトリ配下にある ~/Pictures や ~/Videos などの位置を変更する方法
Ubuntu 20.04 LTS をPCにインストールした直後のホームディレクトリ配下には、
~/Pictures や ~/Videos などのディレクトリが存在する。
Terminal から $ ls を叩いたりした時に、ごちゃごちゃしていると感じたため、
以下のように整理しようと思った。
- ディレクトリ名を短くしたい (
~/Documents->~/docs) - 別のディレクトリに移動させたい(
~/Downloads->~/var/downloads) - 隠しディレクトリにしたい (
~/Videos->.videos)
とりあえず $ mv で変更はしたが、それだけだたGUI上からディレクトリを操作する「Files」アプリからアイコンをクリックして参照する際に
「Oops! Something went wrong.」とエラーのポップアップが出てしまう。これが気持ち悪い。
調べてみると、どうやら ~/.config/user-dirs.dirs の内容を編集する必要があるっぽい。
以下は変更例 (コメントは除外)
before
XDG_DESKTOP_DIR="$HOME/Desktop" XDG_DOWNLOAD_DIR="$HOME/Downloads" XDG_TEMPLATES_DIR="$HOME/Templates" XDG_PUBLICSHARE_DIR="$HOME/Public" XDG_DOCUMENTS_DIR="$HOME/Documents" XDG_MUSIC_DIR="$HOME/Music" XDG_PICTURES_DIR="$HOME/Pictures" XDG_VIDEOS_DIR="$HOME/Videos"
after
XDG_DOCUMENTS_DIR="$HOME/docs" XDG_DOWNLOAD_DIR="$HOME/var/downloads" XDG_DESKTOP_DIR="$HOME/.desktop" XDG_TEMPLATES_DIR="$HOME/.templates" XDG_PUBLICSHARE_DIR="$HOME/.public" XDG_MUSIC_DIR="$HOME/.music" XDG_PICTURES_DIR="$HOME/.pictures" XDG_VIDEOS_DIR="$HOME/.videos"
上記の通り変更後、とりあえず再起動を行いGUI 上で「Files 」を実行したところ問題なさそうだった。
