0.はじめに
最近デイリーコンテストでの練習時間をとれていない事に
不安を覚えつつ参加。
てこずりながらもDまで解けましたが、E以上は
解けず及第点といった結果でした。
レートは+5と微増で900台はキープできています。
1.A - Print 341
最初に"1"を格納したリストansを用意。
そのリストに、N回"01"を追加し
最後にansを結合した文字列を表示して終了
https://atcoder.jp/contests/abc341/submissions/50333119
2.B - Foreign Exchange
問題文を読むと両替する順番とか一部両替で得するケースが
あるかとか考えてしまいそうな気がしましたが、結局
1つ目の国から順番にすべて両替していくだけでした。
【実装】
・変数ansを0で初期化
・N-1回以下繰り返し
・S,Tをインプット
・両替単位p(現在のi国のコインをもとに
・何セットi+1国のコインが得られるかの数)を求める
・p=(ans+A[i])//S
・ansにp*Tをセット
・最後にans+A[N-1]を出力して終了
https://atcoder.jp/contests/abc341/submissions/50339276
3.C - Takahashi Gets Lost
なんとなく飛ばしてしまいたくなる面倒そうな2次元表
問題でしたが、まぁ、D以降も簡単そうではなかったので
取り掛かりました。
制約から、500×500×500が最大かなーとおもいつつ、陸地スタート
の場合だけ、3つ目の500がかかると思えばいけそうかなと
とりあえず単純に実装。
実行時間2974msと奇跡的にぎりぎりでACを頂けました・・・。
TLEするようなら、上下左右の移動範囲をもとにスタート
地点を狭めることも考えていましたが、そこまでしないで
済みました。
【考え方】
・MAP情報を表に格納
・MAPを順にみていき、”.”の時移動チェック関数を実行
・移動関数チェックの結果を集計し、最後に表示
[移動チェック関数(引数MAPのマス位置i,j)]
・移動情報もとにマスを動かしていき
海マスを通ったら0を返す。
海マスを通らず最後まで移動出来たら1を返す。
https://atcoder.jp/contests/abc341/submissions/50353788
4.D - Only one of two
まず、単純にNとMの小さい方から1ずつカウントアップしていき
NかMどちらかでしか割り切れない時にカウントアップ。
カウントがKになった数字を表示して終了としました。
もちろん例題3でTLEとなったので、まじめに考え始めました。
【考え方1(ちょっと間違ってる)】
・ある数Pが、問題の条件で言うX番目かの判断方法
LCをNとMの最小公倍数とした場合
X=(P//N)+(P//M)-((P//LC)×2)
→2分探索でPを探し、X=Kとなったら、Pを出力して終了
例題3を解いてみると考え方1でのPは、X番目からX+1番目の
間であり、ちょうど割り切れる数ではないことに気づきました。
ただ、Pが求まれば、答えは、N×(P//N)か、M×(P//M)になるので
(まぁ大きい方なんだと思いますが)
Pを2分探索で求めたあと、↑のどちらがピッタリなのかを求め
答えとしました。
【実装】
1.N,M,Kを入力
2.変数LCにNとMの最大公倍数をセット
3.Lに0、RにLC×Kをセット
以下繰り返し
-1.変数Midに(L+R)//2をセット
-2.変数cntに(Mid//N)+(Mid//M)-((Mid//LC)×2)
-3.cnt=Kの時
-1.AにN*(Mid//N)をセット
-2.BにM*(Mid//M)をセット
-3.(A//N)+(A//M)-((A//LC)*2)がKの時Aを出力して終了
-4.(A//N)+(A//M)-((A//LC)*2)がKではない時Bを出力して終了
-4.cnt>Kの時、RにMidをセット
-5.cnt<Kの時、LにMidをセット
https://atcoder.jp/contests/abc341/submissions/50380972
以上