Atcoder ProblemsのBoot camp for beginnersのEASYにあるC問題が全部解き終わり、Mediumに移行しようと思いましたが、Easyが全部終わってないのも気持ち悪いなと思ったので、先にEasyを終わらそうと思いました。
Atcoder ProblemsのBoot Camp for BegginersのEASY、全部解いた。次からMediumのC問題中心に解いていきます。 pic.twitter.com/PZZA5B9CpS
— やーご (@ateruimashin) May 28, 2020
疲れて"Beginner"を"Begginer"と書いてました。英弱かよ。
1.CODE FESTIVAL 2016 qual B B問題
予選にN人が参加し、それぞれ国内または海外またはそれ以外の学生です。
国内の学生は、上位A+B人なら予選通過、海外の学生は上位A+B人以内かつ海外の学生の中で上位B人以内なら予選通過するので、それぞれの学生について予選を通過できたか出力せよという問題です。
国内と海外以外の学生ってなんだよと思いましたが、それ以外となっている人については何も考えずに"No"を出力すればいいです。(それ以外とは学生でない人を指すらしいです。)
次に、参加者全員はまず上位A+B人に入らないといけないので、これを予選通過枠と呼べば、一人予選通過するたびに予選通過枠が1つ減ります。
国内参加者は予選通過枠に入ればいいので、予選通過枠が1つ以上あるならばYesを出力ます。
海外参加者は予選通過枠に加えて、海外参加者上位B人に入らないといけません。まず予選通過したら予選通過枠を一つ減らし、次に海外参加者の通過者のカウントを一つ増やします。このカウントがB未満なら"Yes"を出力します。
書いたコードは以下の通り。
2.三井住友信託銀行プログラミングコンテスト2019 B問題
問題:B-Tax Rate
税抜価格X円の税込み価格がN円になるとき、Nを出力せよ、ない場合は":("と出力せよという問題。
類題としてはABC158 C-Tax Increaseがあります。どちらもループ回して一致するかどうか探すコードを書けば通ります。
書いたコードは以下の通り。
全探索は結構無駄があるので、解説の解法2では税抜価格を"N/1.08の小数点切り上げ"として、税込価格がN円になるか確認するだけでOKらしいです。
3.パナソニックプログラミングコンテスト2020 B問題
問題:B-Bishop
角行の動き方をする駒と縦Hマス、横Wマスの盤面があり、その盤面上を角行が0回以上動きを繰り返して好きに移動するとき、到達できるマス目は何個あるかという問題。
あるパターンを見落とすとWAしか出なくなる問題です。私は解説読んで「あっ」ってなりました。
HとWが1以外のとき、到達できるマス目は(H*W+1)/2となります。最初はHとWの積が偶数か奇数で分けて考えていましたが、
- 偶数の場合→w*h/2
- 奇数の場合→w*h/2+(w+1)/2=(w*h+1)/2
となっていますが、小数点以下は切り捨てになっているので、どちらも奇数の場合の式で書けます。
見落としたパターンは「H=1」または「W=1」の時です。このときは駒は動けないので、"1"となります。
書いたコードは以下の通り。
こういう盤面上を動かすときは縦か横が1マスしかない時を考えないといけません、という教訓を得られた問題でした。
4.AGC014 A問題
3人はそれぞれクッキーを持っていて、3人同時に自分の持っているクッキーの枚数を半分にして残りの二人に渡すという操作を、誰かの所持枚数が奇数になるまで繰り返す。操作回数を出力せよという問題。
3人のクッキーの枚数は漸化式として書けるので、数学的に解けるのかなと思ってましたが、うまいことできなかったのでシミュレーションすることにしました。
シミュレーションするときはループを回す必要があるのですが、無限に繰り返すことができるパターンもあるので、それを省く必要があります。
無限にループするパターンは、全員のクッキー枚数が同じ(かつ枚数が偶数)の時のみです。
そういうわけで、全員が同じ枚数を持っている場合は0、ただし枚数が奇数の場合は-1を出力、その他の場合はシミュレーションをします。
シミュレーションは問題の操作の通りにするだけです。最大何回ループが回るか想定できなかったので無限ループにしています。
また、実装中にやったミスとして、変数a,b,c(クッキーの枚数を格納)をそのまま計算に通して、計算に使うべきaの値を更新してしまい、その後のbとcの値が想定と異なってしまいました。それを防ぐためにa,b,cを一回コピーするようにしました。
書いたコードは以下の通り。
5.ABC027 A問題
N人の子供がいて、X人のキャンディーを持っている。子供はそれぞれある数のキャンディーをピッタリもらうと満足する。満足する子供の数を最大化させたときの人数を出力せよ、という問題です。
最初、ぴったりもらうとという条件を見落としてて、ただ単に昇順にソートしてx以上あるならOKみたいなものをかいていました。
ただ、どっちにしろ、昇順にソートするのには代わりはありません。
前からぴったりになるように配って、配る度にxを減らすという操作を、xがある子どもの要求量を下回るまで来る返すせばOKです。
ただし、最後の子供に配るのを忘れないようにします。
書いたコードは以下の通り。
6.日立製作所社会システム事業部プログラミングコンテスト2020 B問題
A種類の冷蔵庫とB種類の電子レンジがあり、それぞれの値段がついています。また、M枚の割引券があり、ある冷蔵庫とある電子レンジを一緒に買うとc円割引されます。冷蔵庫と電子レンジを1台ずつ買った時、合計金額の最小値を出力せよ、という問題です。
制約条件がA,Bはどちらも最高10\^5なので、全通りを考えると10\^10通りと制限時間に終わらなくなります。
そのため、まずは割引券を使わない場合は、冷蔵庫の中の最低価格と電子レンジの最低価格を出しておきます。この総和が割引券を使わないときの合計価格の最小値になります。
そのあと、割引券を使ったときの価格を考えます。こちらはループを回して求めていきます。あとは、合計金額の最小値を更新し続けていけば答えが出ます。
書いたコードは以下の通り。
7.ABC141 C問題
早押しクイズ大会を開催している。参加者がN人いて、誰かが正解するとその他の参加者全員-1ポイントされる。ラウンド終了時、ポイントが0以下の参加者は敗退、0より大きいなら勝ち抜ける。参加者それぞれが勝ち抜けたか敗退したか出力せよ、という問題。
ABCの問題が残っていました。
ポイントは減る以外に変動しないので、とりあえず全員の参加者のポイントを初期ポイント-問題数で初期化します。その後、正解者のポイントを+1し続け、最後に0よりポイントが多いならば"Yes"、そうでないなら"No"を出力すれば良さそうです。
書いたコードは以下の通り。
これを書く前、ちょっと変な実装をしてREを出しました。
8.AGC037 A問題
文字列Sが与えられ、これをK個の文字列に分割する。この時、それぞれの文字列は、次の文字列と異なっていなければならない。この分割数Kの最大値を出力せよ、という問題。
私は自力で解けませんでした。解説見ると動的計画法とかあったので、DPを実装したことなかったので狼狽しました。というか、漸化式の作り方がわからない。そういうことで、他の人はどうやって実装してるのかと思って他の人の提出を見てみました。
すると、多くの人がシンプルに実装してて、コードを眺めながら「なるほどな～～～～」って思ってました。
分割した文字列ですが、次の文字列と異なっていればいいため、サイズは最大でも2になります。解説動画だと4より小さくなることがわかっていればいいといってました。まあ、この情報は実装には使わないんですが・・・。
やることは単純で、切り出した文字が前の文字列と等しいなら、更に次の文字を持ってきて前の文字列と比べるというのを繰り返すだけです。
書いたコードは以下の通り。
練習で範囲for文を使いました。
9.AGC012 A問題
参加者が3N人いて、それぞれの参加者に強さが設定されている。そして3人1チームをN組作ることにした。そのチームの強さは、チームメンバーの内2番目に強い人の強さで表される。N組のチームの強さの総和の最大値を出力せよ、という問題。
そんなに難しい問題ではありませんでした。
全てのチームの強さの総和を最大化したいので、それぞれのチームの強さもできる限り大きくしたいです。そうすると一番チームの強さを最大化できるのは、参加者の中で一番強さが大きい人、その次に大きい人、一番小さい人でチームを作ったときです。
要するに、強さが大きい人二人と強さが小さい人一人でチームを構成すると、全てのチームの強さの総和が最大化できます。
参加者の強さは昇順にソート済みとして、強さが小さい人は一人目~N-1人目から選びます。強さが強い人二人は、大きい人とその次に大きい人を選びます。すると、強さの総和の最大というのは、N人目、N+2人目、N+4人目・・・の強さを足し合わせたものと一致します。
書いたコードは以下の通り。
10.AGC041
2N人の選手がN台の卓で練習を行う。選手は合計Nペアに分かれ、どちらかが勝利し、どちらかが敗北します。勝利した場合は次にX-1卓で練習を行い、敗北した場合は、X+1卓で練習を行う。ただし、1卓で勝利した場合はそのまま、N卓で敗北した場合もそのままである。ある二人の選手が最初A卓、B卓でそれぞれ練習を行っている時、最小で何ラウンド行えばこの二人は同卓になるか、という問題。
めんどくさそうですが、紙に書いてみればなんとなく整理できます。
N台の卓球台を左から1卓、2卓、・・・と名前をつけます。
まず二人の差が偶数ならば、A卓から右へ、B卓から左へ同じ回数移動すればちょうど真ん中の卓で同卓できるので、|a-b|/2が答えになります。
次に二人の差が奇数になる場合を考えます。私はここでハマって一回WAを出しました。
差が奇数の時、二人が偶数の場合と同じように動いても真ん中で同卓することはできません。そのため、卓移動しない端を次のように利用します。
- 1卓かN卓に近いほうが端まで移動する。この時もう片方も同じだけ同じ方向に移動する。
- 端に到達した方は、1ラウンドだけ卓移動しないように勝敗を決める。
- 1ラウンド終了後、端にいる選手はもう片方の選手の方へ移動し始める。
こうすることで、最小ラウンドで二人が出会うことができます。端で1ラウンド使うことで、二人の差を偶数にすることができ、二人の差が偶数の場合の計算式を利用することができます。
書いたコードは以下の通り。
14行目で端に近いほうが端まで移動するために必要なラウンド数を出しています。その後は、どちらが移動したかを判別して、それぞれの位置を更新、最後に差の絶対値の半分を答えに加えるという実装をしました。
11.DISCO presents ディスカバリーチャンネルコードコンテスト2020予選
1本の鉄の棒がN-1個の切れ目によってN個の区間に分かれている。その切れ目で棒を切る予定であるが、どの切れ目を選んでも半分にできない恐れがある。そのため、切る前に、ある区間1つを1mm伸ばす、またはある区間を1mm縮める操作をすることにした。どちらの操作も1円のコストがかかる。棒を半分にするために必要な最小の金額を求めよ、という問題。
これも私は自力で解けませんでした。解説を見て「そういうふうに帰着できるか」と納得した問題です。
やることは一つで、ある切れ目を選び、それより右側と左側の長さを差の最小値を出力するだけです。
ただし、毎回和を求めているとTLEするようなので、累積和を用いて、それぞれの長さを出します。
切れ目より右側は累積和、左側は全体の長さから累積和を引いた長さになります。あとは、その差を出して、最小値を更新するだけです。
書いたコードは以下の通り。
私はずっと真ん中の位置を近い切れ目に合わせるような数式を考えていました・・・。これを考えると長さを変えた時真ん中の位置も変わるので、考えることが増えてしまうんですよね。途中で考え方を変えるべきだった。
12.CODE FESTIVAL 2017 qual C B問題
2つの整数列があり、この2つが"似ている"とは、それぞれの差の絶対値が1以下ということを表す。ある整数列が与えられた時、それと似ている整数列であり、全ての項の積が偶数となるのはいくつあるか、という問題。
これも自力で解けませんでした。解説読んだら、めちゃくちゃ単純なことで、こんなものも解けなかったのかと思いました。
まず、似ている数列の各項は、与えられた数列の各項の±1か同じなので、3パターンあります。それがN項あるので、似ている数列の全パータンは3\^Nパターンあります。
ここから積が奇数になるパターンを引けば求める答えが出てきます。
積が奇数になるパターンは、整数列の全ての項が奇数である場合です。よって、奇数の項はそのまま、偶数の項は±1して奇数にすると、全て奇数の整数列ができます。
したがって、積が奇数になるパターンは、与えられた整数列の偶数の数をMとすれば、2^Mパターンになります。
あとは実装するだけです。書いたコードは以下の通り。
13.AGC004 A問題
各辺1のブロックがA×B×Cの直方体状に並んでいる。この各ブロックを二色で塗る。この時、どちらの色で塗られたブロックも1つ以上ある、どちらの色で塗られたブロックも1つの直方体状になっている、という条件の下で塗る。二色のブロックの個数の差の最小値を答えよ、という問題です。
めっちゃ簡単。そう思って提出したら、過去の自分がWA出していました。
まずは、各辺のいずれかが偶数の長さをもつ場合。これは直方体をきれいに半分にできるので、差は0になります。
次に、各辺の全てが奇数の長さを保つ場合。このとき、差を最小化したいので、一番長い辺を2つに分けます。そうすると、1ブロック列が塗り分けたときの差になります。そのブロック列に含まれるブロック数は、その他の辺の掛け算で算出できるので、その値を出力すれば良さそうです。
ここで問題になったのは、2番目に大きい長さを出さないといけないということです。ちょっと調べましたが、どうせ3要素しかないし、配列に入れてsortしても変わらんやろ！となったので、ソートして0番目と1番目の要素の掛け算ということにしました。
書いたコードは以下の通り。
14.CODE FESTIVAL2016 qual A B問題
問題:B-仲良しうさぎ
N匹のうさぎがいる。各うさぎは自分以外のうさぎの内1匹が好きである。そして、両想いのうさぎは仲良しといえる。仲良しなペアの個数を求めよ、という問題。
最初、有向グラフかな？と思いましたが、そんなことしなくても実装できました。
"あるうさぎが好きな番目のうさぎ"の好きな番目が自分であればいいので、配列が使えれば十分です。
ただし、0番地から使う場合は、配列に入力するときに値を-1しておく必要があります。
また、１が2を好きで、2が1を好きな時、カウンタは2増えるので、最後に2で割る必要があります。
書いたコードは以下の通り。
15.おわりに
AGCのA問題がやけに解けなかった傾向にあります。解説や他の人の実装を見たら、もっと単純に考えるべきだなと感じることが多くありました。一回混乱するような方向に考えが進んだら、考えをリセットして単純化していくほうが良さそうです。
まあ、Template Matchingのように単純化しても複雑になる問題もありますが。(しかもTrainingだとHardに分類されているABCのB問題・・・)
なにはともあれ、Easyは全部解き終わったので、Mediumに進みます。ここから一筋縄では行かないような気がするので、頑張っていきたいです。
｡оО(｡´•ㅅ•｡)Оо。がんばっていこう・・・