2020年 12月 12日 肉を切らせて骨を断つ
まえがき
本文
なぞなぞ おじいさんが生まれた朝に買ってきた時計,な~んだ??
答えを見る
大きなのっぽの古時計
はい,markdownの新しい使い方を学んでしまいました.やったね.
メモ
- 折りたたみ <details><summary>見せたい部分</summary>隠したい部分の文章ぶらぶらぶらぶら</details>
解説記事ではありません!!!!!!!!!!!!!!!!!!!!!!!
解説記事ではありません!!!!!!!!!!!!!!!!!!!!!!!
解説記事ではありません!!!!!!!!!!!!!!!!!!!!!!!
この記事は青少年の発育に大きな支障をきたす場合があります!!
解説記事ではありません!!!!!!!!!!!!!!!!!!!!!!!
この記事は青少年の発育に大きな支障をきたす場合があります!!
解説記事ではありません!!!!!!!!!!!!!!!!!!!!!!!
この記事は青少年の発育に大きな支障をきたす場合があります!!
解説記事ではありません!!!!!!!!!!!!!!!!!!!!!!!
解説記事ではありません!!!!!!!!!!!!!!!!!!!!!!!
この記事は青少年の発育に大きな支障をきたす場合があります!!
解説記事ではありません!!!!!!!!!!!!!!!!!!!!!!!
この記事は青少年の発育に大きな支障をきたす場合があります!!
解説記事ではありません!!!!!!!!!!!!!!!!!!!!!!!
この記事は青少年の発育に大きな支障をきたす場合があります!!
今日解いた問題WTF
ABC166 F- Three Variables Game
A,B,Cがあって,文字列が入力でN回与えられる
文字列がABのとき,「Aに+1,Bに-1」か「Aに-1,Bに+1」のどちらかの操作をする.
(与えられる文字列は"AB", "BC", "CA"のいずれか)
このとき,操作の途中でA,B,C < 0 にならないように操作することができますか?っていう問題
暗黒微笑おじさん大勝利チョンパァコード(230行くらいある)
#include <bits/stdc++.h> using namespace std; using ll =long long; typedef pair<int,int> P; #define For(i, a, b) for(int i = (a) ; i < (b) ; ++i) #define rep(i, n) For(i, 0, n) #define debug(x) cerr << #x << " = " << (x) << endl; void coY() {cout <<"Yes"<<endl;} void coN(){cout <<"No"<<endl;} //Write From this Line int main() { int n, a, b, c; cin >> n >> a >> b >> c; int x = 0, y = 0, z = 0; vector<char> ans(n); queue<int> qx; // AB queue<int> qy; // BC queue<int> qz; // AC rep(i,n){ string s; cin >> s; if(s == "AB"){ qx.push(i); x++; a--; b--; ans[i] = 'A'; int ind; if(a < 0 || b < 0){ // 両方負 if(a < 0 && b < 0){ if(x >= 2){ //2回取り出して,A,Bと振り分ける ind = qx.front(); qx.pop(); x--; ans[ind] = 'A'; a += 2; ind = qx.front(); qx.pop();x--; ans[ind] = 'B'; b += 2; } else { if(y){ // BCがある ind = qy.front(); qy.pop(); y--; ans[ind] = 'B'; b += 2; ind = qx.front(); qx.pop(); x--; ans[ind] = 'A'; a += 2; } else if(z){ //ACがある ind = qz.front(); qz.pop(); z--; ans[ind] = 'A'; a += 2; ind = qx.front(); qx.pop(); x--; ans[ind] = 'B'; b += 2; } else { coN(); return 0; } } } else { if(a < 0){ // aだけ0 ind = qx.front(); qx.pop(); x--; ans[ind] = 'A'; a += 2; } else { // bだけ0 ind = qx.front(); qx.pop(); x--; ans[ind] = 'B'; b += 2; } } } } if(s == "BC"){ qy.push(i); y++; b--; c--; ans[i] = 'B'; int ind; if(b < 0 || c < 0){ // 両方負 if(b < 0 && c < 0){ if(y >= 2){ //2回取り出して,B,Cと振り分ける ind = qy.front(); qy.pop(); y--; ans[ind] = 'B'; b += 2; ind = qy.front(); qy.pop();y--; ans[ind] = 'C'; c += 2; } else { if(z){ // ACがある ind = qz.front(); qz.pop(); z--; ans[ind] = 'C'; c += 2; ind = qy.front(); qy.pop(); y--; ans[ind] = 'B'; b += 2; } else if(x){ //ABがある ind = qx.front(); qx.pop(); x--; ans[ind] = 'B'; b += 2; ind = qy.front(); qy.pop(); y--; ans[ind] = 'C'; c += 2; } else { coN(); return 0; } } } else { if(b < 0){ // bだけ0 ind = qy.front(); qy.pop(); y--; ans[ind] = 'B'; b += 2; } else { // cだけ0 ind = qy.front(); qy.pop(); y--; ans[ind] = 'C'; c += 2; } } } } if(s == "AC"){ qz.push(i); z++; a--; c--; ans[i] = 'A'; int ind; if(a < 0 || c < 0){ // 両方負 if(a < 0 && c < 0){ if(z >= 2){ //2回取り出して,A,Cと振り分ける ind = qz.front(); qz.pop(); z--; ans[ind] = 'A'; a += 2; ind = qz.front(); qz.pop();z--; ans[ind] = 'C'; c += 2; } else { if(x){ // ABがある ind = qx.front(); qx.pop(); x--; ans[ind] = 'A'; a += 2; ind = qz.front(); qz.pop(); z--; ans[ind] = 'C'; c += 2; } else if(y){ //BCがある ind = qy.front(); qy.pop(); y--; ans[ind] = 'C'; c += 2; ind = qz.front(); qz.pop(); z--; ans[ind] = 'A'; a += 2; } else { coN(); return 0; } } } else { if(a < 0){ // aだけ0 ind = qz.front(); qz.pop(); z--; ans[ind] = 'A'; a += 2; } else { // cだけ0 ind = qz.front(); qz.pop(); z--; ans[ind] = 'C'; c += 2; } } } } } coY(); rep(i,n){ cout << ans[i] << endl; } }
やべ~WWW
これはね,ツカレタ(ツカレタ)
私は頭を動かした
とりあえず,全探索しようとすると,2N通りがあって,N<=105なので無理.(ABが来たときAを+1するかBを+1するかの2通りがN回)
次に何となくで,ABが来たときAもBも-1する.BCが来たときBもCも-1, ACが来たらAもCも-1っていう感じに一旦しておく.(こういう,とりあえず悪い方に倒しておく,みたいな考え方を使って,後から許せるかどうか,みたいな考え方を使う問題,どっかにあったよね~~)
で,-1し続けた結果A or B or C < 0 になったとき,どっかの操作で0になったものを+1してたってことにする(どっかの操作では-1した,ってことにしてたので,+2することで実質的にどっかの操作で+1したってことになる)
で,A<0 になった時を考えると,
「ABのときにAを+1する操作をしてたことにする」か「ACのときにAを+1する操作をしてたことにする」
のどっちを選べばいいか分からねえなあ…って思って3秒諦めました.
あさか said 「それ,もうちょっと詰めれば多分ACするんじゃね」
私は頭を動かした
k 回目の操作で AかBかCが負になったときを考えます.
-1を2回するので…?
負になったときの値(AやB,Cの値)は-1しかない.
-1になるとしても,それは最大でも2個(AとB,BとC,AとCと言った組み合わせ)が-1になる
-1になったときに,k回目より前(j回目とする)の操作を隠蔽?(過去を改変?)したいです.
一回過去を改変すれば,1個(AかBかC)を正(+1)にすることが出来る!!
すると,現在(k回目)と過去(j回目)を改変すれば,負になった値を2個正に戻すことができりゅっ♡
流れを追って見よう!!
今,(A,B,C) = (1,3,0)のとき
s[0] = "AB";
とりあえずAとB両方とも-1
(A,B,C) = (0,2,0)
s[1] = "AC";
(A,B,C) = (-1,1,-1)
はい,このとき,s[0] = "AB"では,Aを+1だったことに(過去を改変)して,
s[1] = "AC"では,Cを+1だったことにします.(現在を改変?)(実装では,とりあえずAもCも-1した後に改変しているので)
すると
(A,B,C) = (1,3,0)
s[0] = "AB";
(A,B,C) = (2,2,0)
s[1] = "AC";
(A,B,C) = (1,2,1)
ただ,ここで更に問題となるのが,
s[1] ="AC"のとき,このACはAの+に使うのかCの+に使うのかということです.
先程の例では,実はs[1]でAを+にすると,Cが-になってしまうことが私には確かめられます
先に簡単なことから説明しておきます.
- s = ABで,AかBの片方だけが負の値になったとき
この時は簡単で,負になった方を+にするだけで解決出来ます.(現在の改変のみ)
過去の改変は必要ないですね.
はい,簡単(にぼし視点)なことは終わり.
難しいところ行きます.
先程のs[1] ="AC"のとき,このAC(現在のAC)はAの+に使うのかCの+に使うのかということですが,
過去に操作を確定していないACが1個以上(これは,Aを+するか,Cを+するか,まだ決まっていないようなAC, 暫定的にAもCも-1していたやつのこと)存在する時
現在のACはどっちの+に使ってもいい.
過去のACはAの+に,現在のACはCの+に.っていう感じに適当に決めてやればいい
過去に操作を確定していないABが一個以上あるとき
現在のACはCの+に使う.
過去のABをAの+に使う.
これで,AもCも正に戻すことが出来ます.
過去に操作を確定していないBCが一個以上あるとき
現在のACはAの+に使う
過去のBCをCの+に使う
過去に操作を確定していないACもABもBCも無いとき(悲しい)
このときは,Noを出力することになります.
(AかC,どちらか一つしか正に戻してあげることができない ToT)
こんな感じで改変を進めつつ,あ,無理~~になった瞬間Noを出力ってやればイケソウだなって思って実装を頑張ってやったらAC(これは正解の意味)しました(やったね)
コメント
まぁ,未証明ACっすけど,後付けでなんでOKなのかな~って理由を超雑に考えてみます.
(と,言いつつ解いてるときに考えていたことも混ざってる)
A<0, C<0 になったとき,
ACを使ってどっちかを正にしてあげる
で,ACの余り(過去に操作を確定していないAC)が無いとき
ABを使うか,BCを使うかですが,どっちかがあるならどっちを使っても良いっていうことを示せば,多分先程の解法は証明出来るんじゃないかなって雑に思っています(知らないので)
負になった値(AやBやC)を正の操作に戻すことを,「Aを救う」「Bを救う」「Cを救う」などと表現します.
だから,さっきのA<0,C<0になったときっていうのは,
「AとCを救うことを考えなきゃいけないとき」っていうことなんですよね.
ACが足りないなら,ABかBCを使ってAかCのどちらかを救わなきゃ行けないんですけど,
このとき,どちらを使っても将来的にBを救うために使えるもののかずが変わらないって言うのが分かるじゃないですか〜!!
で,まぁこれが多分AとCを救うときにAC以外にABを使うかBCを使うかどっちでもいい,ってことを示すのに役立つと思うんスよね~(情報学部生並の感想)
あとがき
ACしたときの感情,な~んだ??
答えを見る
気持ちいい
