質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

1848閲覧

AtCoder:ABC80 D問題について

cinnamoroll

総合スコア14

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

1クリップ

投稿2018/05/29 14:11

編集2018/05/29 14:13

前提・実現したいこと

AtcoderのABC80のD問題について,作成したプログラムがシステムテストを通らない(誤りを含む)理由がわかりません.
使用言語はC++です.

問題ページ

方針

それぞれのチャンネルに対してmapを用いて番組の放送開始時間と終了時間をキーと値にとる.
すべての時刻で同時に録画器を動かす必要のある数を求め,その最大値が答えである.
ただし,同じチャンネルで連続した時間(ex.時刻1-3と時刻3-5)に番組がある場合,別々に計算すると放送前の待機時間0.5が重複してしまうため,1つの番組として扱う.

発生している問題・エラーメッセージ

基本的な挙動は正しいが,テストセットの一部でWA(誤った解が出力された状態)になる.

該当のソースコード

#include<iostream> #include <stdio.h> #include<string> #include <cmath> #include <algorithm> #include <vector> #include <cstdint> #include <queue> #include <map> #include <set> #define MOD 1000000007 #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr) #define dump(x) cout << #x << " = " << (x) << endl; #define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; typedef long long ll; using namespace std; int main(){ int n,c; cin >> n >> c; map <int,int>channel[c+1]; REP(i,n){ int s,t,C; cin >> s >> t >> C; channel[C].insert({s,t}); } REP(i,c){ int key = 0,t = 0; ITR(itr,channel[i+1]){ if(itr->first == t){ // 連続した時間の番組があれば,1つにまとめる. channel[i+1][key] = itr->second; channel[i+1].erase(itr); } key = itr->first; t = itr->second; } } const int NMAX = 100010; int s[NMAX] = {}; REP(i,c){ ITR(itr,channel[i+1]){ s[itr->first-1]++; //待機時間があるため,録画器は番組開始の1手前の時刻から使用 s[itr->second]--; } } /* REP(i,c){ cout << i+1 << endl; ITR(itr,channel[i+1]){ cout << itr->first << " " << itr->second << endl; } } */ int ans = 0; REP(i,NMAX-1){ s[i+1] += s[i]; ans = max(ans,s[i+1]); } cout << ans << endl; return 0; }

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

元のコードでは連続している番組をまとめた際にkeyの設定を間違えていると思います。3つ連続した番組があると3つ目の番組の終了時間が期待とは異なるエントリーに記録されてしまうと思います。そのため折角削除したエントリーがまた復活してしまいますよね・・・


また、自分の環境はAtcoderの環境とは違うのですが、(cygwin, g++ (GCC) 6.4.0, g++ -std=gnu++1y -O2でコンパイル)元のコードだと連続番組を統合する論理で、itrがおかしな要素を指し示したり無限ループに陥いる現象が起きました。

C++の標準ライブラリーに暗いのでここを見た上で感じた(ほとんど推測)で修正してみてますが、以下のコードに直したところ少なくとも無限ループはしなくなり番組の統合も期待通りに行われているように見えました。

問題ではないかと感じたのは「eraseしたiteratorに対してfirstやsecondにアクセスしたり++演算子で次の要素に正しく位置付けられることを前提としている」点です。それをしないようにしたのが下記のコードです。

C++

1for(auto i = 1; i <= c; i++) { 2 int key = 0, t = 0; 3 map<int, int> &ch = channel[i]; 4 for (auto itr = ch.begin(); itr != ch.end(); ) { 5 if (itr->first == t) { 6 t = ch[key] = itr->second; 7 itr = ch.erase(itr); 8 } else { 9 key = itr->first; 10 t = itr->second; 11 ++itr; 12 } 13 } 14}

(すみませんが、関係ない部分も好みに合わせて変更しました。改悪になってなければよいのですが・・・)

投稿2018/05/30 02:20

KSwordOfHaste

総合スコア18392

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

cinnamoroll

2018/05/30 13:46

イテレータの扱いに不慣れで文法に怪しさを感じてはいましたが,3つの連続した番組の連結をテストしたとき表面上では問題なさそうだったので見逃していました... 回答ありがとうございました!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問