htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Beginner Contest 100

B - Ringo's Favorite Numbers Submission #2676172 - AtCoder Beginner Contest 100 N=100のケースだけ注意。200点のくせに問題文斜め読みしてたら足引っ掛けそうな罠が。 C - *3 or /2 Submission #2677755 - AtCoder Beginner Contest 100 ある数を3倍す…

AtCoder Beginner Contest 099

B - Stone Monument https://beta.atcoder.jp/contests/abc099/submissions/2645570 問題文が!よくわからない!!塔の上には積もらず、上の方を覆い隠すようにだけ積もったってこと??よくわからないのでサンプルから雰囲気で和の公式でアレした。わたしに…

AOJ 0585 Nearest Two Points 最近点対問題

距離が最小の2点 | Aizu Online Judge この問題、適当に証明もせずなんとなく思いつきでコードを書いて提出したら通ってしまって、CPU時間のランキングを見てみるとC++やJavaのコードに囲まれていておっかしいなーと思ってたんだけど、ちょっと考えてみたら…

yukicoder No.407 鴨等素数間隔列の数え上げ

No.407 鴨等素数間隔列の数え上げ 素数の列挙を行う必要のある問題。素数列挙といえばエラトステネスのふるいで、これを普通に組んでTLEになった問題に今まで当たったことはなかったけどこの問題ではだめだった。 定数倍に気を遣ったエラトステネスのふるい…

AtCoder Beginner Contest 097

B - Exponential Submission #2496124 - AtCoder Beginner Contest 097 どうやって求めるかぱっと出てこなかったのでめっちゃループを回した。 for i in Xから1まで for j in ルートiから1まで for k in 1から9まで i == jのk乗だったら答えはi みたいな。k…

AtCoder Beginner Contest 096

C - Grid Repainting 2 Submission #2461512 - AtCoder Beginner Contest 096 番兵で周りを囲む、ループ回しながら隣のマスを調べるなど二次元座標探索の基本をやる問題。制約がゆるいので定数倍を気にする必要は無かったが、pythonのindexingはかなり遅いた…

AtCoder Beginner Contest 094

B - Toll Gates Submission #2352431 - AtCoder Beginner Contest 094 問題文読むのがなんか辛かった……。解いてる時は普通にループ回す泥臭い方法しか思いつかなかったけど、制約厳しくてもAを二分探索して終わりじゃないか。制約変えてCで出てたらハマりそ…

AtCoder Beginner Contest 092

D - Grid Components Submission #2260916 - AtCoder Beginner Contest 092 最初は面積がA+B以上になる長方形の格子を作って、格子のマス目を塗りつぶすことで連結成分を減らしていき目的の状態を作れないかなんて考えたがどう考えても面倒で、よくよく制約…

AtCoder Beginner Contest 090

去年末あたりから色々忙しいのと自信をなくしてた風味でしばらくやってませんでしたが、少しずつABCからやり直していく所存です(こっそりと C - Flip,Flip, and Flip...... Submission #2186244 - AtCoder Beginner Contest 090 手書きシミュレーションがめ…

AtCoder Regular Contest 083 参戦記

o--- 1422 -> 1408 C - Sugar Water 結果:AC(2WA) Submission #1598690 - AtCoder Regular Contest 083 コンテストではDPで解いたのだけど、DPを思いついてコードを書き始めるまでにすごい時間がかかってしまったのでダメ。最大F+1までのサイズのdp配列を用…

AtCoder Grand Contest 019 参戦記

oo---- 1428 -> 1425 (-3) A - Ice Tea Store 結果:AC Submission #1539280 - AtCoder Grand Contest 019 | AtCoder アイスティーは1/4リットル・1/2リットル・1リットル・2リットルの4種類の値段が付いているが、購入するアイスティーはN(整数)リットル…

AtCoder Regular Contest 079 参戦記

o-o- 1355 -> 1395 (+40) C - Cat Snuke and a Voyage 結果:AC Submission #1463078 - AtCoder Regular Contest 079 | AtCoder 用意してあったダイクストラをそのままベタッと貼りました。完。 pythonのheapqは二分ヒープのようなのでこれを使ったダイクス…

AtCoder Grand Contest 018 参戦記

o---- 1358 -> 1355 (-3) A - Getting Difference 結果:AC(1WA) Submission #1446363 - AtCoder Grand Contest 018 | AtCoder 問題文一通り読んでどういう問題なのか全く把握できなかったので辛かった。 入力例 2 3 5 6 9 3 出力例 2 IMPOSSIBLE どれだけ操…

AtCoder Regular Contest 078 参戦記

oo-- 1337 -> 1358 (+21) C - Splitting Pile 結果:AC Submission #1422177 - AtCoder Regular Contest 078 | AtCoder すぬけくんが先頭から連続した数列を取り、アライさんが残りを取ることになるので、snuke = 0,arai = sum(a)から始めて、数列から数字を…

AtCoder Grand Contest 016 参戦記

o---- 1293 -> 1300 (+7) A - Shrinking 結果:AC Submission #1360112 - AtCoder Grand Contest 016 | AtCoder うだうだ考えないでシミュレーションしましょう。高々100文字しかないのだしどう見ても計算量的に間に合うのに無い頭で考えようとするから早解…

ABC054-D DP

D - Mixing Experiment DPやるだけの400点問題なんだけど今更こんなのでハマってしまったので忘れないように記す。 2種類の物質がa:bで混じっているc円の薬がN個あるので、これを好きなように混ぜてなるべく安く指定の比率を実現したいという問題で、制約も…

AtCoder Beginner Contest 064 参戦記

oooo unrated A - RGB Cards 結果:AC http://abc064.contest.atcoder.jp/submissions/1339289 (100*r+10*b+g) % 4 == 0で判定。 B - Traveling AtCoDeer Problem 結果:AC http://abc064.contest.atcoder.jp/submissions/1339821 max(a) - min(a)を出力。 C…

ABC041-D bitDP

D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder この問題、解説見てもACコード見てもプロい人のブログとか見ても、お願いだから日本語書いて?って感じで困っていたのだけど、このブログの 感覚的には空集合の場合の数から全集合の場合の数へ、集合の…

AtCoder Regular Contest 075 参戦記

o— 1281 -> 1293 C: Bugged - AtCoder Regular Contest 075 | AtCoder 結果:AC Submission #1323396 - AtCoder Regular Contest 075 | AtCoder 数列をソートして合計を取り10の倍数だったら数列の中の10の倍数ではない最小の数字を捨てて合計をチェック……を…

Codeforces Round #416 (Div. 2) B 平方分割

B. Vladik and Complicated Book 適当訳:数列と3つの数字からなるクエリl, r, xが与えられるので、元の数列とそれのl番目からr番目までを昇順にソートした数列を比べて、x番目の数字が変わってないか調べてNE! 数列 5 4 3 2 1 クエリ 1 3 1 → 変換済み数列…

AtCoder Grand Contest 015 参戦記

oo—- 1305 -> 1281 A: A+...+B Problem - AtCoder Grand Contest 015 | AtCoder 結果:AC(3WA) Submission #1312681 - AtCoder Grand Contest 015 | AtCoder 0通り・1通りなどのケースを場合分けしたら、数列に含まれる最小の数字と最大の数字は確定している…

AtCoder Regular Contest 074 参戦記

ox-- 1295 -> 1305 C: Chocolate Bar - AtCoder Regular Contest 074 | AtCoder 結果:AC Submission #1297073 - AtCoder Regular Contest 074 | AtCoder 先にHとWのどちらかが3で割り切れないか確認して(割り切れたら答えは0確定)、 Wが2で割り切れるなら…

Typical Contest 001-B, ARC032-B, ARC037-B UnionFind

B: Union Find - AtCoder Typical Contest 001 | AtCoder Submission #1294904 - AtCoder Typical Contest 001 | AtCoder UnionFindの実装が面倒そうで避けてたので練習として。データ構造としては配列一本持つだけでどのように操作するか/比較するかだった…

ABC012-D 最短経路問題

D - バスと避けられない運命 最短経路問題の練習をいくつかこなしていたら、ダイクストラを真っ当に実装したはずなのにめっちゃTLEが出るこの問題に遭遇。おかしいと思って解説を読むと、 •注意点 – 遅い言語では通りません! • Perl, Ruby, Pythonなど • 計…

AtCoder Beginner Contest 061 参戦記

ooox unrated A - Between Two Integers 結果:AC(2WA) Submission #1278622 - AtCoder Beginner Contest 061 | AtCoder 早く提出しようと提出フォームに直接書いたらひどいことに…… B - Counting Roads 結果:AC Submission #1279301 - AtCoder Beginner Co…

AtCoder Grand Contest 014 参戦記

oox--- 1242->1295 A - Cookie Exchanges 結果:AC(2WA) Submission #1263025 - AtCoder Grand Contest 014 | AtCoder 問題文の通りシミュレーションするだけ。奇数判定を最初に行うのを忘れてWAした。 B - Unplanned Queries 結果:AC Submission #1263649 …