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

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 律儀にシミュレートしようとすると難しく思える問題ですが、解き方は意外と単純です。 package main import ( "bufio" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextInt…

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" "fmt" "os" "strconv" ) var sc *bufio.Scanner func nextInt() int { s…

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 sys import n…

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

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です。この土日のコンテストは不参加だったのもあり記事にするのは間に合いませんでした。 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 …

irisruneです。GW中はJuliaについて色々調べたりしていました、その辺の諸々は雑記に。 atcoder.jp 少し忙しいので解説が難しくない問題を選びました。GW前の記事とジャンルが一緒ですね。 package main import ( "fmt" ) const INF = 1000000000 func minIn…

irisruneです。回転寿司なんかに行くとできるだけ多くの種類のネタを食べる派です。 atcoder.jp 多分実装が難しい部類の問題じゃないでしょうか。結構ゴリゴリ書いたので長めです。 package main import ( "fmt" "sort" ) type susi struct { t int d int } …

irisruneです。新しめのABC-D問題を扱うのは久々ですね。 atcoder.jp 解説だけでも3種類の解き方が示されていますが、 今回用いた解き方は累積和を用いたしゃくとり法に少し近い解き方です。見た瞬間はUnion-Find木使うのかと思いました。 package main impo…

irisruneです。ゲーム理論系の問題で500点ばかり見るのは気のせいでしょうか。 今回は解いた問題の実装が軽かったのと、似たような問題が過去にあったので久々の2本立てです。 ABC 085-D ABS atcoder.jp あまり入出力例が多いとボロが出るから例3,4は自明な…

irisruneです。この問題を選んだ理由は最近発売された某ゲームを連想したからです。 今回は構造体の配列が作れなくてGoを断念したのでKotlinで解いていましたが、 後でGoで解き直したので両方のコードを掲載します。 atcoder.jp 初見だとそれほど難しくなさ…

irisruneです。500点問題が厳しいので予定を変更して先週扱わなかったこの問題を。コードがかなり長いです。 atcoder.jp Twitterで検索をしたら糸口というかほぼ答えが見つかったので解いてみました。 …が方針変更が激しくて変数名とかがめちゃくちゃになっ…

irisruneです。一昨日のAGCは所用で参加できなかったので今日も過去問になります。 前回と同様、今回もC++での提出コードです。 https://atcoder.jp/contests/abc119/tasks/abc119_d この問題のポイントは に（東西それぞれで）最寄りの神社と寺を高速で求め…