エイシングプログラミングコンテスト2020参加記

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

2020/7/11に開催されたエイシングプログラミングコンテスト2020に参加しました。

atcoder.jp

今回の配点を確認すると、難易度はABC並というところ。ここ最近のABCの成績は2完終了続きなので、今回はそれ以上を目指していました。

今回の結果

で、今回は3完で終了。ギリギリ2完を回避！

エイシング2020結果

エイシング2020結果

レートの方も一応上昇です。

振り返り

エイシング2020結果

エイシング2020結果

A問題

A - Number of Multiples

倍数の個数を勘定する問題。

制約が100までと小さいので、問題文のとおりLからRまでfor文で回して実装してAC。

B問題

B - An Odd Problem

配列の順番と中身がいずれも奇数である個数を数え上げる問題。

これも制約が100までと小さいので、問題文の通り実装してAC。

C問題

C - XYZ Triplets

最近鬼門のC問題。

制約上、xを100までのループとして、y <= x,y <= zの条件で3重ループを回す全探索でいけるとの見込みで実装し、なんとかACできました。

とりあえずレート下げは回避できたかと、一安心です。

D問題

D - Anything Goes to Zero

ここまでほぼゴリ押しの実装で通せましたが、この辺で限界がきました。

整数Xを2進数で表した時の1の個数で割り続ける操作が何回できるかという問題でしたが、制約上Xの最大値が2の20万乗ぐらい。最初の1回目の余りの取得ができればというとこでしたが、このへんの実装に詰まってしまい、この問題はパスすることに。

E問題

E - Camel Train

コンテスト中に問題文には目を通しましたが、解法が思いつかずでした。

コンテスト後、解説を参考にしてやっと解けましたが、前の方が好きなラクダと後ろのほうが好きなラクダそれぞれ独立で考えるというやり方に考えが至らずでした。

F問題

F - Two Snuke

 解法すら思いつかないが、ABCの600点問題とは思えないような難易度かと。。

今回の実績

レーティングは、ちょこっと上がりました。早く茶色抜けしたいのですが、グラフをみるとなんとなく停滞ムードが漂います。

コンテスト実績

コンテスト実績

総括

ゴリ押し実装のみで3完達成でした。今後はゴリ押しで解けない問題も中心に精進していきます。

ABC173 参加記

AtCoder 競プロ ABC

2020/7/5に開催されたABC173に参加しました。

atcoder.jp

前回は成績が悪く、あわや灰色転落の憂き目にあうかというところでした。

今回はなんとか3完以上の結果を出して、レート上昇を目指したいです。

今回の結果

で、、、

ABC173結果

ABC173結果

前回に続き2完終了。。ヽ(ﾟ`Д´ﾟ)ﾉﾟ｡ｳﾜｧｧｧﾝ!!

振り返り

ABC173提出結果

ABC173提出結果

A問題

A - Payment

今回もAは計算するだけ問題。特に詰まることなくAC。

B問題

B - Judge Status Summary

特定文字列の出現回数を集計する問題。これも特に詰まることなくAC。

C問題

C - H and V

なんかうまい計算方法がありそうでなさそうな微妙な問題。

タテヨコの制約が最大6であることから、愚直に全検索して解答する問題だと判断したが、結局実装が追いつかずで提出すらできずでした。

コンテスト後の解説で、bit全探索の手法があることを初めてしりました。

今回を機に覚えておこう。

D問題

D - Chat in a Circle

なんか法則性があるのかと思い、色々と検討したが結局コンテスト中に思いつかず。

最近カンが働かんなー。

E問題

E - Multiplication 4

多分でかい方から順に掛け算していって、後でマイナスを調整するのかなーという感じで検討。しかし、考えれば考えるほど対応が難しいケースが思いついてしまい、結局挫折しました。

F問題

F - Intervals on Tree

まともに読む時間も残ってませんでした。後ほど解説を確認すると、実装自体は単純だったようです。

 

今回の実績

2完だったけど、なんとか茶パフォで凌げたので、結果レートはプラスでした。

ひー、あぶないあぶない。(^_^;)

コンテスト実績

コンテスト実績

総括

前回、今回と2完終了。もうこのまま一生上のランクに上がれないのかーと思ってしまいますが、なんとかめげずに精進していこうと思います。

Introduction to Heuristics Contest 参加記

AtCoder 競プロ Heuristics Contest

2020/6/28に開催された、Introduction to Heuristics Contestに参加しました。

atcoder.jp

今まで参加してきたABCのように、入力に対して正解を出力するプログラムを作るのでなく、できるだけ良い解を出力するプログラムを作るコンテストだそうです。

 

正直この手のコンテストには、経験も何もない状態ですが、とりあえず勉強がてらということで参加してみました。

今回の結果

で、結果は以下の通り。1点しか取れずで終了となりました。

IHC結果

IHC結果

振り返り

IHC提出結果

IHC提出結果

一度A問題に目を通しましたが、とりあえず訳がわからんかったのと、入門者向けガイドということでB問題を案内されたので、Bから取り組むことに。

B問題

B - Scoring

A問題の小問題のような感じ。スコア計算をするプログラムを書いてAC。

これで1点ゲットw

C問題

C - Incremental Scoring

これもA問題の小問題。コンテスト日程を色々変更することによるスコアの推移を出力するプログラムを書いたが、実装がまずかったか、TLEを喰らってしまった。

 

とりあえず、残り時間も少ないし、1回はA問題提出したかったので、この問題はパス。

A問題

A - AtCoder Contest Scheduling

で、コンテスト残り30分ぐらいで取り掛かったA問題。

 

難しいことはよくわからんが、とりあえず各日ごとの満足度の最大値のコンテストを選んでおけば何点か取れるんじゃね？ってことで実装して提出してみましたが、なぜか結果0点を喰らってしまいました。

 

どこかバグってるんじゃねーか？と思い色々調べてみましたが、最低限アウトプットの仕様は守ってるハズということで、残り時間で2回ほど小改造したプログラムを提出したものの、結果はいずれも0点。

 

おいおい、ちょっと基準厳しすぎじゃね？とか言ってるうちに時間終了となりました。

今回の実績

今回のコンテストはratedでないので、レーティング変動はありませんでした。

総括

前提知識ほぼゼロの状態で参加しました。散々な結果でしたが、多少の経験が積めたのはよかったと思います。この手のコンテストで成績が出せる様に今回の問題を復習しようと思います。

 

ABC172 参加記

AtCoder 競プロ ABC

2020/6/27に開催されたABC172に参加しました。

atcoder.jp

前回のABC171では5完を達成し、やっと灰色を卒業しました。

今回は、次の緑色レート達成に向けて、さらにレーティング上げを目指したいところです。

今回の結果

で、、今回の結果は無念の2完終了でした。。。

ABC172結果

ABC172結果

灰色相当のパフォーマンスで、レーティング下げ。灰色転落するかと思いました。。

振り返り

ABC172提出結果

ABC172提出結果

A問題

A - Calc

計算するだけ問題。特につまるとこなくAC。

B問題

B - Minor Change

2つの同じ長さの文字列を比較し何箇所文字が異なるかを答える問題。

これも特につまるところなくAC。

C問題

C - Tsundoku

問題をみて、机A、Bから、数字の小さい方を選び続ければOKやん、と思った問題。

Queueを使った実装をして、サンプルが通ることを確認後、意気揚々と提出したらWAを喰らいました。

 

で、よくよく考えたら、例えばAの方が数字が大きい場合も、その次に極端に数字が小さい本が連続するケースとかでまずいやん、と気づきました。

 

結局コンテスト中は上手い解法が思いつかずでしたが、終わってみれば基本的なしゃくとり法などで解ける問題でした。これが思いつかないのは、自分が実力不足だということですね。

D問題

D - Sum of Divisors

素因数分解とかして約数の個数求めるのかと思ったが、まともに全て数について約数の個数を個別に計算してたら間に合わんやろということで、実装に悩みましたが、結局実装できずでした。

E問題

E - NEQ

コンテスト中に問題文を読んだが、解法が全く思いつきません。

後でみると、包除原理を使って解く問題とのこと。これもこの機会に覚えるようにする。

F問題

F - Unfair Nim

で、このゲームの必勝法が存在する条件はなんなん？？というところで考察がとまりました。

タイトルから察すればよかった、てことかいな？

今回の実績

前回やっと灰色卒業したのに、もう転落の危機を迎えましたw

コンテスト実績

コンテスト実績

総括

今回は、また自分の実力不足を痛感する結果でした。

次回に向けて、過去自分が解けなかった問題を中心に復習を行い、レベルアップを図っていこうと思います。

ABC171 参加記

AtCoder 競プロ ABC

2020/6/21に開催されたABC171に参加しました。

atcoder.jp

前回のABC170では、灰色卒業目前のところが400未満のパフォーマンスしか出せず、灰色卒業のおあずけをくってしまいました。今回こそ文句なしの灰色卒業と行きたいところです。

今回の結果

で、結果は自分でも驚きの5完達成！

ABC171結果

ABC171結果

文句なしの灰色卒業です。

振り返り

ABC171提出結果

ABC171提出結果

C問題

C - One Quadrillion and One Dalmatians

前回、C問題でWAを何回かやらかしたので、今回はあえてC問題から着手することにしました。で、このC問題がなかなかの厄介な問題。

 

問題をみて、こりゃ10進数をAーZの26進数のように変換する問題かと考え、なんとかサンプルケースが通る実装をして提出したものの、結果はWA。。

 

色々なケースを考えて、ローカルでテストを繰り返した結果。どうも各桁を算出する際に毎回1を引いてけばうまくいくという結論に至り、なんとかACが取れました。

 

以下は実際に提出したコード。

https://atcoder.jp/contests/abc171/submissions/14565211

 

で、この問題だけで40分以上かかってしまいました。

A問題

A - αlphabet

入力された文字が大文字か小文字かを判別する問題。特につまるとこなくAC。

B問題

B - Mix Juice

入力された数列から、小さいもの順に何個か足していく問題。これも詰まるとこなくAC。

 

D問題

D - Replacing

数列が与えられ、数列内のある数全てを別のある数に置き換えたら、合計がどう変わるかを答える問題。

 

数字を添字にした配列を作り、数の個数を管理すれば計算量が抑えられるということに気付き、なんとかAC。

E問題

E - Red Scarf

自分以外の全ての数字をXORした数が数列として与えられる。元の数列を答えなさいという問題。

 

あまり時間もないので、もう直感に頼るしかない。

 

たぶん入力の数列全部XORしとけば、なんか色々打ち消されて、そっから元の配列の各要素とそれぞれXORすればいいんじゃないだろうか。という雑な考察で実装してみたら、サンプルケースが通ってしまいました。

 

で、とりあえず提出したら、なんとACが取れました。完全にヤマカンです。

F問題

F - Strivore

問題文に目を通すだけの時間はありましたが、カンで解ける様な問題ではなく、ここで時間切れとなりました。

今回の実績

参加6回目にして、やっと灰色卒業です。

コンテスト実績

コンテスト実績

総括

過去最高の5完達成となりましたが、どうも今回は難易度が以前と比べて低めだったようです。とはいえ目先の灰色卒業という目標は達成したので、次は緑を目指して頑張っていこうと思います。

AGC046 参加記

AtCoder 競プロ AGC

2020/6/20に開催されたAGC046に参加しました。

atcoder.jp

過去2回参加したAGCでは0完フィニッシュ。さらに灰色レートのため、レーティング対象外であり、およびでない感をひしひし感じるのですが、参加するだけならタダなので勉強がてら参加という感じです。

 

ま、今回は配点をみるとなんとか1完は行けそうな予感があります。

今回の結果

で、結果は予告どおりの1完で終了です。AGC参加3回目にして0完卒業！

AGC046結果

AGC046結果

振り返り

AGC046提出結果

AGC046提出結果

A問題

A - Takahashikun, The Strider

気合を入れて臨んだA問題。初手からわけがわかりませんでしたw

ABCの200点とは難易度が段違いですww

 

0完終了の嫌な予感もしながら、検討に取り掛かります。

 

最初に三角関数使って動く座標を計算するやり方が思いついたが、なんか誤差とかの関係でドツボに嵌まりそう。。問題の雰囲気からして、単純な公式を当てはめれば解けそうな感じがするなーという感じで考えてました。

 

で、色々考えた挙句サンプルの解答、X=90でK=4、X=1でK=360から推察して、Xと360のGCDを求めて、360をそれで割ってみりゃいいんじゃね？ってことで組んでみたらなんとか一発でACしてくれました。

 

大分ギリギリでしたが、とりあえず今回の目標達成です。

B問題

B - Extension

ほとんどA問題で燃え尽きてるんですが、B問題も覗いてみました。

 

で、わかりませんでした。

 

特にどうすれば重複するケースを排除できるのかがわからん。もう少し精進が必要。

C問題

C - Shift

わかりませんでした。

D問題

D - Secret Passage

わかりませんでした。

E問題

E - Permutation Cover

わかりませんでした。

F問題

F - Forbidden Tournament

わかりませんでした。

今回の実績

画像は前回の使い回し。レート更新の対象外のため、前回と変わらずです。

コンテスト実績

コンテスト実績

総括

今回は、ほんとギリギリで1完達成できました。

 

次回は2完以上！と言いたいとこですが、正直自分の実力では全然足りません。

 

あまりできないことをあれこれ考えてもしょうがないので、AGCの過去問にもぼちぼちと取り組む時間を作っていこうと思います。

ABC170 参加記

AtCoder 競プロ ABC

ABC170に参加しました。

atcoder.jp

前回のABCは4完だったので、今回も前回と同じ4完が目標。

前日の東京海上日動プログラミングコンテストでレーティング398まで上昇したので、今回の結果で灰色卒業は間違いないだろうなーと思っておりました。

今回の結果

で、終わってみれば目標未達の3完終了です。

ABC170結果

ABC170結果

しかも、C問題で相当WAをやらかしてしまい、今回は400未満のパフォーマンス。

灰色卒業は、おあずけとなりました。

振り返り

ABC170提出結果

ABC170提出結果

A問題

A - Five Variables

 入力が5個あって、何個目に0があるかという問題。とくに詰まるところなくAC。

B問題

B - Crane and Turtle

 入力はX、Yの整数。鶴と亀が合わせてX匹、足は総数Y本となる鶴と亀の数の組み合わせが存在するかという問題。

 

ちょいと上手い解法がわからんかったので、愚直にIF文の分岐をたくさん使い、なんとかACまでこぎつけました。

C問題

C - Forbidden List

整数Xと数列が与えられ、Xと絶対値が近い整数の内数列に存在しないものを探すという問題。

 

数値の上限値も小さいので、int[102]程度の配列を作って数列内の数字を添字にする要領で実装すればいいんじゃね？ってことで提出まで漕ぎ着けてみれば、これがWAの繰り返し。

 

そもそも絶対値が同じ解が複数ある場合に低い値を出すという条件を見落としてたり、解答が0になるケースの実装が怪しそうだったりとかで、もう色々直しながら提出してたら、結局5回もWAを喰らった後、やっとACが出せました。(なんか当てもんみたいになってしまったw)

D問題

D - Not Divisible

整数の数列が与えられ、数列内の他のどの数字でも割り切れない数はいくつかを答える問題。

 

多分愚直にやるとTLE喰らいそうだから、ソートしてから評価すればもうちょい効率よくなるのでは？という感じでサンプルケースが通るコードを作ってみましたが、提出してみれば、結局TLE。。

 

コンテスト中は改善策が思いつかず、この問題はここで諦めました。

 

あとで解説をみてみれば、エラトステネスの篩の要領でやれば計算量が抑えられたとのこと。全く思いつかなかったなーと反省しました。

E問題

E - Smart Infants

 問題文読むと、普通に考えて実装めっちゃ重そうで、愚直にやるとTLE食らいそうな感じ。時間も残り少ないのでパス。

F問題

F - Pond Skater

問題文をみただけで、BFSを使うやつやなー。ということで、BFSらしき実装をしてみましたが、すでに残り時間がほとんど無く、テストもできぬまま終了となりましたー。

今回の実績

Rated5回目にして、初のレート下げを経験してしまいました。

C問題でWAを繰り返したのがほんとに痛かった。

 

コンテスト実績

コンテスト実績

総括

今回はWAのペナルティーを多く喰らいすぎて、残念な結果になってしまいました。

 

2完、3完レベルだと、簡単な問題をどんだけ早く正確に解けるかという競争になりがちですね。次回からは提出前にできるだけテストしてから出すようにして、WAを喰らう回数を抑えるように心がけます。