Atcoder ProblemsのTrainingのEasyにあるC問題埋めの続きです。
Easyでも最後の3問ぐらいはどうやっても解法が思い浮かばなかったりしたので、実力の無さを噛み締めていました。
目次
1.ABC139
問題:C-Lower
N個のマスが並んでいて、隣のマスの高さが今のマスの高さ以下なら移動できるので、可能な移動回数を出力せよという問題。
右だけに進むので、高さを配列に入れて右にずっと見ていけば答えが出ます。
書いたコードは以下の通り。
2.ABC140
少し苦労した問題です。一個一個整理しながら考える必要があります。
謎の整数列Aがあり、そこに既知の整数列Bが与えられます。整数列Bのそれぞれの要素は、同じ番目の整数列Aの要素と次の要素の最大値より大きくなるという条件があります。このとき、整数列Aの総和を求めよという問題。
整数列Aの総和を最大にするので、それぞれの要素はわからなくても大丈夫ですが、入れながらやったほうがデバッグするときとかわかりやすい気がします。
書いたコードは以下の通り。無理やり実装した。
3.ABC158
制約条件が高々100までなので、ループ内で値を一つずつ増やしていって、一致するかしないかだけ見ていれば大丈夫です。小数点以下切り捨てだけ注意。
書いたコードは以下の通り。
4.ABC148D
レンガを壊して、残ったレンガに書かれている数字を1,2,3,…とするとき、壊すレンガの最小個数を答えよという問題。
左から1,2,3,…と書かれたレンガが残ればいいので、左から1のレンガが出るまで壊す、1のレンガが出たら2のレンガが出るまで壊す、というのを繰り返せば答えが出ます。
書いたコードは以下の通り。
5.ABC155
問題:C-Poll
出てくる文字列をそれぞれカウントするという問題。私は無理やりpairを作ってやってましたが、解説ではmapを使って実装していたので、なるほどなあとなりました。
今回の問題では出力されるのは、書かれた回数が最も多い文字列を全て、"辞書順"で小さい順に出力するというものです。
なので、mapに入れれば勝手にsortされるので、出力するときに便利です。また、文字列をkeyとすることで、めんどくさいことをしなくても、そのkeyのvalueにアクセスできます。
mapを使わずに実装すると次のようになります。mapを使った場合は解説を見て下さい。
6.三井住友信託銀行プログラミングコンテスト2019
問題:C-100 to 105
1個100円、101円、102円、103円、104円、105円の品物がぞれぞれ(実装する上では気にしなくていいぐらい)大量に売られています。それらを組み合わせて合計金額がX円になるような買い方ができるかどうか判定せよという問題です。
どれか1個だけ買う場合、2個買う場合、3個買う場合・・・と考えてあげると、次の表のようになります。
| 買う個数 | 範囲 |
|---|---|
| 1 | 100~105 |
| 2 | 200~210 |
| 3 | 300~315 |
ここからわかることは、合計金額を100で割った商をNとすれば、可能な合計金額の範囲は100N~105Nになります。
書いたコードは以下の通り。
7.ABC095
Aピザ、Bピザ、ABピザ(Aピザ半分、Bピザ半分)の3種類のピザがあり、AピザをX枚、BピザをY枚用意する必要がある。ABピザ2枚でAピザ1枚、Bピザ1枚に組み替えることはできる。このとき、最小でいくら必要かという問題。
私は、ABピザを買う枚数を2枚ずつ増やしていって、その中で一番値段の安かった場合を出力するようにしました。
書いたコードは以下の通り。
8.ABC151
コンテストの問題ごとにACした数と、ペナルティ数(ACするまでに提出した数)を出力せよという問題。
提出する問題は順番通りではないので、前から順番に取っていくのはダメ。ただ、問題番号が数字なので、vectorや配列で取っていれば大した問題ではない。
各問題にACしたか？という情報と、ACするまでに何回提出したかという情報を持つpairを作成して、ACしたら提出回数をカウントストップさせれば良さそうです。
書いたコードは以下の通り。
9.おわりに
pairの扱いは慣れてきました。しかし連想配列を使うのは全然経験値が足りてない。もっと練習します。