AtCoder Beginner Contest 172
ABC172に参加しました。
Cをめちゃくちゃにバグらせた結果、解けたはずのDも落としたのでかなり苦い回になりました。Bまではそれなりに早く解けたので大丈夫まだ焦るような時間じゃないと言い聞かせています。
Tasks - AtCoder Beginner Contest 172
All Submissions - AtCoder Beginner Contest 172
A-Calc
計算するだけですね…。
B-Minor Change
SとTを前から見比べて、違う文字になっていればカウントしていきます。
C-Tsundoku
Cは解けるだろうと高をくくっていたので、積読か～～あるあるwwwとか思いながら実装し始めたところ完全に終わってしまいました。
まず机Aの本を順番にK分になるまで読んでいき、その後一冊ずつ読む数を減らしていって、都度机Bから読めるだけ読んでいき、カウントを更新するという方針で実装しようとしました。結局コンテスト後にもこの方針ではAC出来ていません…。どこが間違っているのかわかりませんが、少し時間を空けてリトライしようと思います。1冊も読めない時の添え字の扱いとか多分そういうことだと思うのですが…。
せめて解説ACはしておきたいと思い、コンテスト後に解説PDFを見ながらACしました。X冊目まで読むのにかかる合計の時間を机ごとに前計算しておき、しゃくとり法のイメージで実装するとすんなりACできたので、バグらせにくい方針で解き始められるのは大切だなあと改めて実感しました(コンテスト二回ぶりN回目)。
D-Sum of Divisors
コンテスト中ほとんど考えなかったのがもったいなかったですね。
コンテスト後にエラトステネスの篩の要領で、実装しACしました。
あらかじめN+1個の配列を用意し、2<=i<=Nの範囲で、各iの倍数に1ずつ足していくことでN+1個分のそれぞれの約数の個数をカウントすることができます。C++であれば1.4秒くらいでできるようです。
頑張ればできたんじゃないかという気はしますが、まぁたどり着くこともできなかったので言っても仕方ないですね。
今回は以上です。
Eも解説見ながらならできるかもしれないので考えておきたいです。
AtCoder Beginner Contest 171
ABC171に参加しました。
一時間ほどで5完出来たので、1WAと難易度を差し引いても悪くはなかったのではないでしょうか。茶diffで詰まることはなくなってきたので嬉しいですね。
Tasks - AtCoder Beginner Contest 171
All Submissions - AtCoder Beginner Contest 171
A-alphabet
αから'a'を引いて非負になればαは小文字ということになります。
文字コードが順に、...A~Z,...........a~z........というように並んでいるからです。
(自分は覚えていないので適当にテストしました)
B-Mix Juice
Pを配列で受け取って、sortし、小さいほうから順にK個足して出力します。
C-One Quadrillion and One Dalmatians
これはめんどくさかったです。
命名ルールを見ていくと、a~zまで順に使っていき、zまでで1サイクルになっているのが分かります。a~zまでの26文字で繰り上がりの計算をしていく感じかなあということでzzにあたる702やzzzにあたる18278を26で割ってみました。702/26=27,18278/26=703というようになるので、これはaaaやaaaaの番号になります。普通に数を数えるときは10で割って繰り上がりを考えるので、同じようにすればいいと考え、26で割った余りがa~zのどこに対応するかを試してみました。その過程で混乱して1WAを出しましたが、すぐに修正できたので良かったということにしておきます。
解いている間は26進数の問題だというようなことは意識していませんでした。次からはもっとすばやく解けると思います。
D-Replacing
各要素を大きさごとに一括で扱っており、最後に足し合わせることになります。なので、ある数がいくつ存在するかだけが分かっていればいいことになります。mapである数がいくつ存在するかを管理すれば簡単に一回の操作を行うことができるので、すぐに解くことが出来ました。
E-Red Scarf
xorには苦手意識があったのですが、問題文を見ながらいくつか試してみると解けてしまいました。
ひとまず1と2のXORを考えると、これは3になります。どうように、3と1のXORは2、3と2のXORは1です。XORの順番は入れ替えても問題がなく、同じ数が偶数回XORされるとどのような順番であっても0になるということが分かります。この状態で、入力例1を見ると、4つの要素がそれぞれ三回ずつXORされていることに気が付きました。ここで、Nが奇数の場合もあると話は変わってきますが、偶数という制約があるので、全てのXORを取ると各すぬけくんに書き込まれた数をそれぞれ1回だけXORしたものが残ります。初めにこれを計算しておいて、その後順に各すぬけくんが計算したほかのすぬけくんたちのXORともう一度XORすることで、本猫(？)に書き込まれた数が分かります。
今回は以上です。
茶diffの取りこぼしがなくてよかったです。
AtCoder Beginner Contest 170
参加しました。
更新が遅れています…。記憶が色あせつつあるので、少し簡略化してでも三日以内には書きたいところですね。
A~Cの三完でした。Cまではそこそこ早く解けるようになってきたので、良くなってきてるよ～と自分に言い聞かせています。
Tasks - AtCoder Beginner Contest 170
All Submissions - AtCoder Beginner Contest 170
A-Five Variables
for文を5回まわして0を受け取ったらiを出力します。
B-Crane and Turtle
いわゆる鶴亀算ですね。
制約が緩いのですべて試しても鶴亀算を解いてもいいです。
C-Forbidden List
入力を配列で受け取ったら、まずsortをすることで、前から順にみていき、Xより大きい数字に到達した時点で出力を確定できます。
あるいはsetで受け取ることで、0～101までの全てについてpに含まれるかどうかを確認することで出力を確定することもできます。X=1で、1,2がpに含まれた場合出力は0になります。X=100も同様です。
D-Not Divisible
とりあえず提出してみる癖は本当にやめないといけないです。毎回言ってますが…。
愚直にやる以外にあまり思いつかなかったので、とりあえず高速にできないかなあと頑張っていたようです。しかしうまくいかずに失敗しました。
コンテスト後に解説などを見て、1からNまでの配列にフラグを立てることで数列を管理するようにしてACしました。
エラトステネスの篩のイメージで処理部分を書くとより高速化できるので復習しておきたいと思います。というか、ここできっちり復習していればABC172のDで泣きを見ずに済んだと思います…。
今回は以上です。そろそろ水色以上のdiffになっている問題で、手を付けていないものにもトライしていきたいです。
東京海上日動プログラミングコンテスト2020
東京海上日動プログラミングコンテストに参加しました。
先週のことのはずなのに遠い昔のことのように感じます。
B問題で絶対値のつけ忘れで1WAはもったいなかったですね。
Tasks - Tokio Marine & Nichido Fire Insurance Programming Contest 2020
All Submissions - Tokio Marine & Nichido Fire Insurance Programming Contest 2020
A-Nickname
連続する3文字ならどこでもいいので、先頭の3文字をfor文で取り出しました。
B-Tag
一読した直後は子供がそれぞれ一秒あたりちょうど同じ距離しか進めないのかと思ってしまいました。なので最適に動いたら絶対に捕まらないのでは？となりました。
もちろんそんなわけはないので、二人の時速差とスタート時の距離を求めて割ることで時間内に捕まえられるかが分かります。スタート時の距離を求める際に絶対値をつけ忘れてWAを出しました。もったいないですね。
C-Lamps
読んでもあまりよくわからなかったので、サンプルを見ながら適当にいくつか試しました。一回目の操作以外は真ん中から順に増えていって最後に端の電球の強さがNになって、以降変化がなくなるということが分かりました。また、だいたいlogNより少し大きいくらいですべての電球の強さがNになるということもわかりました。これらは左右均等に光が届く関係上真ん中あたりは両端からの光が比較的早く届くようになるのに対し、両端に反対の端の方からの光が届くようになるのは当然最後になるからです。一回操作するごとに各電球の強さがだいたい2倍弱くらいになっていきます。
K回、それぞれの電球が届く範囲のすべての電球に順に加算していくととても間に合わないので、一つ前の操作から新しく届くようになった電球にのみ加算処理を行えばいい感じになったりしないかなと考えました。結局TLEもWAもとれずに時間切れになりました。途中で、この方針のまま続けても解ける見込みはないとわかっても、とりあえずWAだけでも取りたいとこだわってしまうのが本当によくないです。
累積和については知ってはいたのですが、解説を見るまでは少しも頭に浮かびませんでした。一応累積和で解けるということを理解した状態で今日解いてみたところすぐに解けてよかったです。
D以降はまだしばらくは手が出なさそうでした。
以上です。
NOMURA プログラミングコンテスト2020
NOMURAプログラミングコンテスト2020に参加しました。
ABC169と順番が前後しましたが、このコンテストではそれなりに結果がよかったので後回しになりました。
ABCの三完でした。Dはコンテスト中にはどうしていいのか分からずに諦めましたが、今日明日中には解説を見てACしておきたいです。
NOMURA Programming Competition 2020 - AtCoder
All Submissions - NOMURA Programming Competition 2020
A-Study Scheduling
ABCよりかはさすがに難しいですね。制約があるので、寝る時刻から起きる時刻を引いて、さらに勉強時間を引いて出力します。
たったそれだけのはずなんですが、コードを書くのに手間取って出遅れてしまいました。
B-Postdocs
一見するとDの前にはPを置いた方がいいような気がしますが、よく考えてみると？を全てDにしたものでも博士・PD指数を最大化できます。具体的には、？Dとなっていたときは、？がPでもDでも指数は2になりますが、？Pとなっていたときは、？がDのときのみ指数が1になります。最大のものを1つ求めるだけなので、全ての？をDに置き換えて出力します。
C-Folia
グラフの問題は正直得意ではないと思っていたのですが、D以降も軽く目を通してみてCが一番解けそうだったので考えてみることにしました。
パッと見てすぐに分からない時は、具体的な数字を用意したりサンプルの数字を使ったりして実際に書いてみることにしています。今回は二分木ということなので、各頂点はそれぞれ子を0個1個2個のいずれかの数だけ持つことができます。子の数が0個の頂点(葉)の数は各深さですでに決められています。なので、次の深さに子を持てる数は、頂点から葉を引いたものになります。頂点数を最大化したいので、葉以外の頂点はそれぞれ2個の子を持つようにできれば答えになると考えてグラフを書いてみました。すぐにこの方法では深さNのところで葉の数が入力を超えることが分かりました。グラフを眺めていると、当たり前のことなのですが各頂点が子を辿ってグラフの下にどんどん降りていくと最終的に葉にたどり着かないといけない(子がある場合はまだ下に行くことになる)、ということが分かります。つまり、子の数によってその元の頂点(親？)の数がある程度制限されます。深さNには葉しか存在しないため(子を持つ場合は深さがN+1になるから)、深さNの頂点の数は確定しています。深さNの頂点の数が決まっているので、深さN-1の頂点の数もある程度範囲を絞ることができます。具体的には((深さNの頂点の数+1)/2+深さN-1の葉の数)から(深さNの頂点の数+深さN-1の葉の数)までです。この要領で、グラフの下から順に各深さで取ることのできる頂点の数の範囲が決まっていきます。これをあらかじめ求めておけば、深さ0では頂点は一つしかなく、1つ下の深さに行くときには子は2つまでしか持てないので(二分木のなので)、上から順に先に求めた範囲の中で最大になるように頂点を取っていくことで、頂点数の最大値を求めることができます。
上記のコードを何とか書き上げて終了10分前に何とかACできました。
Cまで何とか解くことができてよかったです。少しずつできることが増えていると実感すると嬉しいです。
AtcCoder Beginner Contest 169
ABC169に参加しました。
ACDの三完でした。自分の弱いところがもろに出たという感じで、大変勉強になりました。しかもCはコンテスト後に追加されたアフターケースでしっかりWAになるコードだったので実質二完というありさまでした。
AtCoder Beginner Contest 169 - AtCoder
All Submissions - AtCoder Beginner Contest 169
A-Multiplication1
かけて出力します。
B-Multiplication2
地獄を見ました。解けなかったのはもう最悪仕方ないとして、特に原因もわかっていないまま適当にいじったコードをデバッグ代わりに提出するのは止めないといけないです。普段から考察を詰め切らないで出すことがあるので、そこから改善していきたいです。
散々ほかの人が解説してくれていますが、自分で試したことを一応書いておきます。
元の数Aと、これから掛け合わせたい数Xがあったとして、A*Xをした時点でオーバーフローしているかが判定できればいいと考えたので、A*X/X＝Aにならなかったときは-1を出力するようにしてみました。コンテスト中は完全に混乱していたのでこのシンプルなコードすら正確に書けていませんでした。ただ、コンテストが終わってから書き直したところ、テストケースのhand_01.txtのみWAになっており、原因が分かりません。4294967296を二つ受け取り、かけて10の18乗以上になるので-1を出力するはずなのですが、二つ目の4294967296をかけるとオーバーフローするという判定が機能していないようです。頭の片隅に残しておいていずれ解決したいと思います。
コンテスト後に出したACコードは、これまでの積で10の18乗を割った商が、次にかける数より小さい場合には-1、さらに実際にかけて10の18乗よりも大きければ-1を出力するようにしました。こうすることで、64bit整数は9*10の18乗程度なので、10の18乗を超えてもオーバーフローしないようにして大小比較できるようにしました。
C-Multiplication3
シンプルにlong double型で処理したところあっさりACしたのでコンテスト中は何も考えませんでした。コンテスト後に解説などを見ながら挙動を確認したところ、double型で受け取ったときは990と出力されていた数値型をlong long型にキャストして出力してみたところ989と出力されたときは心底感心しました。また、同じdouble型の変数に入力と同じ数を直に代入するとキャストしても990のままでした。これはよくわかりませんでしたが、入力の時に誤差が発生している、というのをツイッターで見たので何か違うのかもしれません。
最終的には0.001を足してから100倍してキャストしたものを掛け算して、最後に100で割ることでACしました。
少数以下は出力と内部で保持している2進数の数が微小に違うこと、特にキャストする際は切り捨てに気を付けないといけないことは理解したつもりですが、また誤差に気を付けないといけない問題が出たときにはかなり慎重に調べてから解くことになりそうです。
D-Div Game
とりあえず解くことが出来たので、今回のコンテストの救世主になりました。
素数の指数表現ということを見て、素因数分解すればいいということがすぐに分かりました。ここまではよかったのですが、素因数分解をするコードを空で書くことにかなり手間取り、目も当てられない汚いコードをなんとか書いてACしました。ここも冷静に素因数分解のアルゴリズムについて解説したブログなりを参照すればよかったものの、もう少しでできそう、という気持ちで書き始めたコードにこだわって時間を浪費してしまいました。そもそも練習量が十分であれば素因数分解に気が付いたのはすぐだったのであっさり解けたことと思います。次はすぐに書けるようにしておきたいです。ライブラリの整備については少し考えたのですが、空で書くことができるように練習する方が当面はプラスが大きいかなと思ったので見送ることにしました。
素因数分解ができたら、素数pの累乗数のうち、小さいほうからいくつ作ることができるかを数えていくことで答えにたどり着きました。
E-Count Median
問題文を見てすぐに方針が立ったので、時間さえあればここも解けていたと思います。めちゃくちゃもったいなかったです。
まず、中央値として考えられる最小値はXすべてがAのときで、最大値は同様にBの時です。いずれかのXを大きくしたのに中央値が小さくなったり、Xを小さくしたのに中央値が大きくなることはあり得ません。さらに、XがすべてAの状態から、Xを一つ選んで1だけ大きくする、という操作を考えました。この時、中央値はたかだか1(Nが奇数)か0.5(Nが偶数)しか変化しません。なので、この操作を繰り返すことで、中央値の最小値から最大値までのあいだの1(0.5)刻みのすべての値を取ることができます。
ここまではすぐに分かったので、大慌てでコードを書いて終了20秒前に提出したのですが、添え字やカウントの式などが雑でWAとなりました。コンテスト後、それらを修正した後にもう一度提出したところhandmade03のみWAになりました。Nが偶数の時、中央値をきっちり2で割って求めて最大値と最小値の差を取って2倍していたのですが、おそらくここで誤差が生じていたのかと思います。2で割らずにそのまま差を取って1を足して出力したところACとなりました。
今回は以上です。普段の適当さの悪いところが遺憾なく発揮されることとなりました。毎回以後気を付けなければ…というところが出てくるのでしっかり活かしたいと思います。
ABC168
AtCoder Beginner Contest 168に参加しました。
散々な出来だったのですが、まぁコドゲで気もそぞろだったしね～と自分に言い聞かせています。
恐怖のAB二完でした。
Tasks - AtCoder Beginner Contest 168
All Submissions - AtCoder Beginner Contest 168
A-Therefore
場合分けを書いていくのが面倒でした。素直にif文とorを使いましたが、配列を用意してforを回したほうが気持ち簡単だったかもしれません。
B-Triple Dots
空の文字列にSの長さとKのうち小さいほうの回数だけSを前から順に加えていきます。Sより短ければ最後に…をつけて出力します。
C-Colon
とんでもないことになりました。Water Bottleを思い出しながら解きました。まず座標を出そうかということになりました。合いません。二辺と挟角が分かるのでそういえば余弦定理も使えるなあということで余弦定理をググりC++のsin,cosのリファレンスを読み試しましたが合いません。コドゲのことが常に頭の片隅にあったので注意散漫のままイライラしていたら時間になりました。
復習の時にコードを見返すとどうも割合の概念をあまり理解できていないとしか思えませんでした。
D-Double Dots
コドゲでやったやつ！ということで普通にBFSを書いて、用意した配列に何回目の移動で訪れたのかをメモしていき、最後に出力するだけでした。
せめてCを飛ばしてDをやっておけばよかったです。
救いのない回になってしまいましたが仕方ないですね。
次に期待することにします。
