回文数

07/15(月) 午後4時起床。今日は祝日である。 午後11時過ぎまで先週の週記を書いていた。うっかり週末をすべてなろうに捧げてしまったため全然出来上がっておらず、コンテスト部分が軒並み穴あきのまま投稿することになった。 午後11時半からはCF #958 div.2。 Dashboard - Codeforces Round 958 (Div. 2) - Codeforces Aはを個作るように分割していくのがよいと考えてシミュレーションした。最後の状態からマージで元に戻すことを考えれば、最適な操作方法を考えずとも直ちにが得られる。Bは連続するそれぞれに対して操作を行った後、全体を操作してが残…

第363回は回文回 atcoder.jp A - Piling Up B - Japanese Cursed Doll C - Avoid K Palindrome 2 D - Palindromic Number A - Piling Up リンク：A - Piling Up (atcoder.jp) 概要：レート100上がるごとに^の数が増えます。次に^が増えるのはレートがいくつ上がったタイミングか数えてね 現在のレートを100で割った余りを見ることで解答できます。 100から上記の余りを引いた数を出力します。 #ABC363 A - Piling UpR = int(input())pr…

↓問題のページ↓ D - Palindromic Number 小さい方から順番に回文数を列挙していき、\(N\)個以上に到達したらそこで打ち切って\(N\)番目を出力・・・としたいところだが、制約を確認すると\(N \le 10^{18}\)であり、最大値が大きすぎるためこの方針ではTLEする。というわけで、まずは長さが\(L\)の回文数がいくつあるのかを考える。 evima氏の動画 でも言及されている通り、回文というのは前半のみを指定すれば後半も自動的に定まるため、前半部分が何通り存在するのかを調べることになる（以下、長さが\(L\)の回文数が\(c_L\)個存在し、各\(d_i\)を1桁…

https://atcoder.jp/contests/abc363/tasks/abc363_d桁数を指定すれば、その中で何番目の回文数は何かわかります。 オーバーフローの問題はi128を使えばよいです。 // Palindromic Number #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&m…

5完。何が悪かったんだろう。スピードか、実装力か。考察はそれほど時間かかってないけど、実装は方針考えるのに時間使ったり重い実装選んだりしてる。実装速度と精度は、今回はよかったと思う（バグらせまくったのは精度というより方針側）。 A - Piling Up 茶色になることは考えなくていいので、100で割って（切り捨て）1を足せば個数がわかる。答えは400未満（終了後にちゃんと考えると100以下も言える）なので全探索する。最初、個数をそのまま比較していたが、そもそも1を足す必要がないと実装が進んでから気づいた。解説を見て。なるほど、最長100かかるところから、道をどれだけ進んであるかを引けば答えだ…

5完2WA 各問題 A - Piling Up 基本的に 100 - R % 100 ですが、R % 100 が 0 の時は 100 です。 B - Japanese Cursed Doll L をソートして、長いほうから P 番目の人が何日後に T 以上になるかをチェックすればよいです。その人が最初から T 以上であれば 0 です。 C - Avoid K Palindrome 2 全探索すればよいです。 D - Palindromic Number 各桁ごとにいくつ回文数があるかは計算で求められます。また回文数は下半分を決めれば上半分も決まるため、桁数が確定すればそこから何番目の回文数を求…

https://projecteuler.net/problem=3610進で回文数を出してそれが2進で回文数になっているか調べるくらいですが、2進で考えると回文数は必ず奇数になるんですね。 これを進めて考えると、例えば、17xxxという10進数を2進にすると10xx…となりますが、末尾を考えると10進で71で2進で01ですが、4で割ると余りが3と1になり、17xxxはありえないことが分かります。しかし、こうしても速くなりませんでした。 from collections import Set import sys #################### library ###########…

こんにちは。 今回は Project Euler の第1問から第10問まで Haskell で解いてみようと思います。 Project Euler は、時間制限なしの競技プログラミングのようなもので、過去に紹介しています。 taq.hatenadiary.jp そして、Haskell も最近始めました。 taq.hatenadiary.jp 実は割と気に入っていて、何かしたいなと思っていたところ Project Euler の存在を思い出しました。 Python で解いていって記事を書いているのですが、Haskell でも練習がてら解いてみます。 (ここ1年くらい更新が止まっていますが…) t…

さて、6次半二重魔方陣は「たて」「よこ」方向で異なる相愛力を発現するバランス感のわるい歪な構造を有しているとばかり思っていましたが、異なる行と列を組み合わせることにより、同等の相愛力があらわれるという事実が明らかとなりました。