AtCoder Beginner Contest 159

AtCoder Beginner Contest 159 - AtCoder

結果:5AC(4WA)
落としたのは問題E。なんだかなぁ。もう少し時間があれば行けそうな気がしたんですが。
後の祭り、粛々と解説読んで「あー」っていう仕事をしましょう。

問題A

 _nC_2を正しく計算できますか問題。
これが _nC_kだと格段に難易度が上がる。

問題B

真っ正面から3つ条件全部書いて終わり。
Python 以外だと、文字列の逆転とか面倒なんだろうなぁとか思いつつ。

問題C

立方体最適。高校でやった。

問題X: スタンド攻撃だっ……!

て…「敵」がいるのかッ! f:id:katoufujiBanana:20200322225204p:plain この「コンテスト」の中にッ!

怖いなぁ。
AtCoder の中の皆様、ほんまお疲れ様です。

問題D

素直に解いたら、計算量が N^{2} \simeq 4 \times 10^{10}とか言い出して TLE 起こしたので、ぐっと誤答の式をにらんで、ちょろっと式を変形したら、計算量が N程度になって AC。

問題E

今回解けなかった問題。
解説見る限り、アプローチは正しかったらしい。滑り込みで回答出しましたが WA。(だって答案書いている際にスニペット組むために使った定数値そのまま埋め込んだコードだから合ってるわけないっすわぁ)
ただ、それを修正したコードをテストしてみても、入力例3で正しい出力が出ず。何かまだ間違えていたんでしょうね。

問題F

とりあえず、LとかRとかは後からどうにかするとして、足してSになる組み合わせ全部出すかといってコードを提出。dp テーブルの中に、「どこからどこまで足したものですよー」という情報持たせつつ。
=> おそらく、組み合わせを持たせていたせいで計算量が減らず LTE

ぐっと dp を睨んで閃いたので、ごく一部だけいじった dp を素直に解いて、最後にいい感じのところ足し合わせて計算量をN \times S \simeq 10^{7}程度に。
=> MOD で割り忘れて WA。
=> やっぱ Python の限界でもう一回 LTE
=> PyPy で AC。詰め、甘々でゎ。

感想

わーい、順位3桁台だぁ。
ただ、問題Eがやはり悔やまれる。なまじ方針はあっていただけに。

パナソニックプログラミングコンテスト2020

Panasonic Programming Contest 2020 - AtCoder

これ、実質 ABC なのでは??
結果:4AC(3WA)

問題Bゆるすまじ

問題A

リストにぽい。

問題B

 H Wが両方奇数の場合とそうじゃない場合で場合わけすりゃ一発でしょ~ => WA

( 'ω')?

( 'ω')

( 'ω')????????????

あっ、身動き取れないパターンある。

問題C

これ、よくわからないけど、

import math
math.sqrt

すると、誤差で WA になる予感がする。--そう囁くのよ、私のゴーストが。
というわけで、誤差発生しないよう式変形して無事 AC。

問題D

こう、なんというか、 N が10以下って言ってるし、素直に全部書き起こしていく方針で書いて AC。

問題E

それぞれの文字列が、元の文字列の中でどこにいたか、最悪の場合  8001 \times 8001 \simeq 6.4 \times10 ^ {7} 回文字列の部分一致みないといけないなぁ。計算間に合わないんじゃねこれ、といって放棄。
あー、でも解説みるとなんかそれっぽい方法でごり押ししてんなこれ。もしかして C 系言語だと間に合う系? 言語の壁か辛いなぁ...、いや、PyPy で AC だしている人いますわ。ほげー。

問題F

頑張ったけど、ダメでした。解説を見ましょう。

┏━━フ━━┓
┃すごい定理┃
┗━━━━━┛

フ。

連結成分の定義が欲しいが、これ、「黒四角の塊いっぱいあるけど、そのうち1つだけ残してとれる最短距離を全部列挙して、その中の最大値が答え」って言ってます?
時間切れ直前に滑り込み投稿して、WA くらったんですけれども、多分「どれだけ迂回する必要があるか?」の方の計算を間違えてますね。惜しいような気はするが、WA は皆等しく、WA。無念。
いや、よくよく見直したらもう一個の方も間違えてますわ。あー。

感想

またも 4AC。ちょっと今回はレート変動見られていないのでブログには載せず。
コンテスト参加より、なんかまじめに勉強した方がよいのだろうか。
ぎぶみー蟻本。

日立製作所 社会システム事業部 プログラミングコンテスト2020

Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020 - AtCoder

三度目の企業主催コンテスト。
結果:2AC(1WA)

配点から見て、「AとBは解けて、あとどれくらい解けるかが勝負かなー。Cが解けるといいなぁ」と思いつつ挑戦し、結果見事(?)にAとBのみACして帰ってくるという。

ちなみに、Cは問題見て10分ぐらい考えて投げ捨てた。「距離3の節同士のグラフに組み替えて、そこから一個ずつ割り当てていっても、計算量 over しない?」って。

問題A

hi,
hihi,
hihihi,
hihihihi,
hihihihihi

問題B

そりゃ、M+ 1パターン調べて終わりですよねー。
ところで私は、乾燥機付き洗濯機が欲しいです。

問題C

上述の通り、10分ぐらいで放棄。
解説曰く、

解説「とりあえず2色に塗り分ける」
ワイ「えっ、距離3に着目したいのに?」
解説「こうする」
ワイ「はぇー」

とりあえず、2色に塗り分けるのって、グラフ系問題常套手段なんですかね? 探索ロジックとかしか勉強していなかったので、ここは盲点。ただ、微妙に知識問題とは少し毛色が違う感じもする。

問題D

問題Cを放棄した代わりにこちらに挑戦。
制約から、「DP っぽいけど、計算量が間に合わんな...。オーダーから考えて、おしゃれなソートキーが存在する?」と考え、紙にごりごり式を書いては因数分解を繰り返す。
だがしかし、コードテストが通らない。

時間切れにつき解説をみると、DP をやりつつも、おしゃれな場合分けで計算量をびっくりするほど圧縮していました。

なるほど理解したぞー、と再提出したところ TLE の嵐。うそやろ...。

問題E

配点で日和った。

問題F

配点で日和った。

感想

順位表を眺めたところ、参加者の約9割が300点以下というおもしろい結果に。また、ABC とは違った感じ。

なんだろう。何が足らないんでしょうね。場慣れ?

AtCoder Beginner Contest 158

AtCoder Beginner Contest 158 - AtCoder

結果:4AC(2WA)
あまり芳しくない。残念。

問題A, B, C

は、あまり特筆することもないかなぁって。

問題D

は、解説にある通り計算量を押さえる工夫が必要。
工夫せず提出して、一回 LTE を踏んで、1WA。

問題E

最終的にたどり着いたアルゴリズムは、解説の pdf と同じような感じ。計算量も同じはず。しかしながら、結果はLTE
コンテスト終了後コードを眺めて怪しい箇所を探していたところ、気づいたんですが、今回の  int(S) って  10^{200000} くらい行くじゃないですか。実際、手元の Python 10^{200000} % 3 を計算してみると、少しばかりラグが発生しているのを感じる。提出したコードの中で、この値を真正面から割り算して余りを出していたのがダメだったんじゃないかなっーて。

というわけで、毎回部分文字列切り出しては int にキャストしてやる方法から、こう...うまい感じにやる方法に変更したところ
Submission #10641667 - AtCoder Beginner Contest 158
AC 取れました。
何名か同じ方法で時間内に解いている方々いらっしゃいますね。

もったいない、これが出来ていれば 400~500 番台に入れていたのに。

問題F

未提出で終了。
例えばロボットが robot3, robot2, robot4, robot1, robot5 と並んでいて 31 まで到達して、15 まで到達するなら、3 を起動すると 5 まで起動するよね、ということが考慮できていないコードになってたのが、入力例・出力例3をコードテストに流したところ判明。

「どこまで到達できるのか、を保持させないといけないなぁ」と言って保持させる方法を考えている間に時間切れ。
あー。

感想

水色到達後、初 ABC(157 所用で不参加でした)でこの結果は、幸先が悪い!
Rating に暫定マークが出ていることもあって、今回は Rating 差分 -1 となりました。このままでは、緑~水色の境界をふらふらする人になるかも。巨大な数字の取り扱いにも、注意しないとなぁ...。
昔、階乗で痛い目にあって、メモリ・計算速度で不利にならないように、手元のコピペ用コード集には、MOD でよしなにしてくれる階乗計算や、累乗、_nC_kとか、逆元計算関数とかを準備していたのですが、自分で計算せずとも Python の仕様の弱いとこついてくる数をぶち込まれるのには無警戒でしたね...。反省。

AtCoder Beginner Contest 156

AtCoder Beginner Contest 156 - AtCoder

勝ち申した。
f:id:katoufujiBanana:20200222223755p:plain

6AC 達成しました!!

問題A

逆算できるかな問題。

問題B

高校のときセンターの勉強でやったなぁと思いつつ、記憶にある解法通り実装すると、底が2でないときに誤差が発生することが発覚
「高々30桁を超えることはないでしょ~。多分」と問題条件からざっくり計算して、ループの中でkをかけ合わせていき、誤差なくAC。ちょっと怖かったので、31までループさせました。

問題C

解析解を出すと、Pは全員の座標の重心に来る時が最適なのですが、Pも整数という条件があるので、重心を小数点以下四捨五入した値にすればOKと判断*1
「四捨五入する関数ってなんだっけ~」といってググって round 関数の丸め方向などの罠を看破(?)しつつ、素直に計算。AC。

問題D

累乗や、 _nC_kを効率よく計算できるかな問題。

問題E

「要素が全て0以上k+1以下の整数で、総和がnになるようなリストが何通りあるか」という問題に帰着。
要素の値域の制限がしんどい...と思いながら悩んでいたところ、

  • 実質制限なし(kがでか過ぎて、普通にnHn求めればOKな場合)

  • 実質制限あり(そうじゃない場合)

のパターンにとりあえず場合分け。
そして後者のパターンに悩んでいたところ、「各部屋にいる人数が最終的にいくら増減したか」に着目し、減るときは1人減るだけなことに気づいたところ、_nC_kとかを使った答えを発見。AC。

問題F

n_iの値域から、「本当に計算したら時間足りないんだろうなぁ」と思いつつ、「むしろ増えないタイミングっていつだろう?」という方向に注目。
(modがなければ増やせた回数) - (modがあるせいで増やせなかった回数) を計算してAC。

感想

競プロというより、高校の数学みたいな知識があると解きやすくなるような問題が多かった印象。しっかり勉強していてよかった。
ついに、今日のコンテストでめでたくレートが水色になりました。
目標達成! グラフがどうこう言ってたのはどうした。

つぎの目標は水色の維持。できればちょっとずつレートを積み上げながら。

*1:最小化したい関数が二次関数ゆえ。

AtCoder Beginner Contest 155

AtCoder Beginner Contest 155 - AtCoder

久々の参加からの解答確認即ブログ更新。
今回難しかったですね。結果3AC でヒヤッとした。

問題A

33-4
-> AC。雑に Python の Set に投げて、長さ2なら OK~って。

問題B

アルストツカに栄光あれ!
-> 「PならばQ」は「not(P)またはQ」であることを知っていたので雑に論理式書いて終了。

問題C

B.B.K.K.B.K.K.
何かの音ゲーというのは知っている。
=> dict にぽいっと投げて、素直に得票数最大のものを書き下して終わり。計算量耐えられるかな? と心配になったけど杞憂でした。

............。
.........。
......。

\         /_ /     ヽ /   } レ,'           / ̄ ̄ ̄ ̄\
  |`l`ヽ    /ヽ/ <´`ヽ u  ∨ u  i レ'          /
  └l> ̄    !i´-)     |\ `、 ヽ), />/        /  地  ほ  こ
   !´ヽ、   ヽ ( _ U   !、 ヽ。ヽ/,レ,。7´/-┬―┬―┬./  獄  ん  れ
  _|_/;:;:;7ヽ-ヽ、 '')  ""'''`` ‐'"='-'" /    !   !   /   だ.  と  か
   |  |;:;:;:{  U u ̄|| u u  ,..、_ -> /`i   !   !  \   :.  う  ら
   |  |;:;:;:;i\    iヽ、   i {++-`7, /|  i   !   !  <_      の  が
  __i ヽ;:;:;ヽ `、  i   ヽ、  ̄ ̄/ =、_i_  !   !   /
   ヽ ヽ;:;:;:\ `ヽ、i   /,ゝ_/|  i   ̄ヽヽ !  ! ,, -'\
    ヽ、\;:;:;:;:`ー、`ー'´ ̄/;:;ノ  ノ      ヽ| / ,、-''´ \/ ̄ ̄ ̄ ̄
                 ̄ ̄ ̄            Y´/;:;:;\

問題D

とりあえず、Aをソートして、積の小さい順に組み合わせにインデックス割り振るロジックを見つけて、そこからどこがK番目になるか逆算すれば...、え、負数も入ってくんの? やめてください死んでしまいます。

問題D 解答視聴後

ああ、正負で処理がちょっと変わるのは不可避なのね...。
模範解答の計算量は O(nlognlogh) の模様。但し h は積の最大値 - 積の最小値。ごりごりに二分木探索を使うのと、「K番目の値は何か」の代わりに、「この値は何番目か」に逆転させるのかー。

......。

どっちもどこかで見たことあるじゃ~~~ん。
頻出テクじゃ~~~ん。も~~~。

問題E

桁を小さいほうから見ていって、6以上なら一個上の紙幣でお支払い、5以下ならそのままの紙幣でお支払い。一個上の紙幣を出すときは繰り上がりに気を付けつつ...、だめだ、入力例3の答えが一致しない。

問題E 解答視聴後

なるほどー?
DP 使うと大丈夫で、上の自分の解答だとなぜダメなんだろう。わからない。わからないけど、少なくとも自分の解答では、N=955 のとき、1055 で支払いしようとするからだめだ。1000 でお支払いした方が枚数が少ない。前者12枚、後者10枚。そして確かに DP でやると、10枚という答えがでる。
うーん。
わからん。

問題F

あー、なんかこれどこかで見たぞ。
キーエンスさん(2020)の B - Robot Arms とか
ABC153 の F - Silver Fox vs Monster っぽいなぁ。
問題 D と E わからなかったし、これならいけるかもしらん。
-> WA(一部 TLE)。いけませんでした。

問題F 解答視聴後

全然ちゃうやんけ! グラフが出てきて、木がもりもり DFS してた。

結果発表

というわけで、3AC 600点。けれども Rating 上がってるのは幸い。
次回は今週土曜日とのことなので、参加するぞー。

AtCoder 経過報告

AtCoder Beginner Contest 152 - AtCoder
AtCoder Beginner Contest 153 - AtCoder

実は参加してました。 (152 が 5AC で 153 が 4AC)

そんなことより

ABC 153 までやった現在での Rating の遍歴がこちら。 f:id:katoufujiBanana:20200128081308p:plain

目標は水色なのですが、このままやっていると、茶~緑のあたりを行ったり来たりするランクに落ち着きそうな気がする。

ABC 153 の順位表を見たところ、どの色の人がどれくらいの戦績をあげているかというと

  • 5AC(緑)
  • 6AC 50分くらいから時間ぎりぎりまで(緑、水色)
  • 6AC 40分くらいで解き終わってる(水色、青)
  • 6AC 30分くらいで解き終わってる(青、黄色)
  • 6AC 20分くらいで解き終わってる(黄色、橙色)

6AC できないと水色には届かないとみてもよいんじゃあなかろうか。

ふりかえり

6AC を阻んでいたものが何かといえば、だいたい問題 E か F が解けていないというわけなのですが、

ここらへんが壁になっている(ような気がする)。

まじめに、今まで参加したコンテスト(ABC 以外含む)の問題を見返してきて、弱点をあぶりださねば。
はやいとこ、水色になって「アルゴリズム能力カンストっすわー*1。僕に仕事まわしてくれたら秒で解きますわー」って弊社内で言いふらしたいんすよ。弊社あんまアルゴリズムの難易度高い会社じゃないし。