あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

競プロ

AtCoder 第一回日本最強プログラマー学生選手権-予選- B - Kleene Inversion (Go)

irisruneです。随分Go言語にもお世話になっているので競プロ以外でも何かしら形にしてみたい気分です。 問題 atcoder.jp 制約条件に注目すると解き方が見えるかもしれません。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner …

AtCoder 第一回日本最強プログラマー学生選手権-予選- A - Takahashi Calendar (Go)

irisruneです。残念なことに仮眠したらコンテスト時間に寝過ごしてしまったので不参加でした。 問題 atcoder.jp たまには簡単めの問題をということで。条件が少し複雑ですが愚直にやれば解けるはずです。 package main import ( "bufio" "fmt" "os" "strconv…

AtCoder AGC 037 A - Dividing a String (Go)

irisruneです。ふとデザインを変えたいと思いましたが、ある程度まとまった時間を取らないと難しいですね。 問題 atcoder.jp 最多の分割を行うための方針は結構単純です。実は嘘解法と化していたことに後で気付きました。 package main import ( "bufio" "fm…

AtCoder ABC 138 E - Strings of Impurity (Go)

irisruneです。久々に比較的易しめなE問題だった気はします。 問題 atcoder.jp 発想力が占める比重がかなり大きい気はします。 package main import ( "bufio" "fmt" "os" "sort" "strconv" ) var sc *bufio.Scanner func nextInt() int { sc.Scan() i, e :=…

AtCoder ABC 138 D - Ki (Go)

irisruneです。休暇を過ごした人もそうでない人もまた心機一転していきましょう。 問題 atcoder.jp 木構造に慣れていれば単純化しやすい問題ですが、計算量には気を付ける必要があります。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bu…

AtCoder ABC 137 C - Green Bin (Go)

irisruneです。前回のコンテストは色々あり2完で-91(1292→1201)と大変冷えました。 問題 atcoder.jp 解き方自体は発想さえできればといったところですが、言語のソート仕様によっては実装が面倒になります。 実はこの提出コードはAC時のものではありません…

AtCoder Tenka1 Programmer Contest C - Align (Go)

irisruneです。お盆休みのある人もいたり学生さんは夏休みだったりしますが、よい休暇を過ごせるといいですね。 問題 atcoder.jp なんとなくでも解法が見えそうな問題ですが、証明が難しかったり落とし穴があったりします。 package main import ( "bufio" "…

AtCoder ABC 136 E - Max GCD (Go)

irisruneです。問題の解説など試行錯誤していますが、アドバイスや感想などコメントを貰えると嬉しいです。 問題 atcoder.jp あることに気付かないとどうにも方針が立てられないので、かなりパズル要素が強い問題だと思います。 package main import ( "bufi…

AtCoder ABC 136 D - Gathering Children (Go)

irisruneです。日曜開催は予定を合わせるのが難しいです。 問題 atcoder.jp 大体こういう異様に大きな数字が出てきた時は剰余に注目すればよいですね。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextInt() int { s…

AtCoder AGC 002 B - Box and Ball (Go)

irisruneです。久々の過去問回です。 問題 atcoder.jp 突き詰めればただシミュレートするだけの問題で、操作によってどのような挙動を示すのかを把握できれば解くことができると思います。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bu…

AtCoder ABC 135 D - Digits Parade ※解説AC未遂 (Go)

irisruneです。今回は解説ACすらできていないという困った状況です。 問題 atcoder.jp 全探索は途方もない組み合わせ数になり、10進数に対する13で割った剰余なので右何桁かを見てある程度決まるということもないという、かなりアプローチに困る問題です。 p…

AtCoder ABC 135 C - City Savers (Go)

irisruneです。ABC135参加はしましたが…D問題以降が解けずNoSub撤退をすることになりました。 問題 atcoder.jp 逆から解く必要があるように見えましたが全くそんなことはなかった問題です。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *b…

AtCoder ABC 134 E - Sequence Decomposing (Python)

irisruneです。最近晴れることが多くなりましたが、週末を狙って台風が来るのは辛いですね。 問題 atcoder.jp どのようなアプローチで解けばよいかが思いつきにくい問題だと思います。 import sys import bisect import collections def input(): return sys…

AtCoder ABC 134 D - Preparing Boxes (Python)

irisruneです。とりあえずABC134のD,Eはどうにかなりました。 問題 atcoder.jp 計算量の見積りが大変難しい問題です。また、逆から解くというアプローチが求められます。 import sys def input(): return sys.stdin.readline().rstrip() def main(): n = int…

AtCoder AGC 036 A - Triangle (python)

irisruneです。Rustはきちんと勉強してから使わないと厳しい言語だと認識したので、しばらく温めることにします。 問題 atcoder.jp あまりにも数学要素が強い問題ですが、アルゴリズム面でも少々癖があります(というか癖を出してしまいました)。 import sy…

AtCoder AGC 035 A - XOR Circle ※正攻法 (Rust)

irisruneです。一応Rust第2回です。 問題 atcoder.jp 300点問題ですが、正攻法で解こうとすると考慮すべきケースを整理したり実装がやや面倒だったりと厄介な問題です。 use std::collections::HashMap; fn main() { input!{ n: usize, la: [usize; n] } let…

AtCoder AGC 035 C - Skolem XOR Tree (Rust)

irisruneです。Rust第一回ですが、余りにも茨の道すぎて早くも最終回が近い予感がしています。 前置き Rustは入力がかなり難解なので下記サイトよりマクロを拝借しております。中身はほとんど理解できていません。本ブログ上では記述を省略します。 qiita.co…

AtCoder ABC 133 E - Virus Tree 2

irisruneです。個人的に以前のABCの4完が最近のABCの5完に相当するように思えるのですが、誰か統計取ったりしているのでしょうか。 問題 atcoder.jp 500点問題の割にアルゴリズムも実装もかなり軽めで、発想系の問題だと思いました。 import sys import coll…

AtCoder ABC 133 D - Rain Flows into Dams

irisruneです。弊社でRustが布教されているので試していますが、気を付けなければいけないことが多い言語なのでなかなか大変ですね。 問題 atcoder.jp 単純な連立方程式を解くだけの問題ですが、規模が大きいので一工夫必要となります。 import sys import n…

AtCoder ABC 133 C - Remainder Minimization 2019

irisruneです。求められるレベルが上がっている感じがあるので競プロの勉強もしたいですが、他にも勉強するべきことがあるので大変ですね。 問題 atcoder.jp うっかりするとWAを出してしまうこともあるかと思いましたが…気のせいかもしれません。実装はB問題…

AtCoder ABC 133 B - Good Distance (Python)

irisruneです。しばらくコンテストは不参加が続きそうですが、今週はB~E問題まで扱う予定です。 問題 atcoder.jp 書いてあることを実装すれば解けますが、B問題にしては実装がやや重いです。 import sys import math import numpy as np def input(): retur…

AtCoder ABC 068 D - Decrease (Contestant ver.) (Python)

irisruneです。流石にABC132Fは難しすぎたので久々に過去問です。 問題 atcoder.jp 操作を行った結果として状態がどのように変わるか、どのような状態が停止状態となるかを把握することが重要です。 import sys import numpy as np def main(): k = int(inpu…

AtCoder ABC 132 E - Hopscotch Addict (Kotlin)

irisruneです。どうにか自力ACできたのでE問題も取り上げることにしました。 問題 atcoder.jp AtCoder上に類題がほぼないらしく、正解率が低めだったそうです。最短経路問題を理解しているならば、試行錯誤によって解法を思いつくのは割と難しくないかもしれ…

AtCoder ABC 132 D - Blue and Red Balls (Kotlin)

irisruneです。残念ながら今回のコンテストは不参加でした、問題を見るとD問題以降がかなり難しくなっているようですね。 問題 atcoder.jp 考察(+剰余周りの実装)面の問題ですが、ABCが新形式になって以降のD問題としてはかなり難しいと思います。ただしPy…

AtCoder ABC 131 E - Friendships

irisruneです。今週またABCがあるようなのでなるべく参加できるように調整したいですね。 問題 atcoder.jp 最短距離というワードがありますが、探索系(実装系)の問題ではなく考察系の問題なので気を付けましょう。 package main import ( "bufio" "fmt" "o…

AtCoder ABC 131 B - Bite Eating (Go)

irisruneです。ここ最近競技プログラミングに使う言語についてまた悩んでいるところです。 問題 atcoder.jp 実はD問題より解く時間がかかったので取り上げることにしました。絶対値の差ではなく差の絶対値なので誤読しないようにしましょう。 package main i…

AtCoder ABC 131 D - Megalomania (Go)

irisruneです。新形式になって以降C,D問題が簡単になったとは思っていましたが、今回はかなり極端だった気がします。 問題 atcoder.jp 解答者にとってはどちらかと言えばMegalomaniaよりParanoiaみたいな問題です。 package main import ( "bufio" "fmt" "os…

AtCoder ABC 131 C - Anti-Division (Go)

irisruneです。久々にコンテストに参加した結果、5完で1242→1292とレートが伸びました。 問題 atcoder.jp 典型テクニックの寄せ集めのような問題だと思います。 なお、コンテスト本番でPythonを使う度胸はなかったので久々にGo言語で書いております。 packag…

AtCoder ABC 130 D - Enough Array (Python)

irisruneです。AtCoderで言語アップデートがあるそうで、色々な言語が使いやすくなるといいですね。 問題 atcoder.jp 連続部分列とみると累積和を取りたくなりませんか?累積和を取った場合は二分探索が手っ取り早いと思います。 import sys import bisect i…

AtCoder diverta 2019 Programming Contest 2 C - Successive Subtraction

irisruneです。他言語に慣れているとpythonの変数名にキャメルケースを使おうとするたびに警告を出されるのはもやもやします。 atcoder.jp B問題より簡単という噂を聞きましたが全然そんなことはなかったです。見た目以上に考えることが多く、ACするのに5回…