足跡-sokuseki-

りかの日進月歩の記録

C#でプログラミングしてみた

Unityとかやってみたいなあと思ってC#の勉強を始めました。


本気で開発するならIDEを使う必要があるんですが、簡単なC#プログラミングしかしない予定(?)なのでとりあえず端末上でコンパイルして実行できればいいか〜みたいな気持ちです。

ということで、次のコマンドでC#コンパイラ(Mono*1 )をインストールします。

$ brew install mono

インストールが終わったらコードを書きます。

using System;

class HelloWorld
{
        static public void Main ()
        {
                Console.WriteLine("Hello World");
        }

}

名前はなんか適当にhello.csとかにしておく。拡張子は「.cs」です。

保存できたらコンパイルします。次のコマンドでコンパイルするとhello.exeという実行ファイルができます。

$ mcs hello.cs

実行します。

$ mono hello.exe

実行すると端末上に「Hello World」と表示されます。


作成したソースコードhttp://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A&lang=jpに投げます。

ACになります。

めでたしめでたし。

COLOCON -Colopl programming contest 2018- D すぬけそだて――トレーニング――

D - すぬけそだて――トレーニング――

問題概要

スタミナの上限が  X で、 スタミナを全て消費する時間の候補が  N 個ある。
時刻  0 のときにスタミナが  X で、 1 単位時間にスタミナが  1 回復するとき、 i (1 <= i <= N ) 回スタミナを消費する場合の消費したスタミナの合計の最大値を各  i について求めよ。

制約
 1 \le N \le 5000
 1 \le X \le 10^9
 1 \le T_i \le 10^9

TLE解法

dp[  i ][  j ]:= 最後に起動したのが  i 番目の候補で、今までに  j 回起動したときの消費したスタミナの最大値
とすると、遷移が  O(N) かかるので、計算量は合計で  O(N^3) になる。

Submission #2074687 - COLOCON -Colopl programming contest 2018-

解法

最大値を求めるDPは最大値になりうる遷移以外は無駄なので、必要な遷移のみを考えることによって高速化する。

スタミナを消費する回数がたくさんある場合、上限までスタミナが回復してからスタミナを消費すると、上限まで回復したあとから消費するまでにかかる時間ぶん、スタミナを無駄にしてしまう。
また、スタミナを消費する回数が少ない場合、上限まで回復するまで待った方が、上限まで回復する前にスタミナを消費するより、多くのスタミナを消費できる。
よって、スタミナを消費する回数によって、2通りの遷移が考えられ、

  • スタミナが上限まで回復する1つ手前の候補
  • スタミナが上限まで回復した直後の候補

だけを考えれば良い。
これで遷移にかかる計算量が  O(1) になるので、全体で  O(N^2) となり間に合う。

Submission #2075190 - COLOCON -Colopl programming contest 2018-

ABC034 D 食塩水

D - 食塩水

問題概要

 N 個の食塩水があり、  i 番目の食塩水は  w_i グラムで濃度が  p_i \% である。
この中から  K 個選んで混ぜるときの濃度の最大値を求めよ。

制約
 1 \le N, K \le 1000
 0 \le w_i \le 10^9

解法

濃度が  T \% の食塩水を作れるかで二分探索していく。
それぞれの食塩水について、濃度を  T \% にするために必要な水の量(または、濃度を  T \% にするために取り除いても良い水の量)を求める。
食塩水を適切に  K 個選んだときに、
(濃度を  T \% にするために必要な水の量の合計) \le (濃度を  T \% にするために取り除いても良い水の量の合計)
となっていれば、濃度が  T \% の食塩水を作ることができる。

Submission #2083176 - AtCoder Beginner Contest 034

CODE FESTIVAL 2016 Grand Final A 1D Matching

A - 1D Matching


問題概要

一次元の世界に  N 個のパソコンと  N 個の電源がある。  i 番目のパソコンの座標は  a_i であり、  i 番目の電源の座標は  b_i である。
それぞれの電源は一つのパソコンにのみつなぐことができるとき、ケーブルの長さの合計を最小化する場合の数を 10^9+7 で割ったあまりを答えよ。

制約
 1 \le N \le 10^5
 0 \le a_i , b_i \le 10^9

解法

前から順に計算していくことができる。が、証明が難しいので他の人のブログを参考にしてください(最悪)

CODE FESTIVAL 2016 Grand Final: A - 1D Matching · うさぎ小屋
CODE FESTIVAL 2016 Grand Final A - 1D Matching - ferinの競プロ帳

未割り当てのパソコンが  A 個の状態で電源を見ているとき、その電源につなぐことができるパソコンの数は  A 個ある。よって答えに  A を掛けて、未割り当てのパソコンの数を1減らす。また、電源を見ているときに、未割り当てのパソコンがひとつもない場合は、未割り当ての電源の数を1増やす。(この操作はパソコンと電源が入れ替わっても同じ)


Submission #2065237 - CODE FESTIVAL 2016 Grand Final(Parallel)

ARC027 B 大事な数なのでZ回書きまLた。

B - 大事な数なのでZ回書きまLた。

問題概要

2つの文字列が与えられる。同じアルファベットは同じ数字を表し、異なるアルファベットは異なる数字を表す場合と同じ数字を表す場合がある。2つの文字列が同じ  N 桁の数を表すとき、その数は何通りあるか。

制約
 1 \le N \le 18

解法

アルファベットをUnion Findを使って管理する。

各桁の文字において、両方共が数字の場合は無視して良い。
片方が数字の場合は、もう片方のアルファベットは数字が固定されるため、そのアルファベットのとりうる値は1通りしかないので、アルファベットに使われることのないある数(numとする)を用意して、その数にuniteする。
両方がアルファベットの場合は、それらのアルファベットは同じ数字を表すため、uniteする。

あとは、片方の文字列を最初から見て、そのアルファベットがnumにつながっていたら(すでにuniteしていたら)、その桁のとりうる数字は1通りしかないので何もしない。numにつながっていなかったら(uniteされてなくて親が違ったら)、そのアルファベットは10通り(文字列の先頭ならば9通り)の数字をとるので、答えにかけあわせる。そしてそのアルファベットは値を決めたとして、numにuniteする。


Submission #2019412 - AtCoder Regular Contest 027

ARC085 / ABC078 C HSI

C - HSI

問題概要

プログラミングコンテストの 'YES' か 'NO' で答える問題でTLEした。
テストケースは  N ケースあり、そのうち  M ケースでTLEしていた。
そこで、  M ケースではそれぞれ実行に  1900 ms かかって  \frac{1}{2} の確率で正解し, 残りの  N - M ケースではそれぞれ実行に  100 ms かかって必ず正解するプログラムへ書き換えた。
一度ですべてのケースに正解するまで提出を繰り返したときの、プログラムの実行時間の総和の期待値を求めよ。

制約
 1 \le N \le 100
 1 \le M \le min(N, 5)

解法

この問題の答えを  y msとすると、あるケースで不正解だった場合、それ以降の提出の実行時間の総和の期待値は  y msになる。
よって、1回の提出での実行時間の総和を  x ms、すべてのケースに正解する確率を  p とすると、
 y = x + (1 - p)y
という式が成り立ち、この式を整理すると、この問題の答え  y
 y = \frac{x}{p}
になる。

ここで、
 x = 1900M + 100(N - M)
 p = \frac{1}{2^M}
であるので、代入すると
 y = ( 1900M + 100(N - M) )2^M
となる。


Submission #2012637 - AtCoder Regular Contest 085

ARC087 / ABC082 D FT Robot

D - FT Robot

問題概要

2次元平面の原点にロボットが置かれていて、はじめは  x 軸の正の方向を向いている。
'F', 'T' のみからなる文字列  s が命令として与えられ、先頭から順に実行される。

  • 'F' : 今向いている向きに1すすむ
  • 'T' : 時計回りまたは反時計回りの好きな方向に90度だけ向きを変える

すべての命令を実行した後にロボットが座標  (x, y) にいることができるか判定せよ。

制約
 1 \le | s | \le 8000
 | x | , | y |  \le | s |

解法

命令Tは90度だけ向きを変えることができるから、命令Tを区切りとして分割した時、 i 番目(1-indexed)の区間 i が奇数なら  x 座標の向きの移動、  i が偶数なら  y 座標の向きの移動になる。
よって、  x 座標の移動と  y 座標の移動は別々に考えてよい。

 dp_x [i][j] :=  i 番目の  x 軸方向の移動をした後に  x 座標が  j かどうか
 dp_y [i][j] :=  i 番目の  y 軸方向の移動をした後に  y 座標が  j かどうか

という2つのDPを行い、最終的に座標  (x, y) にいるかを判定すればよい。
DPの計算量は  O(| s | ^2) なので十分間に合う。

Submission #2009622 - AtCoder Regular Contest 087
(配列aに分割して入れていく必要はないということに通ってから気づいた)