AtCoder Beginner Contest 152 D - Handstand 2
少し風邪をひいていました、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc)にて開催されました、AtCoder Beginner Contest 152 D問題「D - Handstand 2」の問題と僕との戦闘記です。
0.はじめに
1.問題文
正の整数 N が与えられます。 N 以下の正の整数の組 ( A , B ) であって、次の条件を満たすものの個数を求めてください。
- A , B を先頭に 0 のつかない 10 進数表記で表したときに、 A の末尾の桁が B の先頭の桁に等しく、 A の先頭の桁が B の末尾の桁に等しい
2.制約
- 1 ≤ N ≤ 2 × 105
- 入力はすべて整数である。
3.入力例
- 入力
200000
- 出力
400000008
4.初見の感想
- 制約が2×105であるのでO(N2)の計算量は難しい
- 最初と最後の文字を固定して、間の文字を再帰的に考える方法を最初考えた
→N以下という判定を行って個数を計算するところが少し複雑となる
→そもそも最初と最後の文字の組み合わせ分やらなければならない(9×9=81通り)
5.学びポイント
- O(N)の解法を考える
- 1~Nまでのfor文を回して数字をそれぞれ最初と最後の文字ごとに分類する
- 今回は二次元配列としてtemp[最初の文字,最後の文字]といった配列を用意し、それぞれの個数を分類しています
- 最初の文字の出し方→数字÷(10^桁数)で求められる(小数点以下切り下げ)
- 最後の文字の出し方→数字%10で求められる
6.コードと簡単な解説
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main(string[] args)
{
//入力
int N = int.Parse(Console.ReadLine());
int[,] temp = new int[10, 10];
for (int i = 1; i <= N; i++)
{
//最初と最後の数字を出す
int left = (int)(i / Math.Pow(10, (int)Math.Log10(i)));
int right = (int)(i % 10);
//数字を分類する
if (left != 0 && right != 0)
{
temp[left, right]++;
}
}
int ans = 0;
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
{
//求めるパターンが何個か数える
ans+=temp[i, j] * temp[j, i];
}
}
Console.WriteLine(ans);
}
}
7.最後に
この方針に行きつくまでに時間がかかってしまうのが反省点です…
AtCoder Beginner Contest 147 D - Xor Sum 4
あったかい飲み物が離せません、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc147/tasks/abc147_d)にて開催されました、AtCoder Beginner Contest 147 D問題「D - Xor Sum 4」の問題と僕との戦闘記です。
0.はじめに
1.問題文
N
個の整数があり、
i
番目の整数は
A
i
です。
を 109 + 7 で割った余りを求めてください。
2.制約
- 2 ≤ N ≤ 3 × 105
- 0 ≤ A i < 260
- 入力中のすべての値は整数である。
3.入力例
- 入力
10 3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820
- 出力
103715602
4.初見の感想
- XOR演算自体はabで実装できるので簡単
- 260は整数型に収まらないので工夫が必要
- 全パターン計算していると計算時間が終わらない
5.学びポイント
- XOR演算は桁の繰り上がりがないので各桁でそれぞれ考える
- XORは片方が0、片方が1の時計算結果が1になるのでそれぞれの数字で「0の個数」×「1の個数」を計算すれば何回1になるかが計算できる
- 個数計算は計算量O(N)なので総当たりのO(N2)より相当早い
- 260は整数型に収まらないので各桁でループを回して計算する
6.コードと簡単な解説
using System;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
//入力
int N = int.Parse(Console.ReadLine());
long[] A = new long[N];
string[] str = Console.ReadLine().Split();
for (var i = 0; i < N; i++)
{
A[i] = long.Parse(str[i]);
}
long[] D1 = new long[61];
long[] D2 = new long[61];
long mod = 1000000007;
for (var i = 0; i < N; i++)
{
long digit = 1;
for (var j = 0; j <= 60; j++)
{
//各桁で0と1の個数計算
if (A[i] / digit % 2 == 1)
{
D1[j]++;
}
else
{
D2[j]++;
}
digit *= 2;
}
}
long digit1 = 1;
long ans = 0;
for (var i = 0; i <= 60; i++)
{
//何回XORになるかを計算
long temp = D1[i] * D2[i] % mod;
temp = digit1 % mod * temp % mod;
ans = (ans + temp) % mod;
digit1 *= 2;
}
Console.WriteLine(ans);
}
}
7.最後に
本番では解けなかったので残念でした…
AtCoder Beginner Contest 147 B - Palindrome-philia
寒くて布団が恋しい季節です、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc147/tasks/abc147_b)にて開催されました、AtCoder Beginner Contest 147 B問題「B - Palindrome-philia」の問題と僕との戦闘記です。
0.はじめに
1.問題文
高八士君は回文が大好きで、回文でない文字列が許せません。高八士君は文字列を 1 回ハグするごとに、文字列から 1 文字を選んで任意の文字に変えることができます。
文字列 S が与えられます。 S を回文にするために必要なハグの最小回数を答えてください。
2.制約
- S は半角英小文字のみから成る文字列
- S の長さは 1 以上 100 以下
3.入力例
- 入力
abcdabc
- 出力
2
4.初見の感想
- 前と後ろから順に比較して、真ん中まで異なる回数を数えます
- 入力の長さが奇数と偶数で真ん中の定義が少し変わります
5.学びポイント
- 例えば文字数が3の時は2個目までは見てほしい訳です
- 小数点の切り上げを行うのでCeling関数を使います
6.コードと簡単な解説
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
string input = Console.ReadLine();
double half = input.Length/2;
half = Math.Ceiling(half);
int ans = 0;
for (int i = 0; i < half; i++)
{
if (input[i] != input[input.Length - i - 1])
{
ans++;
}
}
Console.WriteLine(ans);
}
}
7.最後に
実際は小数点切り下げでも問題ないですよ！
AtCoder Beginner Contest 147 A - Blackjack
雨に濡れるのが辛い季節になりました、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc147/tasks/abc147_a)にて開催されました、AtCoder Beginner Contest 147 A問題「A - Blackjack」の問題と僕との戦闘記です。
0.はじめに
1.問題文
3 個の整数 A 1 , A 2 , A 3 が与えられます。
A 1 + A 2 + A 3 が 22 以上なら bust、 21 以下なら win を出力してください。
2.制約
- 1 ≤ A i ≤ 13( i= 1 , 2 , 3 )
- 入力中のすべての値は整数である。
3.入力例
- 入力
13 7 2
- 出力
bust
4.初見の感想
- 単純に入力を足して条件分岐です！
5.コードと簡単な解説
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
string[] input = Console.ReadLine().Split();
int[] a = new int[3];
a[0] = int.Parse(input[0]);
a[1] = int.Parse(input[1]);
a[2] = int.Parse(input[2]);
if (a[0] + a[1] + a[2] >= 22) { Console.WriteLine("bust"); }
else { Console.WriteLine("win"); }
}
}
6.最後に
LINQもどこかでしっかり復習したい…
三井住友信託銀行プログラミングコンテスト2019 C - 100 to 105
毎日鍋を食べてしまいます、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_c)にて開催されました、三井住友信託銀行プログラミングコンテスト2019 C問題「C - 100 to 105」の問題と僕との戦闘記です。
0.はじめに
1.問題文
AtCoder 商店では、以下の 6 種類の品物が 1000000 個ずつ売られています。
- 1 個 100 円のおにぎり
- 1 個 101 円のサンドイッチ
- 1 個 102 円のクッキー
- 1 個 103 円のケーキ
- 1 個 104 円の飴
- 1 個 105 円のパソコン
高橋君は、合計価格がちょうど X 円となるような買い物をしたいです。そのような買い方が存在するか判定してください。 ただし、消費税は考えないものとします。
2.制約
- 1 ≤ X ≤ 100000
- X は整数
3.入力例
- 入力
615
- 出力
1
4.初見の感想
- 入力数字の100以上の値と100以下の値が重要
- 入力数字を100で割ったら何個ぐらい買ったかがわかる
- 100以下は購入個数×5以下まで再現できる
5.学びポイント
- 実は2000以上は必ず再現できる(20個以上買うので100円～105円のコンビネーションで再現できる)
6.コードと簡単な解説
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
int X = int.Parse(Console.ReadLine());
if (X >= 2000) { Console.WriteLine("1"); }
else
{
if (X % 100 <= (X / 100) * 5) { Console.WriteLine("1"); }
else { Console.WriteLine("0"); }
}
}
}
7.最後に
こういうの気付くのどう訓練すればいいんでしょうね？
三井住友信託銀行プログラミングコンテスト2019 B - Tax Rate
こたつで寝落ちする回数が増えてきました、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_b)にて開催されました、三井住友信託銀行プログラミングコンテスト2019 B問題「B - Tax Rate」の問題と僕との戦闘記です。
0.はじめに
1.問題文
高橋君は ABC 洋菓子店でアップルパイをひとつ買い、そのとき N 円を支払ったことを覚えています。
この店で食料品を購入する際には 8 パーセントの消費税が課されます。すなわち、税抜価格 X 円のアップルパイを買う際には X × 1.08 円 (小数点以下切り捨て) を支払わなければなりません。
高橋君はアップルパイの税抜価格 X を忘れてしまい、これを知りたくなりました。 N を入力として X を求めるプログラムを書いてください。なお、 X は整数とします。
ただし、考えられる税抜価格が複数存在する場合はそのうちのいずれか 1 つを求めてください。また、高橋君が支払った金額 N を覚え間違えている可能性もあるので、アップルパイの税抜価格として考えられるものが存在しない場合はその旨を報告してください。
2.制約
- 1 ≤ N ≤ 50000
- N は整数
3.入力例
- 入力
1079
- 出力
:(
4.初見の感想
- ×1.08や÷1.08をすると小数点以下の値が出る
- 入力値を÷1.08して小数点切り捨てし元の数を計算、×1.08して入力値に戻るかどうかを判定する
5.学びポイント
- Math.Floor関数を使うと小数点の切り捨てができる
- Math.Roundで四捨五入できる
6.コードと簡単な解説
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
int N = int.Parse(Console.ReadLine());
double temp = N / 1.08;
double Ans = Math.Round(temp);
if (N == Math.Floor(Ans * 1.08)) { Console.WriteLine(Ans); }
else { Console.WriteLine(":("); }
}
}
7.最後に
初めて四捨五入などを使ったので勉強になりました
三井住友信託銀行プログラミングコンテスト2019 A - November 30
おいしそうなクリスマスケーキのチラシが入る季節になりました、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_a)にて開催されました、三井住友信託銀行プログラミングコンテスト2019 A問題「A - November 30」の問題と僕との戦闘記です。
0.はじめに
1.問題文
2019 年 11 月 30 日のような、ある月の最後の日を「月末日」といいます。
整数 M_1 , D_1 , M_2 , D_2 が入力されます。 2019 年 M_1 月 D_1 日の次の日が 2019 年 M_2 月 D_2 日であることが分かっています。 2019 年 M_1 月 D_1 日が月末日であるか判定してください
2.制約
- 2019 年 M_1 月 D_1 日、
- 2019 年 M_2 月 D_2 日はともにグレゴリオ暦において存在する日付である。
- 2019 年 M_1 月 D_1 日の次の日は 2019 年 M_2 月 D_2 日である。
3.入力例
- 入力
11 30 12 1
- 出力
1
4.初見の感想
- 月の判定なので、一個目と二個目の月を単純比較！
5.コードと簡単な解説
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
//一つ目の入力
string[] temp = Console.ReadLine().Split();
int M1 = int.Parse(temp[0]);
//二つ目の入力
temp = Console.ReadLine().Split();
int M2 = int.Parse(temp[0]);
//入力値の比較
if (M1 == M2) { Console.WriteLine("0"); }
else { Console.WriteLine("1"); }
}
}
6.最後に
やはり更新が滞りがちになってしまいますね…
