![B問題 解説
? まず文字列を標準入力で読み込む
? 空の文字列をあらかじめ用意しておく
– String ret = “”; など
? それぞれの文字に対し、子音のみを別の
文字列に付け加える
– If(子音かどうかの判定) ret += input[i];
? 最後に、作成した文字列を出力する
など](https://image.slidesharecdn.com/abc002-131027085806-phpapp01/85/AtCoder-Beginner-Contest-002-5-320.jpg)
AtCoder Beginner Contest 002 解説
- 1. AtCoder Beginner Contest 002 解説 AtCoder株式会社 代表取締役 高橋 直大
- 2. A問題 問題概要 ? ２つの数字が与えられる ? 大きい方を出力しなさい
- 3. A問題 解説 ? まず、２つの数字を読み込む。 – C言語ならscanf、javaならscannerを使うなど – 解らない場合は、「標準入力」について調べよう ? 次に、その２つを比較する – 比較方法はさまざま ? Ifと不等号を使う方法 ? Maxなどの予め組み込まれている関数を使って、大きい方を 取得する ? 大きい方を出力する – C言語ならprintf、javaならSystem.out.printlnなど – 解らない場合は「標準出力」について調べよう！ – 改行なしでの出力は不正解になるから気を付けよ う！
- 4. B問題 問題概要 ? 30文字以下の文字列が与えられる ? 母音だけを除いて出力しなさい
- 5. B問題 解説 ? まず文字列を標準入力で読み込む ? 空の文字列をあらかじめ用意しておく – String ret = “”; など ? それぞれの文字に対し、子音のみを別の 文字列に付け加える – If(子音かどうかの判定) ret += input[i]; ? 最後に、作成した文字列を出力する など
- 6. B問題 その他の解き方 ? 言語に組み込まれたreplace機能などを 使って、a,i,u,e,oだけ取り除いてしまう ? 判定後に別の文字列に格納するのではな く、１文字ずつ出力してしまい、最後に 改行を出力する
- 7. C問題 解説 ? 2次元平面上に存在する、3つの点のx座 標、y座標が与えられる ? それら3つの点で構成される三角形の面積 を求めなさい
- 8. C問題 解説 ? 符号付面積の公式を使おう！ – (0, 0), (a, b), (c, d)の3点があるとする – 面積S = |ad – bc|/2を利用する – 実際に与えられる点は(0, 0)に必ずあるわけで はないが、平行移動すれば良い。 ? (a, b), (c, d), (e, f)であれば、 ? (0, 0), (c-a, d-b), (e-a, f-b)に平行移動しても面積は変 わらない。
- 9. C問題 注意点 ? 答えが大きくなるのに注意しよう！ – phpなど一部の言語だと、出力方法によっては、 2e+6などの指数表示になってしまう。 ? 割り算に気を付けよう！ – 答えが小数となる場合、整数同士の割り算をする と、誤答になってしまう。 ? 7 / 2などだと3になってしまうのを気を付けましょう ? 符号付面積を使う場合、絶対値をつけよう！ – 付け忘れると、面積がマイナスになってしまうこ とがある
- 10. C問題 その他の回答 ? 四角で包んで、端の三角形を引いていく – バグりやすいのでお勧めしません。 ? 回転させ、（底辺）×（高さ）÷２で求め る – 問題ないですが、回転作業が面倒？ ? ヘロンの公式を使う – 辺の長さa, b, cの三角形の面積 – T = √(s(s-a)(s-b)(s-c)) – それを知ってるなら符号付面積も覚えましょ う
- 11. D問題 問題概要 ? N人に対して、M個の知人関係が与えられ る。 – iさんとjさんが知人である、というような情報 ? ここで、「全員が全員のことを知ってい る派閥」のうち、出来るだけ人数が多い ものを作りたい。 ? その人数の最大値を求めなさい。
- 12. D問題 解説 ? 「最大クリーク問題」と呼ばれる有名問 題 – 無向グラフにおいて、頂点の部分集合Cに対 し、Cに含まれるあらゆる2つの頂点を繋ぐ辺 が存在するようなCを、クリークと呼ぶ。 ? 今回はそのクリークのうち、最大のものを調べる – NP困難の問題であることが知られている ? ???が、こんな難しいことを知ってい る必要はありません！
- 13. D問題 解説 ? 全てのパターンを試す！ ? 例えば、A,B,Cの3人であれば、 – {A} {B} {C} {A,B} {B,C} {A,C} {A,B,C}の７通り ? 12人の場合も、一人一人に対して、派閥 に入れる?入れないが２通りあるので、 2^12で2048通り！ – 実際は、0人派閥はあり得ないので2047通り ? これくらいであれば、どの言語でもすべ てのパターンを試せます。
- 14. D言語 解説 ? パターンの調べ方１ – bitを利用した方法 ? 例えば、3人であれば、1から7までのループを回す ? 2進数にすると、001, 010, 011, 100, 101, 110, 111 ? 各数字に対し、どの桁が1になっているかを列挙す る – それぞれ{0} {1} {0 1} {2} {0 2} {1 2} {0 1 2} ? これを利用すると、全通り調べることが出来る
- 15. D問題 解説 ? パターンの調べ方2 – 再帰関数を使って調べる ? 深さ優先探索の要領で、人数分探索を行う
- 16. D問題 解説 ? 全パターン調べたら、派閥を作ることが 出来たパターンの中で、最も人数が多 かった派閥の人数を出力すれば良い。 – 1人派阀しか出来ない场合もあるので注意！
- 17. D問題 誤った解法 ? 適当な貪欲法を使ってはダメ。 ? 下のような方法は全て不正解となります – 上から順番に、派閥に加えられる人を派閥に 加える – 友人が多い人から派閥に入れていく – 派閥を作りづらそうな人を除外していく ? 確実に正しい答えを返す回答を作る癖を つけましょう！
- 18. D問題 実装が難しい場合 ? 他の人のソースコードを見てみよう！ – bitを使った提出例 ? climpetさんの回答 C++ – http://abc002.contest.atcoder.jp/submissions/110897 ? 葉月怜夢さんの回答 Ruby – http://abc002.contest.atcoder.jp/submissions/111299 – 深さ優先探索を使った提出例 ? おたっくすさんの回答 C++ – http://abc002.contest.atcoder.jp/submissions/110949