ABC072
A問題
最初max(A-B,0)をmin(A-B,0)と書いて１WA
ソースコードは省略
B問題
文字列の偶数文字目(1-indexed)を抜き取って出力
C問題
概要：長さNの整数列に±1(or0)したとき同じ数にできる数の個数の最大値を求めよ
制約が0≦Ai<10^5と小さいので素直に10^5の大きさのカウント用配列を作ってcnt[i-1]+cnt[i]+cnt[i+1]の最大値を求めれば良い（i = 0のときに注意)
D問題
概要：長さNの整数列を隣合う２数を交換する操作をしてAi≠i(1≦i≦N)を満たす数列にするとき最小の交換回数を求めよ
bool型配列を用意し、Ai=iとなる場所をtrueにする
あとはtrueが連続するところを優先してfalseに変えていく
（例えば4,2,3,1という数列の場合4,2を入れ替えるより2,3を入れ替えたほうが交換回数が少なくできる）
yukicoder No.92を解いた
DPで解いた
dp[i][j]:=i(<K)回道を通ったときにj番目の街にいるかどうかという２次元配列を作って０で初期化
最初の1回目はd1に一致する町全てに１を代入（開始地点は任意のため）
i(1<i≦K)回目はi-1回目にいる可能性のある町から行ける町に１を代入すれば良い
競プロで使えそうな関数とか
タイトル通り
関数
std::min()
std::max()
言わずと知れた最小最大を返す関数
DPを更新するときとかによく使う
ex)dp[i][j] = max(dp[i-1][j],dp[i-1][j-A[i]])
ナップザックDP
std::sort()
ソートを一から実装する必要がないときは普通これを使う
ex)sort(array,array+N)
ex2)sort(vector.begin(),vector.end())
昇順ソート
std::fill()
配列とかを初期化するときとかに使う
ex)fill(array,array+N,0)
配列0埋め
std::max_element()
std::min_element()
最小値、最大値のイテレーターを返す関数
ポインタを使うと値を得ることができる
ex)cout << *max_element(array,array+N) << endl
配列の最大値を出力
std::accumulate()
総和を返す関数
関数オブジェクトを使うと総乗を求められるらしいけど普通に実装したほうが早い
ex)sum = accumulate(array,array+N,0)
配列の総和を取得 第三引数は初期値
std::abs()
絶対値を返す関数
ex)cout << abs(num) << endl
std::to_string()
数値をstring型にするときに使う
ex)string s = to_string(3.1415)
std::stoi()
string型を整数型にするときに使う
c++11だとコンパイル失敗するのとlong long型にするときにはstoll()にすることに注意
ex)int num = stoi("810")
std::swap()
２つの変数の値を交換するときに使う
ソート実装するときとか並び替えのシミュレーション時によく使う
ex)if(A[i] > A[i+1])swap(A[i],A[i+1])
昇順ソートするときの交換する部分
using std::swapと先に宣言しないとコンパイルエラーが起きる（？）
以下参考にしたページ等
yukicoder No.7を解いた
21言ったら負けのゲームのように相手に確実に負けとなる数を渡せるかどうかを配列作って管理すれば良い
ABCかと思ったらARCだった(ARC080)
タイトル通り
何を言ってるのか わからねーと思うが
ABC参加しようと思ってARC参加ボタン押してました
初めて１時間でD問まで解けたのに悲しい
以下自分のガバガバ解答
C
長さNの数列与えられて隣り合う２数の積が4の倍数になるように並び替えできるかという問題
２数の積が4の倍数になるとき、片方が４の倍数または両方が２の倍数である必要があるから～みたいな感じで解いた
main(){
int N,a;
int cnt[3] = {};//それぞれの倍数の数 x1,x2,x4
cin >> N;
for(int i = 0;i < N;i++){
cin >> a;
if(a % 4 == 0)cnt[2]++;
else if(a % 2 == 0)cnt[1]++;
else cnt[0]++;
}
if(cnt[0]){//x1が存在する
if(cnt[1])cnt[0]++;//2の倍数を一纏めに
if(cnt[0] <= cnt[2]+1) cout << "Yes" << endl;//4の倍数を交互に配置できる場合
else cout << "No" << endl;
}else{
cout << "Yes" << endl;
}
}
D
同じ数を隣接して表示しなさいって問題
yukicoderのNo.401 数字の渦巻き
みたいに渦巻き状に配置すれば必ず隣接するだろうと思って解いた
かなり汚いコードになってるからいずれ書き直す
（追記）解説読んでから気づいたけど渦巻き状にしなくても蛇状にすればいいっぽい
main(){
int H,W,N;
pair<int,int> p[10000];
cin >> H >> W >> N;
for(int i = 0;i < N;i++){
int a;
cin >> a;
p[i] = make_pair(a,i+1);
}
sort(p,p+N);
int next = p[0].second;//次の数
int r = p[0].first;//次の数の残り数
int muki = 0;//→↓←↑
int x = 0,y = 0;//座標
int num = 0;//次の配列のインデックス
int map[100][101];
for(int i = 0;i < H;i++){
for(int j = 0;j < W;j++){
map[i][j] = -1;//初期化
}
}
for(int i = 0;i < H*W;i++){
if(x < 0 || x >= W || y < 0 || y >= H ||
map[y][x] != -1){
if(muki == 0){x--;y++;}
if(muki == 1){y--;x--;}
if(muki == 2){x++;y--;}
if(muki == 3){y++;x++;}
muki = (muki + 1) % 4;
}
if(!r){
r = p[++num].first;
next = p[num].second;
}
map[y][x] = next;
r--;
if(muki == 0)x++;
if(muki == 1)y++;
if(muki == 2)x--;
if(muki == 3)y--;
}
for(int i = 0;i < H;i++){
for(int j = 0;j < W;j++){
printf("%d%c",map[i][j],j==W-1?'\n':' ');
}
}
}
