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

irisruneです。前回扱った問題のアルゴリズム面についてもう少し解説したいと思います。 問題リンクと提出コードは前回記事を参照してください。 ami-atcoder.hatenablog.com 例えば以下のような入力について考えます。 6 0 1 1 2 2 3 すると、次のような木…

irisruneです。例によってコンテストには出られませんでした。 問題 atcoder.jp アルゴリズムは素直ですが、解法のイメージができるかが問われる問題だと思います。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextS…

irisruneです。GoのLanguage Owner入りをのんびり目指していきたいです。 問題 atcoder.jp 除外して良いケースをどのように導き出すかという問題です。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextStr() string …

irisruneです。今週のコンテストは1完でまた水パフォでした。 問題 atcoder.jp 見かけがかなりわかりにくく、アルゴリズムが組みにくい問題だと思います。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextStr() stri…

irisruneです。気づけばもう11月となり、今年の終わりも近づいてきました。 問題 atcoder.jp パズル要素が強めのグラフ問題です。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextStr() string { sc.Scan() return s…

irisruneです。AtCoderの数学問題は注目を集めやすい印象です。 問題 atcoder.jp 大きなポイントが2つあり、どちらが欠けても上手くいかない問題です。 package main import ( "bufio" "fmt" "os" "sort" "strconv" ) var sc *bufio.Scanner func nextStr() …

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 難しいアルゴリズムが求められそうですが、実装力があれば解けてしまう問題です。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner fu…

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

irisruneです。AtCoder用の手元環境をもう少し整備したい思いです。 問題 atcoder.jp 700点の割には単純な問題だと思います。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextStr() string { sc.Scan() return sc.Te…

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

irisruneです。今週は台風の影響で公式コンテストが開催されないそうです。 問題 atcoder.jp どのような場合に条件を満たす分割が可能か、どのようにして分割の最大数を求めるかがポイントになります。 package main import ( "bufio" "fmt" "os" "strconv" …

irisruneです。流石に残暑も落ち着いてきた感じです。 問題 atcoder.jp 単純に見えて意外と考えることが多い問題です。 package main import ( "bufio" "fmt" "os" "strconv" "strings" ) var sc *bufio.Scanner func nextStr() string { sc.Scan() return s…

irisruneです。少し時間が取れなかったので月曜から過去問です。 問題 atcoder.jp 最小全域木を生成するアルゴリズムに貪欲法の要素を加えた感じになります。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextStr() s…

irisruneです。解説ACですが記事にすることはできそうでした。 問題 atcoder.jp これも一つのbitDPではありそうですが、特殊なケースになると思います。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextStr() string…

irisruneです。ABC-F問題が自力で解けたのはこれで2度目です。 問題 atcoder.jp グラフ理論です。何を求めればよいかが把握できるかどうかの問題だと思います。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextStr()…

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

irisruneです。1300点問題が解けたのは嬉しいです。 問題 atcoder.jp 得点が高いですが、アルゴリズムや実装の難しさよりも数学パズル寄りの問題だとは思います。 package main import ( "bufio" "fmt" "os" "sort" "strconv" ) var sc *bufio.Scanner func …

irisruneです。やはりAGCはB問題が安定しないと手が出し辛いです。 問題 atcoder.jp いつものAGC-Aらしく数学パズル的な問題です。嘘解法ではないはずですが実行時間1978msでした。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Sca…

irisruneです。実行時間1945msはかなり攻めた嘘解法だと思いました。 問題 atcoder.jp 一見愚直に解けそうに見えますが工夫が必要な問題です。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextStr() string { sc.Sca…

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です。台風の影響により、今週は火・水・金の投稿となります。 問題 https://atcoder.jp/contests/abc140/tasks/abc140_c からを逆算するにはどうすればいいかという問題です。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio…

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 func …

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

irisruneです。先週のコンテストはC問題もD問題も難しかったので過去問（リベンジ）回です。 問題 atcoder.jp 累積GCDなるフレーズが一時トレンド入りしたりしました。累積和と微妙に扱いが異なる点に注意が必要です。 package main import ( "bufio" "fmt" …