AtCoder ProblemsのBoot camp for BeginnersのMidiumのC問題を解いていました。解法が全く思いつかない問題も何問かありました。また、途中でABC169で爆死したことで、Pythonでの実装もやってようとなっています。
目次
1.ABC139D問題
問題:D – ModSum
数列{1,2,…,N}を並び替えて、要素自身の番目を自身の値で割った時の余りの和を最大化せよという問題。難しく考えると堂々巡りに陥ります。
解法は単純で、数列P{1,2,…,N}の各要素を一つ左にシフトさせます。すると、数列Q{2,3,…N,1}となります。このようにすると、数列Qの各要素を番目で割れば、最初のN-1個の余りは数列PのN-1番目の要素までと一致し、N番目は余り0となります。結局、数列PのN-1番目までの要素を足し合わせればいいです。ただし、数Pは初項1、公差1の等差数列なので、等差数列の和の公式を使えば一瞬で出ます。
書いたコードは以下の通り。
2.ABC064C問題
レートごとに色が別れており、レート3200以上の人は色を自由に変えられるという設定のもとで、色の種類数の最小値と最大値を求めよという問題。
注意すべきは、""レート3200以上の人は自由に色を変えられる""というのは、”その他のレートの人に付く色以外でも良い"ということです。なので、レート3200以上の人の色を金色や白色にしても問題がないということです。これを忘れるとWAします。
あとは、レートごとに分類して、各レートに人がいるかどうかだけ判定、レート3200以上の人数をカウント。最小値はレート3200以上の人を、人が存在するレートの色に割り当てることで出せ、最大値は人が存在するレートの色の種類+レート3200以上の人数で出せます。
一応、全員がレート3200以上という場合も考えなくてはなりませんが、最小値1、最大値レート3200以上の人数となります。
また、実装で一番めんどくさいのは各レートごとの人数把握です。if文で頑張って書くとか、レートが400刻みなのでレートを400で割って、それで判別するとか色々あります。
書いたコードは以下の通り。
レートを400で割った値を使って配列に入れるのが一番楽だったかなと、他の人の解答を見て思いました。
3.ABC072C問題
問題:C – Together
長さNの整数列が与えられて、各要素に対してて+1する/なにもしない/-1するという操作のどれかを1回行います。その後、ある整数Xと同じ要素の個数を調べます。その個数を最大化せよという問題。
問題文を華麗に読み間違えて2WAしました。
やることは、各値が何回出現したかカウントして、3つ連続するカウントの和の最大値を求めればいいです。
書いたコードは以下の通り。
参考コード:提出#13694779
4.ABC086C問題
二次元平面上を旅する問題です。時刻0に(0,0)を出発して時刻tに(x,y)に到着し、その後(x,y)から出発し・・・という旅行プランが与えられます。また時刻tから時刻t+1の間に旅行者は上下左右1つ分のいずれかの格子点に移動することができます。ただし、その場にとどまることはできません。最終的に、旅行プランが実行可能かどうか判定せよという問題。
紙に書くとわかりやすいですが、隣に移動するために必要な時間は1だけでなく、1+2や1+4でも可能です。つまり、移動する場合に必要な時刻は(最小移動距離)+2N(Nは整数)になります。また、同じ場所に戻ってくる場合は、最短距離で必要な時間は4であり、移動する場合と同様に考えると、必要な時間は4+2N(Nは整数)となります。
あとは、経過時間と移動距離を出し、
- 移動距離>経過時間ならば、移動できないので不可能
- 移動距離=経過時間ならば、移動できるので可能
- 移動距離<経過時間ならば、経過時間から移動距離を引いた上で2の剰余を取って0になるなら可能、1なら不可能
と判定すれば良さそうです。
書いたコードは以下の通り。
5.ABC096C問題
H行W列のマス目を、上下左右に隣接する2つのマスを選び両方黒く塗るという方法を最低0回繰り返し、与えられた状態にできるかどうか判定する問題。
わかりにくいですが、入力例1を見るとわかりやすいです。要するに、自分とその上下左右のどれか1マスは最低塗ります。つまり、1マスだけ塗るということは不可能です。結局、黒マスが隣接しているならば必ずその形は作れますし、1マスだけの場所があるなら必ずその形は作れません。
ということで、実装すべきは1マスのみ黒くなっている部分がないかという判定だけです。
書いたコードは以下の通り。
6.ABC063C問題
問題:C- Bugged
試験を受け、最終成績が10の倍数の場合0と表示されるバグがあります。この時、成績として表示される最大の値を求めよという問題。
まず、全て正解したならば、成績は最大値となります。この成績が10の倍数でなければそのまま出力されます。
一方、成績が10の倍数である時は、なにかの問題が不正解となる必要がありますが、成績は最大化したいので、最大値から1つの問題の配点が引かれた値だけを考えれば良さそうです。
書いたコードは以下の通り。
7.ARC073C問題
問題:C – Sentou
スイッチを押すとT秒間お湯が出るシャワーがあります。そのスイッチをN人が、前の人がスイッチを押してからt秒後に押します。お湯が出る時間の総和を求めよ、と言う問題。
数直線書いて整理するとわかりやすいです。前の人が押してから次の人が押すまでの時間をtとすれば、
- t≧Tならば、お湯は出て次の人が押すまでに止まるので、総和にTを足せば良い
- t<Tならば、お湯が止まる前に次の人が押すので、総和にtを足せば良い。
これを繰り返していけば総和が求まります。
書いたコードは以下の通り。
Tが最大10^9なので一応long long型を使っています。int型でも大丈夫ですけども。
8.ABC088C問題
問題:C – Takahashi’s Information
3×3のグリッドに数が書かれている。また、整数a1,a2,a3,b1,b2,b3の値が決まっており、マス(i,j)にはai+bjが書かれているらしい。このグリッドは正しいか判定せよという問題。
私は連立方程式を立ててやってやろうとしましたた、うまく行かずに詰みました。そこで解説を読んで理解しました。
もし、(a1,a2,a3,b1,b2,b3)=(p1,p2,p3,q1,q2,q3)となる値が存在するならば、任意のxに関して(a1,a2,a3,b1,b2,b3)=(p1+x,p2+x,p3+x,q1-x,q2-x,q3-x)となる組み合わせが存在する。これは、ai+bj=(pi+x)+(qj-x)=pi+qiが成立し、ai+bjの値はどの(i,j)についても変化しないからです。
そこで、xは任意に設定可能なので、一番計算しやすいようにa1=0となるようにxを設定します。そうすると、b1,b2,b3が定まるので、その値から更にa2,a3が定まります。最後に、その値が正しいかどうか判定して、結果を出力します。
書いたコードは以下の通り。
こういう数学的な問題、慣れてない・・・。
9.ABC073C問題
同じ数があれば消し、なければ加えるという操作を繰り返して、最後に残る数字の個数を出力せよという問題。
ただカウントして、2の倍数でなければカウントを増やして、そのカウントを出力すれば良さそうです。
書いたコードは以下の通り。
10.ABC159D問題
ある整数が書いてあるボールがN個あり、k番目のボールを除いたN-1個のボールから整数が等しいような異なる2つのボールを選び出す方法の数を求めめよ、という問題。
私は全く思いつかなかったので解説と他の人の提出を読んで理解しました。
まず、書かれている整数ごとに個数をカウントします。その後、N個のボールから書かれている整数が等しくなるような異なる2つのボールを選び出す方法の数を出します。
その後、各整数から2つ選ぶ場合の数bと、k番目の整数の1つのボールを除いたところから2つ選ぶ場合の数cを出します。
最後に、全通りからbを引いてcを足すというのを繰り返せば良いです。
書いたコードは以下の通り。
11.ABC157C問題
N桁あり、左から数えてs桁目はcである、という条件を満たす整数の内最小のものを出力せよ、できない場合は-1を出力せよという問題。
無理矢理if文で頑張っていろいろな場合を書いて判定すればなんとかなります。というか私はテストケースとにらめっこして実装しました。
ただ、できたコードはすごくやばいことになったので、もっとちゃんとコードを考えましょう。ということで、他の人の提出を見ます。
読んでて頭いいなあと思ったコードがこちら。
N=1なら0~99まで、N=2なら10~99まで、N=3なら100~999までを一つずつ調べていく方法です。M≦5なのでこれでも間に合いますし、Mがもっと増えても実装で工夫すればあんまり問題になりません。
とりあえず、私が書いたコードは以下の通り。
一応通ります。落ちたテストケース見ながらif文がどんどん増えていきました・・・。
12.ARC086C問題
N個のボールがあり、それぞれ整数が書かれています。いくつかのボールの整数を書き換えて、N個のボールに書かれている整数がK種類以下になるようにする時、書き換えるボールの数の最小値を求めよ、という問題。
ソートして、各整数の個数を調べて、さらに個数を昇順にソートして、個数の配列を頭からk-1まで足し合わせてそれを出力すればいいです。
書いたコードは以下の通り。
2回ソートしてるのが余りキレイじゃないなと思いましたが、実装上楽だったので。
13.おわりに
全く歯が立たない問題が何個もありました。経験値を積んで頑張っていきたいです。