3月22日
お絵かきしたよ。
みて！！ 風呂場でシャンプーを見てたらプーさんをシャンプーにしたくなりました。
プーと大人になった僕 pic.twitter.com/GCpwdn4eKa
— 瑞々しぃにぼし@バナナのナナチはバナナナチ (@niboshi_wakai) 2020年3月22日
メモ書き
- 重要なこと、覚えたいことはタイピングよりも手書きのメモのほうが良い。
- 本に書き込みをするだけでアウトプットになるらしい
- アウトプットはインプットの直後に行え
- 頭の中も作業空間もできるだけ片付けて置く。(脳には3つのタスクしか入れておけない。それ以上入れると人は死ぬ)
- 脳を空っぽにするためのものがアウトプット。
- エキスパートになるには1万時間の集中的訓練が必要
- 集中的訓練とは、課題の達成が目的ではなく、自らの能力、つまりスキルやテクニックを向上させることが目的。
- 入念に計画されたことを1万時間行うのは、自分の得意でない分野にも手を伸ばすことである.楽しいとは限らないが、反復大事(this is 集中的訓練)
今日解いた問題
ARC005 B- P-CASカードと高橋君
[天才実装ゲー,方向転換の処理]
僕のコードを見た方が早いですね（ｲｷﾘ)
ing check[8] = {"R","L","U","D","RU","RD","LU","LD"}; int dx[8] = {1,-1,0,0,1,1,-1,-1}; int dy[8] = {0,0,-1,1,-1,1,-1,1}; bool is_side(int x){ // 次見るところが左右の枠に収まっているかを判定する if(x < 0 || x >= 9) return true; return false; } bool is_ceil(int y){ // 次見るところが上下の枠に収まっているかを判定する if(y < 0 || y >= 9) return true; return false ; } int main() { int x, y; cin >> x >> y; --x, --y; string w; cin >> w; vector<vector<int>> a(9,vector<int>(9)); // 9 x 9 のマス目を二次元配列にもたせました rep(i,9){ string s; cin >> s; //rep(j,9) a[i][j] = s[j] - '0'; } //string ans = ""; int k; rep(i,8){ if(w==check[i]) k = i; } // ここまで入力 rep(i,4){ cout << a[y][x]; //ans += to_string(a[y][x]); if(is_side(x+dx[k])) dx[k] *= -1; if(is_ceil(y+dy[k])) dy[k] *= -1; y += dy[k]; x += dx[k]; } cout << endl; }
入力で受け取ったwがcheck[i]のとき、初期の移動させる方向は(dy[i],dx[i])です。
そして、入力で受け取った(y,x)をまず答えの一文字目とします。
その後、wの方向へ進むのですが、壁に当たったとき、上下の壁に当たったらdyを180度反転させる。左右の壁に当たったらdxを180ど反転させる。
ここで重要なのが、180度反転は、元の移動させる向きと力(0か1か）に-1を掛ければいいってことです。多分。
そういう感じにして天才実装します。
string check[8] = {"R","L","U","D","RU","RD","LU","LD"}; int dx[8] = {1,-1,0,0,1,1,-1,-1}; int dy[8] = {0,0,-1,1,-1,1,-1,1}; bool is_side(int x){ // 次見るところが左右の枠に収まっているかを判定する if(x < 0 || x >= 9) return true; return false; } bool is_ceil(int y){ // 次見るところが上下の枠に収まっているかを判定する if(y < 0 || y >= 9) return true; return false ; } int main() { int x, y; cin >> x >> y; --x, --y; string w; cin >> w; vector<string> a(9); rep(i,9){ cin >> a[i]; } int k; rep(i,8){ if(w==check[i]) k = i; } // ここまで入力 rep(i,4){ cout << a[y][x]; if(is_side(x+dx[k])) dx[k] *= -1; if(is_ceil(y+dy[k])) dy[k] *= -1; y += dy[k]; x += dx[k]; } cout << endl; }
stringにしていい感じにしたバージョン！
そういえば今日はABC159
僕は4完そこそこ解きでレート+20でした。昨日と合わせて+20ぐらい。
コンテスト始まって50分ぐらいの段階でE問題がbit全探索だと気づいたのですが、日頃の精進が足りず、残りの時間で実装することが出来ませんでした。
一応動くコードを書くところまでは持っていけたんですけど、なんかまぁ、期待通りのコードにはなってくれませんでしたね（まぁ僕が悪いんですけど）
ABC159 A- The Number of Even
[偶数奇数,parity]
2つの数を足したら偶数になるような2つの数の選び方は、偶数+偶数か奇数+奇数ですよ。っていう問題.
ついでに、N個のボールから2つを選ぶ（順序はどうでもいい）ときの選び方はN×(N-1) / 2だよ。っていう。
(まずN個から1個選ぶのでN通り。次に(N-1)個選ぶのでN-1通り.A,Bの順で取ったものと、B,Aの順で取ったものが含まれているから2で割る(ここ上手く説明できないね))
ABC159 B - String Palindrome
[Palindrome,回文]
この問題面白くて、実はSが回文で、Sの前半も回文だったら、Sの後半調べなくていいんだよ。すごくね？
どういうことかって言うと、まず、Sが回文であるとき、S1をSの前半の文字列cを任意の文字として次のように表せます。
(cはいわゆるSの真ん中の文字）
S1+c+S1
Sが回文だから、cを対称に、左側と右側は同じだからS1+c+S1と書けるよ
そして、左のS1と右のS1は同じ文字列なんだから、どっちかが回文でどっちかが回文じゃないなんてことはありえない。
だから
- Sが回文かどうかを見る
- Sの前半が回分かどうかを見る
この2つだけで答えが求まるのじゃ
ABC159 C- Maximum Volume
[小数を使えますか,体積の最大化]
立方体が一番おっきいの！！
この問題については僕が扱えるものではありません。
おとなしく公式の解説動画を見ようね
ABC159 D- Banned K
[連想配列]
まず、入力で与えられるn個の数字をmapにぶち込んでいって〜…
あーコード見たほうがわかりやすいかな
#include <bits/stdc++.h> using namespace std; using ll =long long; #define For(i, a, b) for(int i = (a) ; i < (b) ; ++i) #define rep(i, n) For(i, 0, n) int main() { ll n ; cin >> n ; map<ll,ll> my_m; vector<ll> a(n); rep(i,n) cin >> a[i]; rep(i,n){ my_m[a[i]] ++; } ll max_ans = 0; // max_ans に、どの数字も消さなかったときの条件を満たす組み合わせの数を入れておく for(auto x:my_m){ max_ans += (x.second *(x.second - 1)) / 2; } rep(i,n){ ll x = my_m[a[i]] ; ll ans = max_ans; ans -= (x * (x -1) ) / 2; // 今見ている数字(a[i])は除くのをうまいことする x--; ans += (x *(x - 1)) / 2; cout << ans << endl; } }
にゃーん（がんばれ〜〜！！）
夏は終わらない
メインコンテンツです。今日のメインディッシュ。はい。
ABC159 E- Dividing Chocolate
[bit全探索,天才実装]
ホワイトチョコレートと普通のチョコレートが混ざった板チョコなんて現実に存在しますか？しません。しません。しないで。
あ〜〜〜…あるかもしれない
H行あるとき、割れ目となる可能性がある場所はH-1個というのはおわかりいただけますでしょうか？
まぁ分からなかったら手を動かしてみてください。僕は手を動かしました。（ブログに図を乗っけるのってめちゃくちゃめんどくさいんでやりません)
で、切れ目入れる位置ってH = 10のときで 2 ^ 9 なんだよ〜 （つまり512通り)
その全部の組み合わせについてどこの列を割るかを考えていくんだけど、このどの列を割るかっていうのは貪欲にしていけばいい。
問題のサンプルを取ってこよう。あ〜やっぱやめた。
ま、bit全探索ってムズカシイヨね！！ 自分が見返したとき用に実装だけ貼っておくわ〜〜
// 2 ^ (h - 1) 通りのbit 全探索. // h = 10 のときは、 000000000 ~ 11111111 までの512通りを試すよ ll ans = INF; // でかい値 for(ll tmp = 0; tmp < ( 1 << h-1); tmp++){ bitset<10> bit(tmp); ll ret = 0; // そのbitのときの操作回数 rep(i,h){ if(bit.test(i)) { ret ++; } } //debug(ret); vector<ll> count(11,0); ll change = 0; //count[change]に入れていく bool cant = false; for(ll x = 0 ; x < w ; x++){ change = 0; for(ll y = 0; y < h ; y++){ if(choco[y][x] =='1') count[change] ++; if(count[change] > k){ if(x == til_w){ // このbitは無理 cant = true; break; } else { // ret + 1して countを全て0にする ret++; rep(i,11) count[i] = 0; x--; break; } } //debug(count[change]); if(bit.test(y)) change ++ ; } if(cant) break; } if(cant) continue; chmin(ans,ret); //debug(ret); } cout << ans << endl;
...自分で見るようだとしても見返すには少し長すぎるコードですね。
次僕が見たとき泣いちゃいそう…（まぁ、頑張れ〜〜）
いや〜だめかな…だめだよね…じゃあこのコードをすこし精錬して図も加えてあげよう。
// 2 ^ (h - 1) 通りのbit 全探索. // h = 10 のときは、 000000000 ~ 11111111 までの512通りを試すよ // 今回は操作回数の最小を求めるので、ansをINFにしておきます。 ll ans = INF; // でかい値 for(ll tmp = 0; tmp < ( 1 << h-1); tmp++){ bitset<10> bit(tmp); ll ret = 0; // そのbitのときの操作回数 rep(i,h){ if(bit.test(i)) { // 行で割る個数を ret に足していきます。 // 010のとき、H = 4で、2行目と3行目の間でチョコを割ることを示す。 // 010のとき、retは+1されます。 ret ++; } } vector<ll> count(11,0); ll area = 0; // area（領域,あとで図解)ごとのホワイトチョコレートの数をcountに入れていく。 bool cant = false; //1つの領域の1つの列に、K個より多くホワイトチョコレートがあった場合は、そのbitでのチョコの割り方では、どの区域にもK個以下のチョコというのは達成出来ない。 // そういうときは cant (できない) を true にする。 for(ll x = 0 ; x < w ; x++){ area = 0; for(ll y = 0; y < h ; y++){ if(choco[y][x] =='1') count[area] ++; if(count[area] > k){ if(x == til_w){ // このbitは無理 cant = true; break; } else { // ret + 1して countを全て0にする ret++; rep(i,11) count[i] = 0; x--; break; } } if(bit.test(y)) area ++ ; // areaが変わるときというのは、割った境界をまたぐとき } if(cant) break; } if(cant) continue; chmin(ans,ret); } cout << ans << endl;
長いけどさっきよりマシそうなコードをやっつけで書きました。 さて図解するぞ…
問題の入力例1をちょっとだけ図で書きました。
— 瑞々しぃにぼし@バナナのナナチはバナナナチ (@niboshi_wakai) 2020年3月22日
