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

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

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

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

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

Q&A

解決済

2回答

1666閲覧

AtcoderのB問題でわからないものがあります

nomi

総合スコア32

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

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

0グッド

1クリップ

投稿2017/09/23 17:36

質問内容

先日行われたCODE FESTIVAL 2017 qual AのB問題についての質問です。
この問題は、何かしらの法則性を見つけて解く問題でした。Atcoder公式の回答を見る限り、答えを導くには以下のような式を導き出す必要があるようです。

k(M − l) + (N − k)l

しかし、なぜこのような式になるのかがよくわかりません。どのような考え方をすればこのような式を導くことができるのでしょうか?思考のステップを飛躍させることなく、詳しく教えて頂けると幸いです。

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

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

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

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

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

guest

回答2

0

ベストアンサー

行についてk個のボタンを押す、列についてl個のボタンを押すことを考えます。

行のボタンを押すと一行がすべて反転します。一行は列の数と同じだけのマスがありますので、反転するマスの数はM個です。では、k個の行ボタンを押した場合は、単純にk * M個のマスが反転して、黒になります。

しかし、実際は列のボタンも押されています。先ほどのk * M個のマスのうち、列ボタンも押されているマスがいくつあるのかを考える必要があります。なぜなら、これらのマスは行と列の両ボタンが押されているため、二回反転して白になっているからです。つまり、列ボタンも押されているマスの分だけ、減らさなくてはなりません。

その数の考え方は一緒です。一行に列ボタンも押されているマスの数は、そのまま列ボタンを押した数のl個です。よって、これもk個の行ボタンがおされれば、k * lとなります。あとはこれを引くだけです。ということで、行ボタンが押されたことによって生じる黒マスの数はk * M - k * lつまりk * (M - l)となりました。

次に列についてですが、全く同じ考え方ができます。行ボタンを考慮しない場合の黒マスはl * N個、行ボタンも押されているマスはl * kとなり、あとは引き算をするだけ、l * N - l * kつまり(N - k) * lです。

最後に行と列それぞれで求めた黒マスの足し合わせます。

k * (M - l) + (N - k) * l

これがk個の行ボタンとl個の列ボタンを押したときの黒マスの数になります。あとは、求めているK(入力で与えられる方です)個になるようなklの組合せがあるかを探すだけになります。

投稿2017/09/23 22:45

raccy

総合スコア21733

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

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

nomi

2017/09/24 07:36

 論理的に飛躍した部分がなく、非常にわかりやすいです!ありがとうございます!!  しかし、次にこのような法則性を見つけ出す問題に遭遇したときに、その問題を解ける気がしません。そこで、3つ質問があります。 1,どうすればこのような法則性を見つけ出す問題が解けるようになるのか教えて頂きたいです。 2,私に足りない力が何なのかが分れば教えて頂きたいです。私に足りないのは数学力でしょうか?練習量でしょうか?それとも他の部分でしょうか? 3,この問題は有名な問題だったりするのでしょうか?3分くらいでこの問題を解く人がいたので、この問題に似た有名な問題があるのかと疑問に思いました。 長々とした質問ですが、答えて頂けると幸いです。
raccy

2017/09/24 09:07

競技プログラミングを解く力というのは、数学を解く力に近い物があると思います。数学力そのものが必要という意味ではなく(といっても全くなかったらそれはそれで駄目ですが)、解けるようになる過程が似たような構成と言うことです。さてその力に必要なものは三つあると思います。 一つ目に、基礎知識。今回の問題はあまり必要とされないですが、エラトステネスの篩や動的計画法などのいわゆるアルゴリズムと言われるものが必要になるときがあります。そういった場合、知らなければ解くことが非常に困難になります。ここら辺は書籍なども出ていますので、そういった所から知識を得れば大丈夫かと思います。なお、数学の知識もある程度は必要です。アルゴリズムは数学と密接に関係するので、一緒に学べば問題ないと思います。 二つ目に、慣れと経験があります。何度も問題を解いていくと似たようなパターンに遭遇することがあります。前にやった問題と似ている、あのときはこんな方法だった、見たいのが見えてくれば、八割方は解けるようになるでしょう。ただ、そういう慣れと経験も単にドリルのように問題をこなせば良いというわけではありません。まずは、自分でどうすれば良いかを考えることです。これがものの数分で諦めて答えを見ても身に付きません。私の場合、考え込むときは数時間、時には一週間ずっと考え続けたときだってあります(といっても休日や寝る前にちょっとなどの合間合間ですが)。 三つ目に、勘とセンス、つまり、いわば才能です。数学でも、大学入試の二次試験や数学オリンピックの問題になると、すらすらと解ける人は極わずかです。練習だけでなんとかなる世界ではありません。それと同じで、競技プログラミングの上位問題をすらすらと解けるというの才能の世界です。いわゆる天才と言われる人達でなければ、トップと言われる領域に辿り着くことは難しいでしょう。 実際の仕事でぶつかる問題のほとんどは二つ目までで十分です。三つ目が必要になるのは誰もまだしたことが無いような最先端の分野やシビアな処理速度や最適化が求められる分野の話です。そういったことはほんの一部であり、選ばれし天才達が担っています。ほとんどの仕事はそこまでの能力は必要とされないので、私達のような凡才達が担って、世の中は動いています。
nomi

2017/09/24 09:45

今回の問題について、私は解き方を聞く前にもう少し考えるべきだったのかもしれませんね。
nomi

2017/09/24 10:04

最後までお付き合い頂きありがとうございました!!
guest

0

この問題のポイントは、白黒の個数はボタンを押す順番や行同士、列同士の中での場所には影響されないことです。
また同じボタンを2回押すことは、そのボタンを押さないのと同じとみなせます。
白黒反転で考えるとわかりにくいですが、N×Mのマス目を持つ障子のような格子を考え、行または列のボタンを押すことを、その行または列に色つきの光を通すシートを張る、または張ったシートを取り除くと考えれば、薄い色のマスを黒、2重になって濃い色になったマスを白とみなして考えられます。
そう考えれば、押す行または列を左上に寄せて考えることができます。入力例3では

1 列目、3 列目、2 行目、5 列目の順にボタンを押せばよい

としていますが、1~3列目、1行目を押すとすると以下のようになります。

□□□■■ ■■■□□ ■■■□□

これは、列を3つ、行を1つ押したと考えれば、左下に「押した3列×押さない2行」、右上に「押さない2列×押した1行」の分だけ■ができていると考えることができます。この合計が目的の値になるかを調べればいいので、k行l列押した場合の■の数

k(M − l) + (N − k)l

をfor文などで調べればいいことになります。

投稿2017/09/23 22:58

swordone

総合スコア20649

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

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

nomi

2017/09/24 10:03

参考になりました!回答頂きありがとうございました!!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問