CodeIQの実力判定Aランク問題でタイムアウトしてしまう。
- 評価
- クリップ 0
- VIEW 1,692
退会済みユーザー
CodeIQの問題をやっていたのですがタイムアウトしてしまいます。
問題
問題は以下です。
【問題】
1から1,000,000までの整数の範囲で、連続する2値を合計します。
2値の合計が、整数Nの倍数になる組み合わせを、数えてください。
ただし、整数Nは、2≦N≦1,000 の範囲とします。
例
整数Nが11の場合、「5, 6（合計は11）」、「16,17（合計は33）」……という組み合わせが、整数Nの倍数になります。
また、連続する2値の最小は「1, 2（合計は3）」、最大は、「999999, 1000000（合計は1999999）」になります。
【入力】
標準入力から、複数行のデータが与えられます。1行のデータが、1つの整数Nになります。
【出力】
1行ずつ処理を行ない、その答えを1行ごと標準出力に出力します。【入出力サンプル】
Input
307
456
545
165
Output
3257
0
1835
6061
ログインが必要なため、以下より転載
https://codeiq.jp/challenge/3117
作成したコード
using System;
public class hoge
{
static void Main()
{
string line;
int num, count = 0, val = 0;
for(;(line=Console.ReadLine()) != null;)
{
if(int.TryParse(line, out num))
{
for(int i=1;i<1000000;i++)
{
val = i + (i+1);
val %= num;
if(val == 0)
count++;
}
Console.WriteLine(count);
}
}
}
}
for分で回すのがいけないのかなと思いましたが最適解がよくわかりません。
ヒントの様なものでも構いませんので何か教えてください。。。
追記
処理制限時間は1秒です。
-
気になる質問をクリップする
クリップした質問は、後からいつでもマイページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
クリップを取り消します
-
良い質問の評価を上げる
以下のような質問は評価を上げましょう
- 質問内容が明確
- 自分も答えを知りたい
- 質問者以外のユーザにも役立つ
評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。
質問の評価を上げたことを取り消します
-
評価を下げられる数の上限に達しました
評価を下げることができません
- 1日5回まで評価を下げられます
- 1日に1ユーザに対して2回まで評価を下げられます
質問の評価を下げる
teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。
- プログラミングに関係のない質問
- やってほしいことだけを記載した丸投げの質問
- 問題・課題が含まれていない質問
- 意図的に内容が抹消された質問
- 過去に投稿した質問と同じ内容の質問
- 広告と受け取られるような投稿
評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します
この機能は開放されていません
評価を下げる条件を満たしてません
質問の評価を下げる機能の利用条件
この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
-
メールアドレスの認証
メールアドレスの認証
-
質問評価に関するヘルプページの閲覧
質問評価に関するヘルプページの閲覧
checkベストアンサー
+1
連続する2つの値ですから、x + (x+1) が N の倍数ですよね。
つまり 2x+1 が N になる値を一つ見つけることができれば、あとは 1000000 までに何回加算できたか分かればよいのでは。
で、2x+1 が N になるということは、変形して 2x = N-1 ですから、x = (N-1)/2 ですよね。
でもって、次の N の倍数を構成する2値のうち小さい方をy とすると、すなわち 2y+1 = 2N ですから、 2y = 2N-1 = N + N-1 より、y = (N/2) + (N-1)/2 です。つまり、y = x + (N/2) になります。
なので、最初の x さえ分かれば、あとは N/2 を足していき、 x<1000000 になるまでの加算回数をカウントするだけでいいのでは。
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+1
CodeIQ運営事務局からのお願いと連絡事項
解答送信の有無を問わず、模範解答のネタばれにつながるような各種行為、別人による不正解答は、固くお断り申し上げます。
CodeIQ運営事務局 スキルチェック部さんからの問題より。
との注意があるので、ふんわりとした回答のみにとどめます。
- 連続する２値にはある縛りがあります。
- とりあえず最小の組み合わせを探します。
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
15分調べてもわからないことは、teratailで質問しよう！
- ただいまの回答率 88.12%
- 質問をまとめることで、思考を整理して素早く解決
- テンプレート機能で、簡単に質問をまとめられる
2017/03/03 17:05
数学とか最近まったくなので問題文通りにしかコードをかけていませんでした。。。
ちょっと試してみます。
2017/03/03 17:13
（切り捨て） も計算ですぐ分かりますから、(1000000-x)/(N/2) で、何回加算可能かも（実際にループさせなくても）分かりますね。
でもって条件から、最初の N が偶数の場合は 0 に固定されます（Nは奇数でないとそもそも該当する2値が存在しえません）、と。
2017/03/03 17:50