久々に Atcoder やってみた.ABC276 (A,B,C)

A 問題

後ろから数えてみました。
a が出たら現在地をメモして break 。
最後まで a が出てこなかったら -1。

a.cpp

#include <iostream>
using namespace std;

int main() {
	string s; cin >> s;
	bool flag = false; int ans = 0;
	for (int i = s.size() - 1; i >= 0; i--) {
		if (s[i] == 'a') {
			flag = true;
			ans = i + 1;
			break;
		}
	}
	if (flag) cout << ans;
	else cout << -1;

	//while (1) {}
	return 0;
}

B 問題

グラフの問題
入力から無効グラフを作り、
各要素数と、昇順に cout(or print) すれば OK

b.cpp

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int N, M; cin >> N >> M;
	vector<vector<int>>g(N+1);
	int A, B;

	for (int i = 0; i < M; i++) {
		cin >> A >> B;
		g[A].push_back(B);
		g[B].push_back(A);
	}

	for (int i = 1; i <= N; i++) {
		
		if (g[i].size() > 0) {
			cout << g[i].size() << " ";
			sort(g[i].begin(), g[i].end());
			for (int l = 0; l < g[i].size(); l++) {
				cout << g[i][l] << " ";
			}
			cout << "\n";
		}
		else
			cout << 0 << "\n";
	}

	//while (1) {}
	return 0;

}

C 問題

"辞書順" , "K-1 番目" がキーポイント。
入力例を参考に考察します。

右から一個ずつ眺めて、徐々に数字が下がっているはずが、
以下の矢印のポイントを境に数字が上がっていきます。

　↓
3 1 2
　　　　　　　↓
9 8 6 5 10 3 1 2 4 7

K-1 番目ならば以下の矢印以降の数字を眺めて
K-1 番目の並びを作れば OK では無いでしょうか？

↓
3 1 2
           ↓
9 8 6 5 10 3 1 2 4 7

この発想を入力例 2 で具体的に考えます。
#STEP 1 切れ目で分ける
           
  input : 9 8 6 5 10 3 1 2 4 7
          ||
  group1 : 9 8 6 5 10
  group2 : 3 1 2 4 7

  group1 は変更しなくて OK
  group2 を辞書順に K-1 とすれば OK

#STEP 2 group2 を辞書順で K-1 に並べ替える

　3 1 2 4 7　の一つ前は
  2 7 4 3 1  です。**理由は調べましょう(笑)
  

上記を前提にコードに落としてみました。
以下は一例でなので、書き方は色々あると思います。

c.cpp

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;

int main() {
	int N; cin >> N;                                   //input
	vector<int>P(N, 0);                                
	for (int i = 0; i < N; i++)                        
		cin >> P[i];                                   

	int stp = 1; int num = P[N - 1];int ref = 0;       
	vector<int>buff; buff.push_back(P[N-1]);           

	for (int i = N - 2; i >= 0; i--) {                 //#STEP1
		if (num > P[i]) {                              
			num = P[i];                                
			buff.push_back(P[i]);                      
		}
		else{
			ref = P[i];                                
			stp = i;                                   
			break;
		}
	}
	                                                   
	buff.push_back(ref);                               
	sort(buff.begin(), buff.end());                    
                                                       
	if (N>2){                                          //STEP2:
		
		for (int i = 0; i < buff.size(); i++) {
			if (buff[i] == ref){
				P[stp] = buff[i - 1];
				ref = buff[i - 1];
			}
		}
		sort(buff.begin(), buff.end(), greater<int>());
		
		for (int i = 0; i <= stp; i++)
			cout << P[i] << " ";
		for (int j = 0; j < buff.size(); j++)
			if(buff[j] != ref)
				cout << buff[j] << " ";
	}
	else {
		for (auto x : buff)
			cout << x << " ";
	}

	//while (1) {}
	return 0;

}