引き続きAtcoder ProblemsのTrainingのEasyにあるC問題埋めです。残り数問でしたが、全然解法が思いつかなくて辛かったです。また、前にやった手法を忘れていたので、記憶力のポンコツさに磨きがかかってきました。
1.ARC088
X以上Y以下の整数からなる整数列の長さを出力する問題ですが、次の条件があります。
i+1番目の整数はi番目の整数の倍数となり、それより大きい。
問題だけ見たら難しそうですが、ただ単に、2番目は1番目の数の2倍、3番目は1番目の数の4倍・・・というふうにやるだけです。
つまり、i×X≦Yとなるiの数を数えるだけです。
書いたコードは以下の通り。
2.ABC120
N個のキューブがあり、各キューブは赤色か青色である。このとき、"異なる色"のキューブが接している場合、この2つのキューブを取り除ける。これを操作ができなくなるまで行う。その時取り除けるキューブの最大数を出力せよ、という問題です。
私は最初、同色のキューブ2つを取り除くものだと勘違いしてました。解説動画でも勘違いしている人がいたようです。解説役のchokudaiさんも勘違いしてましたし。
異色のキューブを取り除くのならば話は簡単です。両方の色のキューブが残っている場合、必ず異色のキューブが接する場所ができます。そのため、どちらかのキューブがなくなるまで操作が続くことになります。
結局、赤色のキューブと青色のキューブの少ない方のキューブの数の2倍のキューブが除外できることになります。
書いたコードは以下の通り。
同色の場合はスタック使うと実装できるらしい。
3.ABC145
町がN個あり、全ての町を通る移動をする。全ての移動のパターンの距離の平均値を出力せよという問題。
ある町からある町へ移動するときの距離を全て出しておきます。あとは、このパターンが何回出てくるかわかれば・・・というところで力尽きました。
一番愚直な方法は、全ての移動パターンを列挙してあげること。全列挙は難しそうでしたが、next_permutationを使えば全列挙できます。ABC150C問題で使ったものです。完全に忘れていました。当然、計算量は大きくなります。
解説に載ってた2つ目の方法は、特定の2つの町を1ペアとして考え、それが含まれる通りが何通りあるかというのを考えるものです。全てのペアで通りは同じなので、全てのペアの距離の総和の2(N-1)!倍が総距離になります。それをN!で割って平均値にするので、全てのペアの総和の2/N倍が答えになります。
これならば、計算量はある程度減らせます。
書いたコードは以下の通り。
フォーマット指定子はfixed使うより、printfで書いたほうが楽・・・。
4.ABC093
3つの整数が与えられ、それらには次の操作が可能です。
- 2つを選んで、その両方に1を加える
- 1つを選んで、その整数に2を加える
これらの操作を繰り返して3つの整数を等しくするときに必要な操作の最小回数を求めよという問題。
結構ぐちゃぐちゃになりましたが、自力で実装しました。解説とは違った考えたかをしています。
私が考えた中で一番のポイントは2つ以上同じ値を作ることです。
まず、それぞれの整数を引いて、2の倍数になるペアを見つけます。3つの整数があるので、偶数ー偶数か奇数ー奇数のペアが作れるのは自明です。また、差が2の倍数になるのを探すのは、”1つを選んで、その整数に2を加える"操作をするためです。
そして、操作回数にその差の半分を加えます。さらに、そのペアを大きい方にあわせます。
これで3つの整数の内、2つ同じ値ができました。
その後、同じ値の整数をp、ペアになってない整数をqとします。
p>qかつpとqの差が2の倍数ならば、操作回数に差の半分を加えます。そうでないならば、p+1とqの差の半分+1を操作回数に加えます。
これは、例えば"3,6,6"となったとき、2を加える操作では全ての整数を一致することができないません。そのため、6に1を足す操作をしてから3に2を加える操作をすることで"3,6,6"→"3,7,7"→"5,7,7"→"7,7,7"とできるので、pに1を加え、操作回数にも1を加えています。
p<qのときは、ペアに1を足す操作のみ行うので、その差を操作回数に加えます。ペアの整数それぞれに2を加えて、最後に1を加える(加えない場合もある)という操作をやっても、両方に1を加える操作をやっても操作回数は同じだからです。
最終的な操作回数を出力して終わりです。
書いたコードは以下の通り。
解説ではもっとシンプルに実装できるような感じに書いてあります。
5.おわりに
これでEasyのC問題は終わりです。次からMediumやっていきます。