机の横に積まれている計算用紙をまとめています。Medium100が終わる気がしません。辛い。キーエンス主催のコンテストの問題見たらさっぱり解法思いつかなくて、私のIQ低くない？ってなってました。
目次
1.ABC117C
キーワード:ゲーム、コマ移動、一次元、最小回数
訪れたい座標にコマを置くと良さそうなのはなんとなくわかりますが、その他にどのように置けばいいか思いつかなかったので詰みました。
解説に全て書かれています。座標と一つ右隣の座標の差が大きい場所を、コマをうまいこと配置することで通らなくてもいいようにします。そのため、この差の和を最大化して、全体の範囲からその和を引けば操作回数を最小化できるようです。
2.ABC056C
問題:C – Go Home
キーワード:一次元、移動、最小値
移動方法がちょっと変わっていて、時刻によって移動距離が変わります。また、移動しないという選択肢もあるので混乱していました。
解説にかかれていますが、O(1)の方法があります。O(1)の解法はO(√X)の解法の考察をちょっと進めると出てきます。
この問題で重要なのは、時刻tまでの和がXを超えるならば、集合{1,2,…,t}の部分集合の和でXを表せることです。つまり、tを一つずつ試していき、集合の和がXを超えるかどうか判定すれば良いらしいです。
O(1)の解法は、集合{1,2,…,t}の和がXと等しくなるという２次方程式を立てると、その解としてtがXを含む数式として表されます。これを用いるとすぐに求まるらしいです。
3.ABC066C
問題:C – pushpush
キーワード:数列、操作、数列を求める
数列をもう一つの数列にある操作を繰り返しながら追加していく問題です。ある操作とは、もとの数列の要素を一つ答える数列の末尾に追加したあとに、答える数列を反転させます。
C++で愚直に実装するならば、答える数列にもとの数列の要素をpush_back()して、reverse()になりますが、毎回reverse()するとめちゃくちゃ計算量が大きくなってTLEします。私は最初提出した解法はこれで、無事にTLEしました。
毎回reverse()すると間に合わないのが明らかになったので、reverse()を用いずに実装する必要があることがわかりました。
ここで、手計算で最初から5番目ぐらいまで操作してみて配列の並びを書き出してみました。すると、偶数番目ならば数列の真ん中から左側にa6,a4,a2と偶数番目の要素が並び、右側にa1,a3,a5と奇数番目の要素が並びます。奇数番目ならば偶数番目と逆になります。
私はここで実装を始めたのですが、解説では更に考察を進めて、iとnの偶奇が一致するかどうかで場合が分かれるまで考えていました。
また、dequeを使えば数列の先頭や末尾にO(1)で要素を追加できるようです。dequeについてはMedium100を進めていたら再び出てきたので、そのときにまとめます。
ぶっちゃけ実装で一番めんどくさかったのは、数列を作ったときに表示させる部分です。数列を作らずに前から順番に出力させるような実装をしたら、すごく頭の悪いコードになりました。
4.ABC130C
キーワード:図形、分割
長方形を２つに分けたときに、小さい方の面積の最大値を求めよという問題です。
私が最初に考えたのは、x座標を通る縦線で切って2パターン、y座標を通る横線で切って2パターンのそれぞれの最小値を出し、２つの最小値の最大値を求めればいいかということです。同じ面積が出るかどうかは、最小値の最大値を求めるときに面積が同じになっているかどうかで判定していました。
しかし、これだとWAになります。
解説を読むと、最初の段落が全てを語ってくれています。つまり、全ての長方形の内側(境界を含む)の点を通る直線では、必ず面積を2等分できる引き方が存在します。また、分割法が複数ある場合とは、座標がど真ん中にあることです。
問題を読んだときに、面積の"小さい方"の"最大値"なので、面積の半分という発想をできなかったのは脳みそが足りなかったなあと反省しています。
setwするのがめんどくさかったのでprintfでフォーマット指定子を使っています。こっちのほうが覚えやすいし楽なんですよね。ただ、coutとprintfは異なるものなので、気をつけないといけないらしい。
5.ARC081C
キーワード:配列、最大値、面積最大化
棒から4本選んでできる長方形の面積を最大化する問題です。簡単そうに見えたのですが、実装してみるとカオスになりました。
配列をsortして降順に並べ、前から2本以上同じ長さの棒がないか探索するというのがメインです。しかし、同じ長さがない、2本または3本、4本以上の場合をそれぞれ考えて上げる必要があります。
これを書いているときに自分のコードを見たら、「なんで最初に各数字の個数を数えなかったんだろう？」と思っています。最近配列内の各要素の個数のカウントはハッシュテーブルやvectorなどでやると実装が簡単だということを知りました。たまにsortして前から順に見ていく必要がある場合もありますが。
うーん、カオス！！というかコードを読んで何をやりたいかわかりにくい。
6.ABC133C
問題:C – Remainder Minimization 2019
キーワード:mod、最小値、周期
気がつくべきは、最大2019×2019回以内の計算で答えが出せることです。これは(i×j)mod2019のmod2019によるものです。
単純に考えてLとRがかなり離れているならば、(i×j)mod2019=0となる(i,j)は存在します。この時、iかjは2019の倍数になっています。そして2019の倍数が現れるのはそこから2019進んだところです。よって、周期2019で2019の倍数が現れます。つまり、iとjをそれぞれ1周期の中で答えが最小化になるかを考えれば良さそうです。
実装は2重ループで書いて、外側のループはLからRを探索するように書きますが、LとRの差が1周期より長い場合は勝手にループから抜けるので問題ないです。逆に実装してて悩んだのは、二重ループの抜け方でした。これは答えが0になってたら二重ループから抜けていいので、どっちのループにも答えが0ならbreakするって書いてなんとかしました。
私は最初、(i×j)mod2019=i mod 2019 × j mod 2019で計算してWAしました。
7.ABC131D
キーワード:second要素でsort
pairで締切とかかる時間を持って、締切でsortするとうまくいきました。ただし、与えられる順番が、{かかる時間,締切}なので、そのままpairにするとsecond要素でsortすることになります。second要素でのsortは比較関数を用意するとできるようですが、今回は単純にpairのfirst要素とsecond要素を入れ替えた形のpairを作ることで、単純にsort()だけを使ってsortできるようにしました。
それだけできれば、経過時間は順に加算し、締切時間はその都度更新して、経過時間が締切時間を過ぎていないかどうかを判定し続ければ大丈夫でした。
8.おわりに
このあたりまで解いて思ったのは、愚直法ではACできない問題ばっかりということです。なので、このあたりから制約条件を見て、どうやるのがいいのか考えるようになりました。制約条件がn<=10^5だったら単純に二重ループにできないなとか、その程度ですけども。