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

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

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

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

Q&A

解決済

1回答

249閲覧

AtCoder:ABC98 D問題について

cinnamoroll

総合スコア14

C++

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

2グッド

1クリップ

投稿2018/05/29 14:33

前提・実現したいこと

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

問題ページ

方針

満たすべき条件は,与えられた数を二進数表記したときAlからArの各2^kの位について,1であるようなAiが1つ以下であることと同値である.(証明略)
たとえば,
10001
00100
01010
は条件を満たすが,
10001
00100
01011
は条件を満たさない.

ここで,n個の数を2bitで2次元配列で管理する.
ある区間[l,r]で条件をみたすとき,l+1,l+2, ... , r-1も条件を満たすので,
rを固定しそれぞれのrに対して条件を満たす最小のlを求めることでO(n)で実装をする.

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

基本的な挙動は正しいが,テストセットの一部で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 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; cin >> n; // n個の2bit表記 int a[n][20] = {}; REP(i,n){ int num; cin >> num; int bit = 0; while(num != 0){ a[i][bit] = (num % 2); num /= 2; bit++; } } /* REP(i,n){ REP(j,20){ cout << a[i][19-j]; } cout << endl; } */ int ans = 0; int s[20] = {}; // Aは最大20桁までである int count = 1; // 固定したrに対して条件を満たすlの個数 int index = 0; // 現在の条件を満たす区間を最長とするlのインデックス REP(i,n){ int flag = 1; // 条件をみたす? REP(j,20){ s[j] += a[i][j]; if(s[j] > 1) flag = 0; } if(flag == 1) { ans += count; count++; } else{ int Flag = 0; //条件をみたすようになるまでlを進める while(Flag == 0){ Flag = 1; REP(j,20){ s[j] -= a[index][j]; if(s[j] > 1) Flag = 0; } index++; count--; } ans += count; count++; } } cout << ans << endl; return 0; }
kuru2par, set0gut1👍を押しています

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

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

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

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

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

guest

回答1

0

ベストアンサー

ansをlongにしたら通りました。
ansの最大値ってN=2*10**5の時のN*(N+1)/2なのでだいたい10**10になり、
intだとギリギリ一桁あふれるんですね。

投稿2018/05/29 19:11

set0gut1

総合スコア2413

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問