htkb-proconの日記

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

AISing Programming Contest 2019

ooo-- 1607 -> 1604 反省しきり。 A - Bulletin Board AC: Submission #3983509 - AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019 縦と横それぞれいくらずらせるかを掛ければいい。 B - Contests AC: Submission #3984497 - …

Educational DP Contest S - Digit Sum 桁DP

めんどくさすぎるイメージを持っていた桁DP、久しぶりに遭遇して解いたら割とソラで書けたのはいいけどTLEで、考察したらそもそも無駄に配列の次元を深くしたりしなくていいんじゃないの??と思ったので書き残してみる。 桁DPの状態遷移はこのように上の桁…

AtCoder青になるまで使ったPythonパフォーマンス小ネタ

AtCoder青になったらなんか書こうと思っていて、12/22に無事青になれたのですが、よく考えたらあんま書くことないな……と思ってる間に年が開けてしまいました。知識披露でもサクセスストーリー的な話でも既に109+7人くらいいる青コーダー達が語り尽くしてしま…

Hello 2019

ooo----- 1466 -> 1510 A. Gennady and a Card Game AC: Submission #47904524 - Codeforces それぞれについて1文字目と2文字目に分けて比較しましょう。 B. Petr and a Combination Lock AC: Submission #47909911 - Codeforces N <= 15なので215=32768の全…

Good Bye 2018

ooo---- 1430 -> 1466 Codeforces久しぶりに出た。2018ラストなので。 A. New Year and the Christmas Ornament AC: Submission #47733927 - Codeforces あたまわるいのでこういう問題嫌いです。愚直に場合分けしたけどr, b-1, y-2の中で一番少ないものに引…

AtCoder Grand Contest 030

o--- 1600 -> 1607 A - Poisonous Cookies AC: Submission #3892026 - AtCoder Grand Contest 030 やるだけなんだけど解毒クッキーより毒クッキーが多い場合毒クッキーを食べる数は解毒+1になるとか、タイムアタックやってると足引っ掛けそうでおっかない問…

CADDi 2018

oox- 1560 -> 1600 C - Product and GCD AC: Submission #3840276 - CADDi 2018 ん〜これxのN乗がPを割り切るか√Pから2まで試してみればいいだけなんじゃないの?と思いそのまま書いたらTLE、何でTLEなのかすぐにピンと来ずpypyで投げ直してみようかと思った…

AtCoder Grand Contest 029

oox--- 1542 -> 1560 A - Irreversible operation AC: Submission #3794678 - AtCoder Grand Contest 029 完全にあさっての方向に突っ走ってしまい20分もかけてAC。AC時の順位が4桁で配点的にもう一問解ける保証もなかったしほんと涙目だった。BWBWBWのテス…

yukicoder No.751 Frac #2

No.751 Frac #2 - yukicoder 最初、問題の意図がつかめなかったが、括線の長さを見ると分子側は一番上から分母側は一番下から処理していくようだ。 分子側は 1 --- 2 ----- 3 ------- 4 の場合、(1/2)/3 = 1/6 → (1/6)/4 = 1/24のようにやり、分母側は 1 ---…

CODE THANKS FESTIVAL 2018 E - Union

E - Union 解説見てもDPの回し方にしばらく悩んだのでメモ。 dp[i][j] := 整数i-1まで余りなく処理したとき、iにj個持ち越した場合の数 って感じの流れは思いつけたんだけど、なーーーーんでか各iを1個残した場合と全部使い切って次に回す場合の場合分けって…

第5回 ドワンゴからの挑戦状 予選

oo--- 1540 -> 1542 A - Thumbnail AC: Submission #3652781 - Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選 解説では平均値と数列の各項にNをかけて整数での比較を勧めているが、そこまで頭が回らなかった。誤差でWA食らってたらなんで…

ディスカバリーチャンネル コードコンテスト2019 予選

ooo- A - チップ・ストーリー ~無色編~ AC: Submission #3645418 - DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 やるだけ。 B - チップ・ストーリー ~漆黒編~ AC: Submission #3646818 - DISCO presents ディスカバリーチャンネ…

CODE FESTIVAL 2018 Final (Parallel)

oxo------- A - 2540 AC: Submission #3611208 - CODE FESTIVAL 2018 Final (Parallel) すべての頂点で、接続されている辺のコスト同士を組み合わせて何個2540を作れるか。そしてそれは頂点ごとに辺のコストをソートしておき左右のポインタを真ん中へ寄せて…

ARC014 C - 魂の還る場所

C - 魂の還る場所 Submission #3626930 - AtCoder Regular Contest 014 解法が思い浮かばなくて試しにビームサーチ解投げてみたら通ってしまって笑ったのでメモ。ただゲームのルール上筒の中に玉がたくさん詰まった状態で終盤から挽回するのは無理なので、不…

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個あるので、これを好きなように混ぜてなるべく安く指定の比率を実現したいという問題で、制約も…