AtCoder Grand Contest 048 参加記

AtCoder 競プロ AGC

2020/10/18に開催されたAtCoder Grand Contest 048に参加しました。

atcoder.jp

茶色コーダーの分際で参加するAGC。とりあえず1完できれば満足という感じで参加することにしました。

今回の結果

で、結局ノルマ達成の1完で終了です。

AGC048結果

AGC048結果

Unratedだったので、レート更新は無しでした。早くRated扱いで出れるようにならんとなー。。

振り返り

A問題だけで燃え尽きました。

AGC048提出結果

AGC048提出結果

A問題

A - atcoder < S

 "atcoder"と文字列Sを辞書順で比較する。Sが辞書順で大きくなるためには何回隣同士の文字を入れ替えるスワップという操作を行う必要があるかという問題。

 

とりあえず前処理で"atcoder"の文字長の長さの配列Aをつくり、

A_i = "atcoder"のi文字目より辞書順で大きい、Sのi文字目より後ろの文字のインデックス

 を作成する。

あとはA_i - iの最小値を求めればOK。。かと思いきや何故かWAを食らったｗ

 

WAになるケースが全然わからないまま数十分時間を浪費したが、よくよく考えると"atcoder"のi文字目とSのi文字目が同じ場合と違う場合で判断を変える必要があったりしたので、そのへんをいじくったらなんとかACしました。

 

で、結局A問題だけで100分近く消費しました。もう後の問題に取り組む気力が残ってません。

B問題

B - Bracket Score

 問題の意味はなんとなくつかめましたが、何をすればいいのか見当がつきません。

早々にあきらめ。

C問題

C - Penguin Skating

 🐧が滑ってるのはなんとなくイメージできましたが、これも何をすればいいのかわかりません。これも早々にあきらめ。

D問題

D - Pocky Game

 問題すら見てません。

E問題

E - Strange Relation

 Dと同じです。

F問題

F - 01 Record

 これ、コンテスト中に誰も解けてないんだけど。。

これまでの実績

最初に触れたとおり、Unratedなので今回レート更新なし。

コンテスト実績

コンテスト実績

総括

今回なんとか1完取れました。次は2完以上取れるように精進します。

また、次回も頑張ります。 

AtCoder Beginner Contest 180 参加記

AtCoder 競プロ ABC

2020/10/17に開催されたAtCoder Beginner Contest 180に参加しました。

atcoder.jp

もともとこの週末はABCコンテスト無しかなという認識でいたんですが、金曜午後ぐらいになってAtCoder公式からABCやるかもツイートがあったので一応気にはかけてました。

で、結局当日の午後3時すぎという、開催まで4時間切ってる段階での開始決定。その時点で外出中だったので、ちょっと今回は参加するかどうか迷いましたが、ちょいと予定より早めに帰宅して参加することにしました。

今回の結果

で、今回の結果はボチボチの4完終了となりましたー。

ABC180結果

ABC180結果

解けた問題の難易度を考えると今回も緑パフォーマンスぐらいかと予想してましたが、果たしてその通りでした。

レートはまた少し上昇。着々と緑まで近づいています。

振り返り

今回は、しょうもないミスを繰り返してしまいました。

ABC180提出結果

ABC180提出結果

A問題

A - box

 N - A + Bを計算すればOK。問題なくAC。

B問題

B - Various distances

 問題にある式どおりに計算すればOK。の、、筈でしたが、値をintで計算したのでオーバーフローしたり、そもそもチェビシェフ距離の計算式が間違ったりで合計2WAも喰らいました。

3回目でどうにかAC。

C問題

C - Cream puff

Nの約数を昇順に列挙する問題。 

素数がどうのこうのと考えるよりは、普通に計算した方が早いかと判断し、2から\sqrt{N} + 1までの整数それぞれでNを割り、余りが0なら、割った数と商をそれぞれTreeSetに入れるというやり方を選択しました。

が、、N = 1の時に1、1と出すというバグを踏んでWA。。

小ミスが多いなとボヤキながら、なんとかAC。

D問題

D - Takahashi Unevolved

 強さと経験値の増え方を愚直にシミュレーションするやり方で解きました。

現在の強さをA倍した場合と、B足した場合を比較し、後者の強さが小さい場合は後者を選択し、そうでなければ前者を選択するという方式で、強さがYを超えないギリギリのところまでシミュレーションを繰り返しました。

初回の提出では、効率化ができておらずTLEを喰らいましたが、ロジックを改善した2回目の提出でなんとかAC。

E問題

E - Traveling Salesman among Aerial Cities

 残り30分ちょいでEまでたどり着きましたが、ここが限界。

問題を一読する限り、各都市間の距離を前処理で計算しておいて、DFSなんかで最短距離を出すのかなー？的な印象でしたが、結局あれこれ試行錯誤した結果、コンテスト終了までに実装が追いつきませんでした。

実際、このブログを書いている今でも解法は分からずじまいなのですが、今週中に自力ACをしようかというところです。

F問題

F - Unbranched

 順位表みる限り、めっちゃ難しい問題雰囲気なんで早々に諦めでした。

また、後日解説ACします。

これまでの実績

前回のABC179の時点では灰落ちするかもー的なことを書いてましたが、直近はなんとか上昇傾向になっています。

コンテスト実績

コンテスト実績

 

総括

問題が解けなかったことも反省点ですが、今回ミスが結構多かったのがより大きな反省材料かと感じています。B、C問題のミスについてはもう少し要因を分析せねば。。 

というわけで、また、次回も頑張ります。

 

AtCoder Regular Contest 105 参加記

AtCoder 競プロ ARC

2020/10/11に開催されたAtCoder Regular Contest 105に参加しました。

atcoder.jp

ARCの参加は先週に続いて2回目になります。

前回の感想としては、最初の2問ぐらいがABCの前半レベルで、あとはめっちゃ難しいという感じなんで、今回は2完ノルマで臨んでみることにしました。

今回の結果

で、今回の結果はノルマ通りの2完終了となりましたー。

ARC105結果

ARC105結果

緑パフォだったので、レーティングはプラス。連日のHighest更新となりました。

振り返り

前回と同じく、C問題以降は歯がたたずでした。

ARC105提出結果

ARC105提出結果

A問題

A - Fourtune Cookies

A,B,C,Dが与えられる。そこから1つ以上の数を選んだとき、選んだ数の和と選んでいない数の和が同じになることがあるかという問題。

一目上手い解法が思いつかないので、とりあえず愚直でやることに。

もらったA,B,C,Dを配列につっこんでソートしてから、以下の判定をしました。

  • 一番大きい数と、残りの数の和が一緒ならYES
  • 一番目と二番目に大きい数の和と、残りの数の和が一緒ならYES
  • 一番目と三番目に大きい数の和と、残りの数の和が一緒ならYES
  • 一番大きい数と一番小さい数の和と、残りの数の和が一緒ならYES
  • 上記の条件にあてはまなければNO 

他の上手いやり方もあるかと思ったが、考えてる時間もないので、ゴリ押しで実装してAC。

B問題

B - MAX-=min

 これも上手いやり方がわからんので、愚直にシミュレーションすることに。

配列aを読んでいって、数字とその個数をそれぞれTreeMapのKeyとValueで管理していく。最大値XはlastKey()、最小値xはfirstKey()でそれぞれ取得できるので、あとは、問題にある通り随時最大値のカードをX - xに書き換えていく。

この処理を続けて行って、Mapのサイズが1になったら終了。

 大分愚直な実装で、実際提出したら、結構反応が鈍い。あわやTLEあるかとヒヤヒヤしましたが(笑)、なんとか1.7秒台で終わってくれました。

後日もっといい解法がなかったか調べたいと思います。

C問題

C - Camels and Bridge

この問題から全く歯がたたず。

考察としては、ラクダの数の最大が8とかなので、橋のパーツの数とラクダの数で2次元配列作ってDPすればいいんじゃね？的な雑な考えしか浮かばずでした。

結局、それっぽい実装をしたものの、サンプルの4分の2しか通らずで結局提出できず。

他の問題もチラ見しましたが、そのままCに時間を費やしてタイムアップとなりました。 

D問題

D - Let's Play Nim

 Nimというのは、以前のコンテストでも題材に上がって居たやつで、全部の山の数のXORをとって結果が0だとどっちかが必勝(うろ覚え)という知識ぐらいしかありません。

問題文に少し目を通しましたが、これならCの方がやれそうかな？という根拠のない自信が出てきたので、パスしました。

E問題

E - Keep Graph Disconnected

 問題文だけチラ見して退散しましたー。

F問題

F - Lights Out on Connected Graph

 Eと同じです。

これまでの実績

一応Highestですが、今の実力だと、いいとこ緑←→茶を行ったり来たりする未来しか見えないです。

コンテスト実績

コンテスト実績

総括

 ゴリ押しでなんとかなる問題ぐらいしか解けてない感があります。

高レベルの問題もコンテスト中に解けるように精進していくしかないですね。

また、次回も頑張ります。

HHKB プログラミングコンテスト 2020 参加記

AtCoder 競プロ 企業主催コンテスト

2020/10/10に開催されたHHKB プログラミングコンテスト 2020に参加しました。

atcoder.jp

2週間ぶりのABCクラスのコンテスト。ここ数回は2完で終わってしまうことも結構あったので、何とか3完をノルマとして頑張ることにしました。

今回の結果

で、今回はノルマ通りの3完で終了です。

HHKB2020結果

HHKB2020結果

2完終了つづきで、下がってた分は取り戻せました。

一応Highestは更新してますが、個人的にはまだ満足行く結果じゃないので、正直更新できて嬉しいという実感はありません。

振り返り

D以降は提出できずでした。

HHKB2020提出結果

HHKB2020提出結果

A問題

A - Keyboard

Sが'Y'ならTの文字を大文字で出力しましょうという問題。

Javaなら大文字変換はtoUpperCase()でやれば良いです。

あとは実装だけ、、と思ったが変にtypoしてまったせいで提出にモタついてしまい、遅めの3分台でAC。

B問題

B - Futon

 一瞬Bにしては難しい問題かな？と思いましたが、縦横がそれぞれ100以下と小さいため愚直なやり方で通すことにしました。

縦横の位置それぞれ2重ループを回しつつ、現在位置と右、または下が散らかっていなければカウンタをプラス1する実装でAC。

C問題

C - Neq Min

解法の検討で大分モタつきましたが、p_iの最大値が200,000ということで、以下の解法で解きました。

  • サイズが200,000を少し超えるぐらいの配列aを初期値0で作成
  • p_iを読んで、a[ p_i ]をプラス1する。その後配列aの値が0となる最小のインデックスを出力する。これをN回繰り返す。

 大分愚直感のある実装で、提出後の反応がいまいちなことから、一瞬TLEもあるかとヒヤヒヤしましたが、なんとか実行時間1sec程度でACしてくれました。

D問題

D - Squares

 解けずでした。おそらく1個1個のケースについて解くなら愚直でやればいいかもしれんが、最大100,000個のケースを一回で通すとなると、個々の計算でループ回すわけにも行かないです。何らかの方程式で解けるやり方があるか色々検討しましたが、結局実力が足らずで時間切れでした。

E問題

E - Lamps

 問題を一目見て、解法がまったく思いつかず。こりゃ多分解答になんかのテクニックが必要なやつだと思って、早々に諦めました。

F問題

F - Random Max

 まったくもってわからず。後日見直します。

これまでの実績

 一応、Highest更新ですが、緑はまだ遠そうです。

コンテスト実績

コンテスト実績

 

総括

なんとか2完終了は回避しましたが、最近水色diff以上の問題がコンテスト中にまったく解けてないのが停滞の原因だと思ってます。高難易度の問題の精進にいっそう取り組もうと思います。

また、次回も頑張ります。

AtCoder Regular Contest 104 参加記

AtCoder 競プロ ARC

2020/10/3に開催されたAtCoder Regular Contest 104に参加しました。

atcoder.jp

さて、私自身AtCoderを始めたのが今年の5月ぐらいなので、ARCというのに参加するのが今回初めてです。そのためARCがどういう位置付けなのかはわかってませんが、まあなんかいろいろ情報を収集してみて、ABCとAGCの中間ぐらいのやつかないう認識です。

配点をみてると、なんとか2問程度は解けるかなという感じだったんで、2完以上を目標にすることにしました。

今回の結果

で、今回は結果は目標通りの？2完でしたー。

ARC104結果

ARC104結果

2完でもパフォーマンスはそこそこだったので、レートの方は上がってくれました。

振り返り

C以降は全く歯がたたずでした。

ARC104提出結果

ARC104提出結果

A問題

A - Plus Minus

方程式を解いていく。

 A + B = 2Xとなるので、Xは求めるのが簡単。

XがわかればＹ= A - Xなので、Yも簡単に求まります。

あとは、実装だけしてAC。

B問題

B - DNA Sequence

文字列Tが問題文にあるような条件を満たすかを判定するには、文字列Tの中に存在する'A'の個数と'T'の個数、'C'の個数と'G'の個数がそれぞれ同じかを判定すれば良いです。

あとは文字列Sのi文字目までにある'A','T','C','G'各文字のそれぞれ個数がわかるような配列を前処理で作っておけば、累積和を計算する要領で、文字列Tが条件を満たせるかを速く判定できます。

実装に少してこずったものの、なんとかAC。

C問題

C - Fair Elevator

 問題文の言ってることが最初よくわかりませんでした。

しかし、よくよく考えて、エレベータ内部をキューに見立てるといいんじゃないかという考えに至りました。先に入った人が先に出る。後に入ってきた人が、その時にいた人より先に出ることは無いという条件が満たせればOK。

 

と、いうとこまでは考察できたんですが、結局、記録の欠落してる部分のパターンをよく考えたときに実装できるような解法が思い浮かばすで、断念しました。

D問題

D - Multiset Mean

 問題文は見ましたが、解き方が全く不明でした。

E問題

E - Random LIS

 このあたりまでくると、問題文もろくに読めずでした。

F問題

F - Visibility Sequence

 Ｅとおんなじで、問題文もろくに読めず。

これまでの実績

なんとかここ数回の下げ分は取り戻しましたが、緑はまだまだ遠そうです。

コンテスト実績

コンテスト実績

総括

今回のコンテストでは、C問題が解けると大分パフォーマンスが跳ね上がってくる感じでしたが、それができるようなレベルに上がるためにはまだまだ精進が必要であると感じました。

また、次回も頑張ります。

追伸

で、さらなる向上をめざすべく、TLで話題になってた、アルゴリズム本をさっそく購入しました。少なくとも年内には読み通してみようかと思ってます。

アルゴリズム本

アルゴリズム本

 

ACL Beginner Contest 参加記

AtCoder 競プロ ACL

2020/9/26に開催されたACL Beginner Contestに参加しました。

atcoder.jp

で、本来この週はRatedコンテストはなかったはずだったんですが、ACL2が延期になったとかで、当日急遽このコンテストが開催されることになってました。この週はぼちぼちと精進してく予定だったんですが、折角なんで参加してみることにしましたー。

今回の結果

で、今回は、3完というぼちぼちの結果で終了です。

ABL結果

ABL結果

ちょうど今のレーティングとおんなじぐらいのパフォーマンスで、レーティング変動なしでした。

 振り返り

B,Cで結構やらかしました。

ABL提出結果

ABL提出結果

A問題

A - Repeat ACL

 入力されるKの数分"ACL"と繰り返し出力しろという問題。

ACL言いたいだけやろと思ったが、とりあえず言われたとおりに実装してAC。

B問題

B - Integer Preference

 条件を整理すると、B \lt CかD \lt AだったらNo、それ以外はYesと出力すればよいので、あとは実装だけしてAC。。

と、おもったら制限がlongの範囲だったので、int型で取ってたプログラムがCEとなった。。。longで取り直してやっとAC。

制限はちゃんと見とけという知見を得ました。

C問題

C - Connect Cities

 問題文をさらっとみて、これUnion-Findで繋いで、出来上がったグループの数のマイナス1が答えということに気付く。

というわけで、とりあえず少し前のABCの問題にUnion-Findの実装があったんで、そっからコードを引っ張ってくることに。

で、その時のACしたコードの出力をマイナス1したらなんかサンプルデータのテストが通ったんで、とりあえず投げてみたらWA食らいましたｗ

まー、さすがにこれで通るぐらい甘くはないだろうということで、今度はUnion-Findの内部のroot配列(根となる要素の配列)に存在する根の種類の数からマイナス1したやつで投げてみたら、これも何故かWA。。。

あまりにも謎な結果だったので、ほかの問題に移ってみたりテストを増やしてみたりといろいろ試した挙句、ACLのPractice ContestのDSU問題から適当なDSUクラスの実装コードを漁ってきて、ごにょごにょした結果あっさりACが取れました。

前の実装のWAの原因が不明でしたが、とりあえず2完終了は阻止したので結果オーライです。

D問題

D - Flat Subsequence

 問題文見てみたんですが、解法がわからんかったのでパス。

E問題

E - Replace Digits

 これも上手い解法は思いつかなかったんですが、とりあえず愚直に実装するコードぐらいは書けそうだったので、とりあえずサンプルは通るコードを書いて投げてみました。

で、案の定TLE食らいました。。

F問題

F - Heights and Pairs

 結局、問題文を一読しても解法は思い浮かばすでしたー。

これまでの実績

相変わらず、茶色の真ん中下あたりをうろうろしています。

コンテスト実績

コンテスト実績

総括

 今回はAC-Libraryを使った練習セットの問題だったということで、ライブラリ周りの知識不足を痛感しました。セグ木とかBITとか現在勉強中なので、自力でライブラリを整備していこうと思っています。

また次回も頑張ります。

AtCoder Beginner Contest 179 参加記

AtCoder 競プロ ABC

2020/9/19に開催されたAtCoder Beginner Contest 179に参加しました。

atcoder.jp

前回は2完を喰らってしまったので、今回はそのリベンジとばかりに気合を入れて臨みました。

今回の結果

で、肝心の結果ですが、今回も2完終了となりました。ヽ(`Д´)ﾉｳﾜｰﾝ

ABC179結果

ABC179結果

灰色パフォーマンスでレーティングは大幅下げ。灰色落ちの危機を向かえそうです。

振り返り

ABC179提出結果

ABC179提出結果

A問題

A - Plural Form

 文字列の末尾で処理を分岐する問題。Javaだとs.endsWith("s")で分岐すればよい。

問題なくAC。

B問題

B - Go to Jail

ループ処理だが、言われたとおり実装するだけ。問題なくAC。 

C問題

C - A x B + C

 この問題でやらかしてしまった。。

A \times B + C = Nを満たす正整数の組(A,B,C)の数を求める問題。

A \times B \lt NとなるA,Bを決めれば、Cは一意に求まる。なので、1からN - 1までのXについて、それぞれ何通りのA \times Bで表すことができるかの組み合わせの数を足し合わせればいいやと考えました。

しかし、ここからが結構厄介で、Xが素数の場合とか、平方数の場合とか、素因数分解したときに同じ素数が複数入ってる場合など色々考えしまい、混乱してしまいました。

で、結局いろいろライブラリなどを使ってこねくり回したものの、結局サンプルすら通らないので退散。。

この問題、後日よくよく考えたら、Aを1からN - 1のそれぞれについて、

A \times B \lt NとなるBの数、すなわちfloor((N - 1)/A)の値を足し合わせれば答えになることに気付きました。

これだと、この問題が灰色diffなのも納得がいきますね。

D問題

D - Leaping Tak

 早々にC問題を諦めて、Dに取り組むことに。

この問題、色々考察するも、結局愚直に各区間のDPを行うやり方しか思いつかない。

なので、とりあえずサンプルが通る実装を行い、多分ダメかなーとおもいつつも提出したら、やはりダメ。結局TLEを喰らってしまいました。

解説をみると、DP高速化が必要とのことで、まだ色々勉強が足らないと思いました。

これを機会に覚えることにします。

E問題

E - Sequence Sum

 C,Dが散々な出来なので、コンテスト中はチラッとしかみれませんでした。

コンテスト後のTLで周期性なるキーワードが出て解法がわかったので、後日ACしておきました。

F問題

F - Simplified Reversi

 これもコンテスト中はチラッとしかみてませんでした。

ま、後日解説ACでもすることにします。

これまでの実績

うかうかしてると、冗談抜きで灰色落ちしそうです。。

コンテスト実績

コンテスト実績

総括

実力不足を思い知らされる結果が続きますが、これを乗り越えるには日々精進をつづけていくしかないですね。 

次回も懲りずに頑張ります。