irisruneです。最近あまりAtCoderに時間を割けていません。 問題 atcoder.jp 3つ目までの条件を満たしつつ4つ目の条件を満たすためにはどうすればよいか考える問題です。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func …

irisruneです。コンテストはE問題の解法がどうにも思いつきませんでしたが、水パフォは出ました。 問題 atcoder.jp 直球の数学問題ですが、D問題だけあって割と面倒な問題です。 package main import ( "bufio" "fmt" "math" "os" "strconv" ) var sc *bufio…

irisruneです。最近台風の接近が多く関東の天気は荒れがちですね。 問題 atcoder.jp 本当に全探索すると間に合わないので少しだけ工夫する問題です。 package main import ( "bufio" "fmt" "os" "sort" "strconv" ) var sc *bufio.Scanner func nextStr() st…

irisruneです。コンテストは当日になってうっかり存在を忘れてしまいました。 問題 atcoder.jp 3重ループは通りませんが2重ループなら通る制約設定が重要です。 package main import ( "bufio" "fmt" "os" "sort" "strconv" ) var sc *bufio.Scanner func ne…

irisruneです。先週はコンテストがなかったので今週は過去問を扱います。 問題 atcoder.jp 一見関係のないように見える要素も実際は必要になってくる問題です。 package main import ( "bufio" "fmt" "os" "sort" "strconv" ) var sc *bufio.Scanner func ne…

irisruneです。もう9月も終わりですが、残暑が続きますね。 問題 atcoder.jp アルゴリズムは単純なので難易度は比較的低いですが、素因数分解が必要なため割と面倒な問題です。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner…

irisruneです。D問題が大体安定して解けるようになっている辺り成長を感じますね。 問題 atcoder.jp Go言語にとってソート以上の鬼門と言えるであろうヒープを使う問題です。 package main import ( "bufio" "container/heap" "fmt" "os" "strconv" ) var sc…

irisruneです。今回は部分点込みの解説になるのでコードの分量が多めなのと、式を使った解説が多くなっています。 問題 atcoder.jp 部分点解法は典型的な…？DP問題、満点解法はその発展となっています。 部分点解法（400点） package main import ( "bufio" …

irisruneです。青パフォを出すのはなかなか難しいですね。 問題 atcoder.jp 律儀にシミュレートしようとすると難しく思える問題ですが、解き方は意外と単純です。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextInt…

irisruneです。ABC-F問題の壁は厚いですね。 問題 atcoder.jp 順列をどのように構築すればよいかがわかれば、順列が存在し得るかどうかも自然とわかります。あるいは小規模なケースで試してみるのもよさそうです。 package main import ( "bufio" "fmt" "os"…

irisruneです。暑さも多少和らいで雨も収まり過ごしやすくなったように思います。 問題 atcoder.jp 理論立てて考えないと、あまりに単純な解法すぎて戸惑うかもしれません。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner fu…

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

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

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

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

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

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

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

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

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

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

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

irisruneです。C問題ではテストケースでトラブルがありましたが、D問題ではPythonの実行時間で少し騒ぎになっていたようですね。 問題 atcoder.jp 公式解説と少しアルゴリズムが違いますが大体同じ解き方です。具体的には、連続する障害物のないマスの数を走…

irisruneです。Numpyを有効に使って計算時間を短くしたかったのですが、なかなか難しいですね。 問題 atcoder.jp 公式解説でも解法が複数説明されていますが、どう解くとしても手法に工夫が必要でかなり難しいです。AtCoder ProblemsのDifficulty684しかない…

irisruneです。Pythonを勉強し始めたので解ける問題はPythonで解くことが多くなると思います。 atcoder.jp 一見難しそうで思いつけば簡単…と思わせて引っ掛けポイントがある、そんな問題だと思います。 import sys n, a, b, c, d = [int(x) for x in input()…

irisruneです。この土日のコンテストは不参加だったのもあり記事にするのは間に合いませんでした。 https://atcoder.jp/contests/abc128/tasks/abc128_d "D"equeueとかけてるからD問題なんですかね。B、Cが難しければDも難しいときました。効率の良い方法を…

irisruneです。今日は試しに2記事公開してみました。 atcoder.jp アルゴリズムの発想と計算量の抑え方の両面が重要となる問題だと思いました。半分嘘解法です。 package main import ( "bufio" "fmt" "os" "sort" "strconv" ) var sc *bufio.Scanner func ne…

irisruneです。今回のコンテストは3完で冷えましたが…Unratedでしたね。 どちらもコンテスト中には解けなかったので解説ACです（正確にはE問題の解説を読んでD問題も解きました）。 ABC 126 D - Even Relation atcoder.jp のダイクストラ法で解けるような最…

irisruneです。今回もJuliaで問題を解いてみました。おまけで以前Go言語で解いた問題も解き直して実行時間など比較しています。 ABC 104 C - All Green atcoder.jp 当時2完で冷えた回ですが、今見ても300点にしては難しいと思います。なお嘘解法でゴリ押しで…

irisruneです。久々にコンテストに参加したらUnratedになったなんとも言い難いお話。 C - AB Substrings atcoder.jp 全探索は（かかるため）できないとして、計算で求めるための場合分けが難しかったです。まずは失敗例を。 package main import "fmt" func …