問題文

左右一列に $N$ 個のマスが並んでおり、左から $i$ 番目のマスの高さは $H_{i}$ です。

あなたは各マスについて $1$ 度ずつ次のいずれかの操作を行います。

マスの高さを $1$ 低くする。
何もしない。

操作をうまく行うことでマスの高さを左から右に向かって単調非減少にできるか求めてください。

制約

入力は全て整数である。
$1 \leq N \leq 10^{5}$
$1 \leq H_{i} \leq 10^{9}$

解法の方針

左から順に見ていって、減らせるものは1減らす
　ここで、減らせるもの＝左の数字より大きいもの

　つまり、一番左の数字は必ず減らせる
操作が終わったら、条件を満たしているか確認する

注意点

　最初、次のように解こうとしたが、testcase_03、04でWAが出てしまった

　誤った手順

左の数－右の数＝1のとき、左の数を1減らす
操作が終わったら、条件を満たしているか確認する

　これだと、(1,2,2,2,1)のようなものが来たとき、Noを出力してしまう

　これは、左側だけ見れば成り立っているが、右から2番目の2に来た時に減らしても、それまでの2が減っておらず、合わなくなるためである

　減らせるものは減らすという貪欲法チックな思考が必要

解答例

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); ++i)
 
int main(){
  int n;
  cin>>n;
  if(n==1){
    cout<<"Yes"<<endl;
    return 0;
  } 
  vector<int> vec(n);
  rep(i,n) cin>>vec[i];
  vec[0]-=1;
  rep(i,n-1){
    if(vec[i]<vec[i+1]){
      vec[i+1]-=1;
    }
  }
  rep(i,n-1){
    if(vec[i]>vec[i+1]){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
  return 0;
}

学んだこと

貪欲法的考え方は常に持っておくべき

後ろから見ると考えやすいかも

2019-08-12

ABC137 D問題 Summer Vacation

atcoder.jp

問題文

$N$ 件の日雇いアルバイトがあり、 $i$ 件目の日雇いアルバイトを請けて働くと、その $A_{i}$ 日後に報酬 $B_{i}$ が得られます。

あなたは、これらの中から $1$ 日に $1$ 件まで選んで請け、働くことができます。

ただし、請けたことのある日雇いアルバイトは選べません。

今日から $M$ 日後まで( $M$ 日後を含む)に得られる報酬の合計の最大値を求めてください。

なお、日雇いアルバイトは今日から請けて働くことができます。

制約

入力は全て整数である。
$1 \leq N \leq 10^{5}$
$1 \leq M \leq 10^{5}$
$1 \leq A_{i} \leq 10^{5}$
$1 \leq B_{i} \leq 10^{4}$

解法の方針

最終日から数えていき、できるようになった仕事を集合に追加する
集合にはprioriuty_queueを用いる

注意点

最終日から遡る必要がある

　　　貪欲法を用いるには単純比較可能である必要があり、賃金要素だけにしたいため

解答例

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main(){
  int n,m;
  cin>>n>>m;
  vector<vector<int>> jobs(m);   //何日目に解禁される仕事かを保持するvector
  rep(i,n){
    int a,b;
    cin>>a>>b;
    if(a>m) continue;
    jobs[m-a].push_back(b);   //m-a日目に解禁される要素として追加　比較はbでするのでbだけ追加
  }
  priority_queue<int> q;
  ll ans=0;
  for(int i=m-1;i>=0;--i){
//m-1日目から遡ってvectorの要素をpriority_queueに移す
    for(int b : jobs[i]){
      q.push(b);
    }
    if(!q.empty()){   //空でtop()すると壊れる
      ans += q.top();   //ansに収入を足す
      q.pop();   //やった仕事は消す
    }
  }
  cout<<ans<<endl;
}

学んだこと

逆順に見ていく

　　　今回の問題では、日数がたつにつれてできる仕事が減っていく

　　　そのため、最終日から遡っていくことで、賃金だけで比較できるようになり、次の貪欲法が使えるようになる

　　　だんだん絞られていくような問題では、後ろからゴールから考えるという手法も覚えておきたい

貪欲法

　　　一番いいものを順番に選んでいくやり方

　　　何をもって「一番いい」か決めるために、比較要素を一つに絞る必要がある

　　　次に書くpriority_queueとも関わりがある

priority_queue

　　　.push()で要素を追加し、.top()で取り出すと、大きいものから順に出てくるコンテナ

　　　知らなかったのでいちいちソートするのか？と思っていたが、これを使うとO(logN)でできるらしい

2019-08-11

ABC137 C問題

atcoder.jp

問題文

文字列 $a$ に含まれる文字を何らかの順序で並べることで得られる文字列を $a$ の アナグラム と呼びます。

例えば、greenbin は beginner のアナグラムです。このように、同じ文字が複数回現れるときはその文字をちょうどその回数だけ使わなければなりません。

$N$ 個の文字列 $s_{1}, s_{2}, \dots, s_{N}$ が与えられます。それぞれの文字列は長さが $10$ で英小文字からなり、またこれらの文字列はすべて異なります。二つの整数 $i, j$ $(1 \leq i < j \leq N)$ の組であって、 $s_{i}$ が $s_{j}$ のアナグラムであるようなものの個数を求めてください。

制約

$2 \leq N \leq 10^{5}$
$s_{i}$ は長さ $10$ の文字列である。
$s_{i}$ の各文字は英小文字である。
$s_{1}, s_{2}, \dots, s_{N}$ はすべて異なる。

解法の方針

入力文字列をsort
mapを用いて同じものを数える
それぞれの(count)(count-1)/2を計算する

注意点

10^5同士をかけるところでllにしないとオーバーフローする

解法1(map)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {
	int n;
	cin >> n;
	map<string, int> mp;
	rep(i, n) {
		string s;
		cin >> s;
		sort(s.begin(), s.end());
		mp[s]++; //ない要素が来たら0初期化
	}
	ll ans = 0;
	for (auto& p : mp) {
		int s = p.second;
		ans += (ll)s*(s - 1) / 2;
	}
	cout << ans << endl;

解法2(vector)

文字列を入れたvectorをsortして隣同士が一致するかどうか見る

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main(){
  int n;
  cin>>n;
  vector<string> vec;
  rep(i,n){
    string s;
    cin>>s;
    sort(s.begin(),s.end());
    vec.push_back(s);
  }
  sort(vec.begin(),vec.end());
  ll count=1;
  ll ans=0;
  rep(i,n-1){
    if(vec[i]==vec[i+1]){
      count++;
    }else{
      ans+=count*(count-1)/2;
      count=1;
    }
  }
  ans+=count*(count-1)/2;
  cout<<ans<<endl;
}

学んだもの

map-連想配列

　１つ目の要素をキーにした配列

　持っていないキーへの操作が来たら0初期化して追加してくれる

unordered-map

　順番を気にしない代わりに速いmap

　今回はこれでも通る

「組み合わせの数」の数え方

　総数を数え上げ、(総数)(総数-1)/2を計算する

範囲for文

　for(代入される変数 : 配列名)で書ける

　続く{}内に代入される変数を書くことで、指定した配列の要素が順番に代入される

　代入される変数の宣言規則は以下（下のURLより）

変数宣言	e を変更可能か？	コンテナ内の要素を変更可能か？
const auto& e	No	No
auto& e	Yes	Yes
auto e	Yes	No

範囲for文 - cpprefjp C++日本語リファレンス

勉強記録

英語とプログラミングをやります。

ABC136 C問題 Build Stairs

問題文

制約

ABC137 D問題 Summer Vacation

問題文

制約

ABC137 C問題

問題文

制約