ABC198
こんばんは。2年前から使っていたDynabookのWindowsが突如起動しなくなり諸々のデータの救出やらなんやらで半月ほどAtCoderどころか競プロ関係が何もできていなかった島崎翔です。今日はABC198に参加したので記録をしておきます。
A - Div
$n$個のお菓子を横一列に並べて、どこかの隣り合う$2$個のお菓子の間に仕切りを置いてその仕切りより左は$A$君に、右は$B$君に、とでもすれば分けられます。植木算の考え方です。
B - Palindrome with leading zeros
例えば平仮名やアルファベットで$n$文字の文章が回文であるかどうかを判断するには、前から$i$文字目と後ろから$i$文字目が同じ文字であるかを$i=1$から$i=n$まで（とするとほとんどの部分を$2$回調べることになり実際は$i=int((n+1)/2)$までで十分）調べればよいです。
今回は後ろのほうの$0$を無視できるので「$1$文字目の数字から「$0$以外で最も後ろにある」ような数字までが回文であるか」を調べます。
私は最初$int$で受け取って演算で何とかしようとしましたが思うように書けなかったので結局$string$で受け取りました。文字列$s$の$i$文字目を$s[i]$と書いて$WA$。競プロから離れていたので細かいミスが多いですね。
C - Compass Walking
基本的に最短経路で向かって最後の$2$歩で調整（参照：入力例2）すればよいと考え天井関数を用いて実装するも$WA$。誤差に殺されたと考えて$sqrt$演算を消すも$WA$。一瞬オーバーフローを疑うも制約的にありえない。
遠い場合のみ考えていたが改めて考えてみると何のことはない。歩幅がめちゃくちゃ長くて目的地がめちゃくちゃ近かったら$1$歩で到着できないではないか。気付けば簡単、その部分の判定を追加して$AC$。
結果・感想
https://atcoder.jp/users/ShoShimazaki/history/share/abc198atcoder.jp
何故かジャッジがめちゃくちゃ重いし手元の環境は整えてなかったので割とイラついて適当なコードを投げまくったらかなりペナを食らいました。落ち着いてコーディングしたいですね。そしてやはりしばらくコードを書かないと細かいところ（$0-indexed$など）にミスが出ますね。出来るだけ毎日続けていきたいです。
D問題を早々に諦めて書き始めたのでコンテスト終了前に書き終わってしまいました。終わるまで公開しないように気を付けないといけませんね。今日はこれで終わります。
AHC001
こんばんは。島崎翔です。AHC001に参加したので記録をしておきます。括弧内の点数は暫定順位付け用の入力での点数です。
問題［A - AtCoder Ad］
「$10000×10000$のマス目の中に格子点を頂点とする$n$個の長方形を重ならないように配置する。その際（$1 \leq i \leq n$として）$i$番目の長方形が内部に点$(x_{i}+0.5,y_{i}+0.5)$を含んだうえで面積が$r_{i}$に近ければ近いほど点数が高い。」みたいな感じです。
解法1（$8e5$点程度）
とりあえず$k$番目の長方形を$(x_{k},y_{k}),(x_{k}+1,y_{k}),(x_{k},y_{k}+1),(x_{k}+1,y_{k}+1)$の$4$点を頂点とする面積$1$の正方形として出力しました。全ての$i \neq j$に対し$(x_{i},y_{i})\neq(x_{j},y_{j})$であることは保証されているので、この出力では$1$番目から$n$番目までの全ての長方形が重ならずに内部に点$(x_{i}+0.5,y_{i}+0.5)$を含むのである程度の点数が得られます。
この提出で暫定順位付け用の入力から得られる点数は$823090$点で、私が提出した時点では同点の方がそこそこな人数いらっしゃったので割と初めに試す解法なのかなと思いました。
解法2（$3e6$点程度）
前述の解法1の処理に加えて、$4$点$(x_{k},y_{k}),(x_{k}+2,y_{k}),(x_{k},y_{k}+2),(x_{k}+2,y_{k}+2)$が$10000×10000$の領域内に収まり他の長方形と重なりもしない場合には$k$番目の長方形を前述の$4$点を頂点とする面積$4$の正方形とする処理をしました。
ほとんどの長方形で面積が$4$倍になったので点数も解法1と比べてけっこう伸びました。
解法3（$7e6$点程度）
前述の解法2の処理に加えて、$4$点$(x_{k}-1,y_{k}-1),(x_{k}+2,y_{k}-1),(x_{k}-1,y_{k}+2),(x_{k}+2,y_{k}+2)$が$10000×10000$の領域内に収まり他の長方形と重なりもしない場合には$k$番目の長方形を前述の$4$点を頂点とする面積$9$の正方形とする処理をしました。
ほとんどの長方形で面積が更に$2$倍以上になったので点数も解法2よりも更に伸びました。正直な話ここまでは慣らしですね。
解法4（$4.18e10$点程度）
前述の解法をベースにしながら本格的に$k$番目の長方形の面積を$r_{k}$に近付けるようにしました
まず初期配置として$k$番目の長方形の$4$頂点は$(x_{k},y_{k}),(x_{k}+1,y_{k}),(x_{k},y_{k}+1),(x_{k}+1,y_{k}+1)$に設定します。次に$n$個の長方形のなかで$10000×10000$のマス目の外周に接していないものについて、乱数を発生させてランダムに$4$方向のうちから$1$方向を選んで長方形をその方向に伸ばす、という処理をしました。
解法5（最終提出・$4.52e10$点程度）
前述の解法をベースにしながら本格的に$k$番目の長方形の面積を$r_{k}$に近付けるようにしました
まず初期配置として$k$番目の長方形の$4$頂点は$(x_{k},y_{k}),(x_{k}+1,y_{k}),(x_{k},y_{k}+1),(x_{k}+1,y_{k}+1)$に設定します。次に$n$個の長方形のなかで$10000×10000$のマス目の外周に接していないものについて、乱数を発生させてランダムに$4$方向のうちから$1$方向を選んでその先に他の長方形が無ければその方向に伸ばす、という処理をしました。
結果・感想
初めてのヒューリスティックコンテストでしたが参加していてとても楽しかったです。しかし割と単純な方法を実装してある程度の点数を出した後、細かい工夫をしたものの点数が伸びなかったのが悔しいところではあります。また次回も参加してみたいです
長いコンテストは時間を決めて取り組まないと延々続けてしまいますね。今日はこれで終わります。
ARC114
こんばんは。島崎翔です。今日はARC114に参加したので記録をしておきます。
A - Not coprime
「$50$以下の素数って少なそうだし全探索か。$Y$は$1$種類の素因数は$1$つ持てばいいからbit全探索かしら。でもbit全探索は勉強しようと思って放置してるんだよな。まだ書けないや。どうしよう。」とういう思考の果てにbit全探索的なものを我流で書きました。for ( int i = 0 ; i < 65536 ; i++ ) { 処理 }を回してif ( ( i % int ( pow (2, 16-j ) ) ) / int ( pow ( 2, ( 15-j ) ) ) == 1 )でbit的な感じで拾っていきました。一時間近くかかりました。
結果・感想
atcoder.jp
Aの1完でパフォーマンスは905、レーティングは516→565でした。
1完でこのパフォが出るとは思いませんでした。
典型力を付けましょうね。今日はこれで終わります。
2021/3/14追記：B問題が茶Diffだったらしいので緑パフォだったのはBが割と早く解けたからですかね。
ABC195
こんばんは。島崎翔です。今日はABC195に参加したので記録をしておきます。
A - Health M Death
倍数判定ですね。余りが$0$なら$Yes$でそれ以外は$No$。
B - Many Oranges
全部が最も軽い（もしくはその付近）場合に最も多くなり、全部が最も重い（もしくはその付近）場合に最も少なくなりますね。
$UNSATISFIABLE$になる条件を$W<A$だけにして$WA$。Sampleでも落ちてたのでちゃんと確認しよう。
C - Comma
$N$の桁数で場合分けして$N<1000$なら$0$個、$1,000 \leq N<999,999$なら$N-999$個的な感じで処理。
Sample合ってたのに間違ってると勘違いして30分くらい存在しないミスを探してました。
D - Shipping Center
見たことありそうだけどナップザックではないのか、、、。
結果・感想
atcoder.jp
A~Cの3完でパフォーマンスは809、レーティングは475→516でした。
ギリギリ緑パフォだったにしてもBのペナとCのロスタイムが痛いですね。もっと早く解けていればもう少し高いパフォだったかも。
コンテストの途中から書き始めていたので投稿が早いですね。今日はこれで終わります。
2021/3/14追記：B問題が茶Diffだったらしいので緑パフォだったのはBが割と早く解けたからですかね。
ABC194
こんばんは。島崎翔です。今日はABC194に参加したので記録をしておきます。
A - I Scream
$4$通りの場合分けでした。場合分けを$A+B$の値と$B$の値でするべきだったのを見落として$A$の値で場合分けしてWA。問題文はよく読もう。
題材はアイスクリームでしたがチョコレートにも似たような分類があったような気が。
B - Job Assignment
基本的には一番短時間でこなせる人に仕事を割り当てますが、ある$1$人がどちらの仕事も一番短時間でこなせる場合が少々複雑です。仕事$A$または$B$を次点の人に割り当てるのか、$1$人に両方割り当てるのかの$3$通りですね。
C - Squared Error
まずなんとなく展開して整理してみたもののよくわからなかったので、小さな$N$で実験してみたところ$~N*($総和の$2$乗$)-(2$乗の総和$)~$なのではないかと思って書いてみたもののWAが出る。
考えてもなぜ落ちるかわからなかったのでGoogleで検索してみるとそれっぽいコードが見つかったのでそれをC++にして提出したところAC。漸化式的な解法だった。
結果・感想
atcoder.jp
A~Cの3完でパフォーマンスは544、レーティングは466→475でした。
AとCのペナルティが痛いですね。あとAではCEも出しました。実力以上のスピードで解こうとすると精度が落ちるということを痛感しましたね。次回はもう少し確実な提出を心がけようと思います。
書き始めとは日付が変わっていますが、今日はこれで終わります。
